5個最常用的C 經(jīng)典算法代碼
[導讀]一、冒泡排序冒泡排序（BubbleSort），是一種計算機科學領域的較簡單的排序算法。它重復地走訪過要排序的元素列，依次比較兩個相鄰的元素，如果他們的順序（如從大到小、首字母從A到Z）錯誤就把他們交換過來。走訪元素的工作是重復地進行直到?jīng)]有相鄰元素需要交換，也就是說該元素列已經(jīng)排...
一、冒泡排序
冒泡排序（Bubble Sort），是一種計算機科學領域的較簡單的排序算法。
它重復地走訪過要排序的元素列，依次比較兩個相鄰的元素，如果他們的順序（如從大到小、首字母從A到Z）錯誤就把他們交換過來。走訪元素的工作是重復地進行直到?jīng)]有相鄰元素需要交換，也就是說該元素列已經(jīng)排序完成。
以下代碼可以直接運行：
#include using namespace std;template<typename T>//整數(shù)或浮點數(shù)皆可使用void bubble_sort(T arr[], int len){ int i, j; T temp; for (i = 0; i < len - 1; i ) for (j = 0; j < len - 1 - i; j ) if (arr[j] > arr[j 1]) { temp = arr[j]; arr[j] = arr[j 1]; arr[j 1] = temp; }}int main(){ int arr[] = { 61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 }; int len = (int) sizeof(arr) / sizeof(*arr); bubble_sort(arr, len); for (int i = 0; i < len; i ) cout << arr[i] << ' '; cout << endl; float arrf[] = { 17.5, 19.1, 0.6, 1.9, 10.5, 12.4, 3.8, 19.7, 1.5, 25.4, 28.6, 4.4, 23.8, 5.4 }; len = (int) sizeof(arrf) / sizeof(*arrf); bubble_sort(arrf, len); for (int i = 0; i < len; i ) cout << arrf[i] << ' '; return 0;}二、快速排序
快速排序（Quicksort）是對冒泡排序的一種改進。
快速排序的思想是：通過一趟排序將要排序的數(shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列。
以下代碼可以直接運行：
#include using namespace std; void Qsort(int arr[], int low, int high){ if (high <= low) return; int i = low; int j = high 1; int key = arr[low]; while (true) { /*從左向右找比key大的值*/ while (arr[ i] < key) { if (i == high){ break; } } /*從右向左找比key小的值*/ while (arr[--j] > key) { if (j == low){ break; } } if (i >= j) break; /*交換i,j對應的值*/ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } /*中樞值與j對應值交換*/ int temp = arr[low]; arr[low] = arr[j]; arr[j] = temp; Qsort(arr, low, j - 1); Qsort(arr, j 1, high);} int main(){ int a[] = {57, 68, 59, 52, 72, 28, 96, 33, 24}; Qsort(a, 0, sizeof(a) / sizeof(a[0]) - 1);/*這里原文第三個參數(shù)要減1否則內(nèi)存越界*/ for(int i = 0; i < sizeof(a) / sizeof(a[0]); i ) { cout << a[i] << ""; } return 0;}/*參考數(shù)據(jù)結構p274(清華大學出版社，嚴蔚敏)*/三、桶排序
桶排序（Bucket sort）或所謂的箱排序，是一個排序算法，工作的原理是將數(shù)組分到有限數(shù)量的桶子里。每個桶子再個別排序（有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進行排序）。桶排序是鴿巢排序的一種歸納結果。當要被排序的數(shù)組內(nèi)的數(shù)值是均勻分配的時候，桶排序使用線性時間（Θ（n））。但桶排序并不是 比較排序，他不受到 O(n log n) 下限的影響。
以下代碼可以直接運行：
#includeusingnamespace std;int a[]={1,255,8,6,25,47,14,35,58,75,96,158,657};const int len=sizeof(a)/sizeof(int);int b[10][len 1]={0};//將b全部置0void bucketSort(int a[]);//桶排序函數(shù)void distribute Elments(int a[],int b[10][len 1],int digits);void collectElments(int a[],int b[10][len 1]);int numOfDigits(int a[]);void zeroBucket(int b[10][len 1]);//將b數(shù)組中的全部元素置0int main(){cout<<"原始數(shù)組：";for(int i=0;icout<",";cout<<endl;bucketSort(a);cout<<"排序后數(shù)組：";for(int i=0;icout<",";cout<<endl;return 0;}void bucketSort(int a[]){int digits=numOfDigits(a);for(int i=1;i<=digits;i ){distributeElments(a,b,i);collectElments(a,b);if(i!=digits)zeroBucket(b);}}int numOfDigits(int a[]){int largest=0;for(int i=0;i//獲取最大值 if(a[i]>largest)largest=a[i];int digits=0;//digits為最大值的位數(shù)while(largest){digits ;largest/=10;}return digits;}void distributeElments(int a[],int b[10][len 1],int digits){int divisor=10;//除數(shù)for(int i=1;idivisor*=10;for(int j=0;j{int numOfDigist=(a[j]%divisor-a[j]%(divisor/10))/(divisor/10);//numOfDigits為相應的(divisor/10)位的值,如當divisor=10時,求的是個位數(shù)int num= b[numOfDigist][0];//用b中第一列的元素來儲存每行中元素的個數(shù)b[numOfDigist][num]=a[j];}}void collectElments(int a[],int b[10][len 1]){int k=0;for(int i=0;i<10;i )for(int j=1;j<=b[i][0];j )a[k ]=b[i][j];}void zeroBucket(int b[][len 1]){for(int i=0;i<10;i )for(int j=0;j1 ;j )b[i][j]=0;}四、合（歸）并排序
歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。
#includeusing namespace std;void merge(int *data, int start, int mid, int end, int *result){ int i, j, k; i = start; j = mid 1; //避免重復比較data[mid] k = 0; while (i <= mid 
下載文檔
