??博主主頁：@??. 一懷明月??
?????專欄系列：線性代數(shù)，C初學(xué)者入門訓(xùn)練，題解C，C的使用文章，「初學(xué)」C++
??座右銘：“不要等到什么都沒有了，才下定決心去做”
??????大家覺不錯的話，就懇求大家點點關(guān)注，點點小愛心，指點指點??????
目錄
冒泡排序
概念
時間復(fù)雜度
空間復(fù)雜度
穩(wěn)定性
算法分析
選擇排序
概念
時間復(fù)雜度
空間復(fù)雜度
穩(wěn)定性
算法分析
直接插入排序
概念
時間復(fù)雜度
空間復(fù)雜度
穩(wěn)定性
算法分析
希爾排序
概念
時間復(fù)雜度
空間復(fù)雜度
穩(wěn)定性
算法分析
希爾排序的特性總結(jié)
堆排序
概念
時間復(fù)雜度
空間復(fù)雜度
算法分析
快速排序
概念
時間復(fù)雜度
空間復(fù)雜度
算法分析
hoare 版
挖坑版
?前后指針版
?拓展延伸
快速排序的非遞歸
算法：
快速排序的優(yōu)化
?1.三數(shù)取中
算法：
2.三路劃分
算法：
歸并排序
概念
時間復(fù)雜度
空間復(fù)雜度
算法分析
拓展延伸
歸并非遞歸
基數(shù)排序
概念
時間復(fù)雜度
空間復(fù)雜度
算法分析
排序算法對比
排序10000個，統(tǒng)計所需要的時間
結(jié)果
冒泡排序
概念
它重復(fù)地訪問排序的數(shù)列，依次比較兩個相鄰的數(shù)，如果順序（從小到大）錯誤就把它們交換過來，訪問數(shù)列是重復(fù)地進行，直到?jīng)]有相鄰數(shù)需要交換，就可以認為該數(shù)列已經(jīng)排序完成。這個算法的名字由來是因為越小的數(shù)會經(jīng)由交換慢慢“浮”到數(shù)列的頂端（升序或降序排列），就如同汽水中的氣泡最終會上浮到頂端一樣，故名“冒泡排序”。
時間復(fù)雜度
O(N^2)
空間復(fù)雜度
O(1)
穩(wěn)定性
穩(wěn)定
算法分析
void BubbleSort(int* a,int n) { for(int i=0;i<n-1;i++) { for(int j=0;j<n-1-i;j++) { if(a[j]>a[j+1]) Swap(&a[j], &a[j+1]);//交換函數(shù) } } }
選擇排序
概念
選擇排序（Selection sort）是一種簡單直觀排序算法。它的工作原理是：第一次從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個元素，存放在序列的起始位置，然后再從剩余的未排序元素中尋找到最?。ù螅┰?，然后放到已排序的序列的末尾。以此類推，直到全部待排序的數(shù)據(jù)元素的個數(shù)為零。時間復(fù)雜度
O(N^2)空間復(fù)雜度
O(1)穩(wěn)定性
不穩(wěn)定算法分析
算法分析 void SelectSort(int* a,int n) { for(int i=0;i<n-1;i++) { for(int j=i+1;j<n;j++) { if(a[i]>a[j]) Swap(&a[i], &a[j]); } } }
直接插入排序
概念
插入排序，一般也被稱為直接插入排序。對于少量元素的排序，它是一個有效的算法?。插入排序是一種最簡單的排序方法，它的基本思想是將一個記錄插入到已經(jīng)排好序的有序表中，從而一個新的、記錄數(shù)增1的有序表。在其實現(xiàn)過程使用雙層循環(huán)，外層循環(huán)對除了第一個元素之外的所有元素，內(nèi)層循環(huán)對當前元素前面有序表進行待插入位置查找，并進行移動。
時間復(fù)雜度
O(N^2)
空間復(fù)雜度
O(1)
穩(wěn)定性
穩(wěn)定
算法分析
void InsertSort(int* a,int n) { for(int i=0;i<n-1;i++)//i<n-1，為了temp=a[i+1]越界 { int end=i; int temp=a[i+1]; while(end>=0) { if(a[end]>temp) { a[end+1]=a[end]; end--; } else//如果a[end]<temp說明0-i區(qū)間已經(jīng)是有序的，不需在比較了，這樣既提高了效率也防止了越界 break; } a[end+1]=temp;//這一步千萬別忘記了 } }
希爾排序
概念
希爾排序(Shell's Sort)是插入的一種又稱“縮小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一種更高效的改進版本。希爾排序是非穩(wěn)定排序算法。該方法因 D.L.Shell 于 1959 年提出而得名。希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關(guān)鍵詞越來越多，當增量減至 1 時，整個文件恰被分成一組，算法便終止。時間復(fù)雜度
O(N*logN)空間復(fù)雜度
O(1)穩(wěn)定性
不穩(wěn)定算法分析
void ShellSort(int* a,int n) { int gap=n;//增量，初始值為 n while(gap>1) { gap=gap/3+1;//這里不固定，也可以是gap/3，gap/2+1，gap/2...，但是gap/3+1 更優(yōu) for(int i=0;i<n-gap;i++)//i<n-gap是防止end+gap 越界 { int end=i; int temp=a[i+gap]; while(end>=0) { if(a[end]>temp) { a[end+gap]=a[end]; end-=gap; } else break; } a[end+gap]=temp; } } }希爾排序的特性總結(jié)
1. 希爾排序是對直接插入排序的優(yōu)化。
2. 當gap > 1時都是預(yù)排序，目的是讓數(shù)組更接近于有序。當gap == 1時，數(shù)組已經(jīng)接近有序的了，這樣就會很快。這樣整體而言，可以達到優(yōu)化的效果。我們實現(xiàn)后可以進行性能測試的對比。
3. 希爾排序的時間復(fù)雜度不好計算，因為gap的取值方法很多，導(dǎo)致很難去計算，因此在好些樹中給出的希爾排序的時間復(fù)雜度都不固定，因為我們的gap是按照Knuth提出的方式取值的，而且Knuth進行了大量的試驗統(tǒng)計，我們暫時就按照：O(N^1.25)到O(1.6*N^1.25)來算。
堆排序
概念
堆排序(Heapsort)是指利用堆積樹（堆）這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法，它是選擇排序的一種。它是
通過堆來進行選擇數(shù)據(jù)。需要注意的是排升序要建大堆，排降序建小堆。
時間復(fù)雜度
O(N*logN)
空間復(fù)雜度
O(1)
算法分析
//向下建堆_大堆 //一次建堆 void AdjustDown(int* a,int n,int parent) { int child=parent*2+1; while(child<n) { if(child+1<n&&a[child]<a[child+1]) child++; if(a[child]>a[parent]) { Swap(&a[child], &a[parent]); parent=child; child=parent*2+1; } else break; } } //堆排序 void HeapSort(int* a,int n) { //這里建堆，其實這里也可以是 // for(int i=1;i<n;i++) // { // AdjustDown(a, n,i); // } //這種是從第二層到第 n-1 層的建堆，效率不高 //下面這種是從第n-1層到第零層建堆，雖然兩種方法的層數(shù)一樣，但是涉及的元素個數(shù)相差很多 for(int i=(n-1-1)/2;i>=0;i--) { AdjustDown(a, n, i); } int end=n-1; while(end>0) { //因為是大堆，所以第一個元素始終是最大的，我們讓最后一個元素和第一個交換，然后再調(diào)整一下，讓調(diào)整后的第一個元素是最大的，注意這次調(diào)整的元素個數(shù)要減一，然后循環(huán)直到 end（每次調(diào)整的元素個數(shù)） 為一就不用交換調(diào)整了。 Swap(&a[0], &a[end]); AdjustDown(a, end, 0); end--; } }
快速排序
概念
快速排序是Hoare于1962年提出的一種二叉樹結(jié)構(gòu)的交換排序方法，其基本思想為：任取待排序元素序列中的某元素作為基準值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準值，右子序列中所有元素均大于基準值，然后最左右子序列重復(fù)該過程，直到所有元素都排列在相應(yīng)位置上為止時間復(fù)雜度
O(N*logN)空間復(fù)雜度
O(logN~N)算法分析
hoare 版
int partsort_hoare(int* a,int begin,int end) { int keyi=begin; while(begin<end) { //右邊找小 while(begin<end&&a[end]>a[keyi]) { end--; } //左邊找大 while(begin<end&&a[begin]<a[keyi]) { begin++; } Swap(&a[begin], &a[end]); } Swap(&a[begin], &a[keyi]); keyi=begin; return keyi; } void QuickSort_1(int* a,int begin,int end) { if(begin>=end) return; int ret=partsort_hoare(a, begin,end); //[begin,ret-1][ret][ret+1,end] int begin1=begin,end1=ret-1; int begin2=ret+1,end2=end; QuickSort_1(a, begin1, end1); QuickSort_1(a, begin2, end2); } //這里所以添加這個函數(shù)，是為了和其他排序函數(shù)參數(shù)保持一致 void QuickSort(int* a,int n) { QuickSort_1(a, 0, n-1); }除了 hoare 版還有兩個版本。
挖坑版
int partsort_hole(int* a,int begin,int end) { int key=a[begin]; int hole=begin; while(begin<end) { //右邊找小 while(begin<end&&a[end]>key) { end--; } Swap(&a[hole], &a[end]); hole=end; //左邊找大 while(begin<end&&a[begin]<key) { begin++; } Swap(&a[hole], &a[begin]); hole=begin; } a[hole]=key; return hole; }?前后指針版
int partsort_prev_cur(int* a,int begin,int end) { int keyi=begin; int prev=begin; int cur=begin+1; while(cur<=end) { //思路：讓 prev 指向的值始終小于a[keyi]，讓 cur 指向大于a[keyi] //1.最開始的 prev 和 cur 相鄰 //2.當 cur 遇到比a[keyi]的大的值以后，他們 1 以后，他們之間的值都是比a[keyi]大的值 //3.cur找小，找到小以后，跟++prev位置的值交換，相當于大的翻滾似的右邊推，同時把小的換到左邊 if(a[cur]<a[keyi]&&++prev!=cur) { Swap(&a[prev], &a[cur]); } cur++; } Swap(&a[prev], &a[keyi]); return prev; }?拓展延伸
快速排序的非遞歸
之所以會有非遞歸版本，因為遞歸需要開辟棧幀，開辟棧幀是在棧進行的，棧內(nèi)存較小，如果遞歸很深會導(dǎo)致棧溢出，而非遞歸是通過循環(huán)實現(xiàn)的，是在堆上實現(xiàn)的，堆內(nèi)存較大，不會出現(xiàn)溢出。
算法：
這里使用了棧這種數(shù)據(jù)結(jié)構(gòu)
void QuickSortNonR(int* a,int n) { int begin=0,end=n-1; ST st; STInit(&st); STPush(&st, end); STPush(&st, begin); while(!STEmpty(&st)) { int left=STTop(&st); STPop(&st); int right=STTop(&st); STPop(&st); int keyi=partsort_hoare(a, left, right); if(keyi+1<right) { STPush(&st, right); STPush(&st, keyi+1); } if(keyi-1>left) { STPush(&st, keyi-1); STPush(&st, left); } } }棧的實現(xiàn)：C語言中數(shù)據(jù)結(jié)構(gòu)——棧_??. 一懷明月?的博客-CSDN博客
快速排序的優(yōu)化
?1.三數(shù)取中
如果排序的元素是有序的，這將對快速排序非常不友好，所以采用三數(shù)取中。
算法：
int GetMidIndex(int* a,int left,int right) { int mid=(left+right)/2; if(a[left]<a[mid]) { if(a[mid]<a[right]) return mid; else if(a[left]<a[right]) return right; else return left; } else { if(a[mid]>a[right]) return mid; else if(a[left]>a[right]) return right; else return left; } } 使用方法： 在 partsort_hoare/ partsort_hole/ partsort_prev_cur中加入 int midi=GetMidIndex(a, begin, end); Swap(&a[begin], &a[midi]);2.三路劃分
因為快速排序的效率和排序的數(shù)列有關(guān)系，快速排序的時間效率O(N*lgN~N^2)，如果數(shù)列如果全是一樣的數(shù)，就會導(dǎo)致效率為O(N^2)，所以需要對現(xiàn)有的結(jié)構(gòu)進行優(yōu)化，例如三路劃分
以前的快速排序結(jié)構(gòu)劃分的區(qū)間只有兩個【小于等于key】【大于等于key】
我們將數(shù)列劃分為三個區(qū)間【小于key】【等于key】【大于key】
三路劃分的整體方法是hoare版和前后指針版的結(jié)合
cur=left key=a[left]
1.a[cur]<key 交換a[left]和a[cur] ++left,++cur
2.a[cur]>key?交換a[right和a[cur] --right
3.a[cur]==key ++cur
實際上：
1.小的放到左邊，大的放到右邊
2.跟key相等的值放到中間
這里針對于遞歸版本
算法：
void QuickSort(int* a,int begin,int end) { if(begin>=end) return; int left=begin; int right=end; int cur=left+1; int midi=GetMidIndex(a, left, right); Swap(&a[left], &a[midi]); int key=a[left]; while(cur<=right) { if(a[cur]<key) { Swap(&a[left], &a[cur]); left++; cur++; } else if(a[cur]>key) { Swap(&a[cur], &a[right]); right--; } else { cur++; } } //[begin,left-1][left,right][right+1,end] QuickSort(a, begin, left-1); QuickSort(a, right+1, end); }
歸并排序
概念
歸并排序是建立在歸并操作上的一種有效，穩(wěn)定的排序算法，該算法是采用分治法（Divide and Conquer）的一個非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。時間復(fù)雜度
O(N*logN)空間復(fù)雜度
O(N)算法分析
?排序詳情：秒懂百科?
void _MergeSort(int* a,int begin,int end,int* temp) { if(begin==end) return; int midi=(begin+end)/2; //[begin,midi][midi+1,end] int begin1=begin,end1=midi; int begin2=midi+1,end2=end; _MergeSort(a, begin1, end1, temp); _MergeSort(a, begin2, end2, temp); int j=begin; while(begin1<=end1&&begin2<=end2) { if(a[begin1]<a[begin2]) { temp[j++]=a[begin1++]; } else { temp[j++]=a[begin2++]; } } while(begin1<=end1) { temp[j++]=a[begin1++]; } while(begin2<=end2) { temp[j++]=a[begin2++]; } memcpy(a+begin,temp+begin,sizeof(int)*(end-begin+1)); } void MergeSort(int* a,int n) { //歸并兩個區(qū)間，做不到在原數(shù)組中操作，需要一個數(shù)組作為媒介，temp就是媒介 int* temp=(int*)malloc(sizeof(int)*n); _MergeSort(a,0,n-1,temp); free(temp); }拓展延伸
歸并非遞歸
歸并排序的非遞歸結(jié)構(gòu)是通過循環(huán)實現(xiàn)的，遞歸是將整個區(qū)間劃分為一個個小區(qū)間進行歸并，而非遞歸是將一個個小區(qū)間歸并，通過變量gap控制每次歸并區(qū)間的大小，如圖
非遞歸的結(jié)構(gòu)，通常會有越界的可能
?
1.將一二種越界跳出循環(huán)，第三種采用修正的方法
void MergeSortNonR(int* a,int n) { int* temp=(int* )malloc(sizeof(int)*n); int gap=1; while(gap<n) { int j=0; for(int i=0;i<n;i+=2*gap) { int begin1=i,end1=i+gap-1; int begin2=i+gap,end2=i+2*gap-1; if(end1>=n||begin2>=n) break; if(end2>=n) { end2=n-1; } while(begin1<=end1&&begin2<=end2) { if(a[begin1]<a[begin2]) { temp[j++]=a[begin1++]; } else { temp[j++]=a[begin2++]; } } while(begin1<=end1) { temp[j++]=a[begin1++]; } while(begin2<=end2) { temp[j++]=a[begin2++]; } //歸并一段，拷貝一段 memcpy(a+i,temp+i,sizeof(int)*(end2-i+1)); } gap*=2; } free(temp); }?2.全按修正方法
void MergeSortNonR_1(int* a,int n) { int* temp=(int*)malloc(sizeof(int)*n); int gap=1; while(gap<n) { int j=0; for(int i=0;i<n;i+=2*gap) { int begin1=i,end1=i+gap-1; int begin2=i+gap,end2=i+2*gap-1; if(end1>=n) { end1=n-1; //修成不存在的區(qū)間 begin2=n; end2=n-1; } else if(begin2>=n) { //修成不存在的區(qū)間 begin2=n; end2=n-1; } else if(end2>=n) { end2=n-1; } while(begin1<=end1&&begin2<=end2) { if(a[begin1]<a[begin2]) { temp[j++]=a[begin1++]; } else { temp[j++]=a[begin2++]; } } while(begin1<=end1) { temp[j++]=a[begin1++]; } while(begin2<=end2) { temp[j++]=a[begin2++]; } memcpy(a+i,temp+i,sizeof(int)*(end2-i+1)); } gap*=2; } free(temp); }
基數(shù)排序
概念
基數(shù)排序（radix sort）屬于“分配式排序”（distribution sort），又稱“桶子法”（bucket sort）或bin sort，顧名思義，它是透過鍵值的部份資訊，將要排序的元素至某些“桶”中，藉以達到排序的作用，基數(shù)排序法是屬于穩(wěn)定性的排序，在某些時候，基數(shù)排序法的效率高于其它的穩(wěn)定性排序法。
時間復(fù)雜度
O(N+range)
空間復(fù)雜度
O(range)
算法分析
void CountSort(int* a,int n) { //計算范圍 int min=a[0],max=a[0]; for(int i=0;i<n;i++) { if(a[i]<min) min=a[i]; if(a[i]>max) max=a[i]; } int range=max-min+1; //統(tǒng)計次數(shù) int* temp=(int* )malloc(sizeof(int)*range); memset(temp, 0, sizeof(int)*range); for(int i=0;i<n;i++) { temp[a[i]-min]++; } //排序 int j=0; for(int i=0;i<range;i++) { while(temp[i]--) { a[j++]=i+min; } } }
排序算法對比
排序10000個，統(tǒng)計所需要的時間
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<time.h> //打印函數(shù) void Print(int* a,int n) { for(int i=0;i<n;i++) { printf("%d ",a[i]); } printf("\n"); } //交換函數(shù) void Swap(int* e1,int* e2) { int temp=*e1; *e1=*e2; *e2=temp; } //向下調(diào)整 //大根堆 void AdjustDown(int* a,int n,int parent) { int child=parent*2+1; while(child<n) { if(child+1<n&&a[child]>a[child+1]) { child++; } if(a[child]<a[parent]) { Swap(&a[child], &a[parent]); parent=child; child=parent*2+1; } else { break; } } } //建大堆排序 void AdjustDownSort(int*a,int n) { for(int i=(n-1-1)/2;i>=0;i--) { AdjustDown(a, n, i); } int end=n-1; while(end>0) { Swap(&a[0], &a[end]); AdjustDown(a, end, 0); end--; } } //冒泡排序 void BubbleSort(int* a,int n) { for(int i=0;i<n-1;i++) { for(int j=0;j<n-i-1;j++) { if(a[j]>a[j+1]) Swap(&a[j], &a[j+1]); } } } //選擇排序 void SelectSort(int* a,int n) { for(int i=0;i<n;i++) { for(int j=i+1;j<n;j++) { if(a[i]>a[j]) Swap(&a[i], &a[j]); } } } //插入排序 void InsertSort(int* a,int n) { for(int i=0;i<n;i++) { int end=i; int temp=a[i+1]; while(end>=0) { if(a[end]>temp) { a[end+1]=a[end]; end--; } else { break; } } a[end+1]=temp; } } //希爾排序 void SellSort(int* a,int n) { int gap=n; while(gap>1) { gap=gap/3+1; for(int i=0;i<n-gap;i++) { int end=i; int temp=a[end+gap]; while(end>=0) { if(a[end]>temp) { a[end+gap]=a[end]; end-=gap; } else { break; } } a[end+gap]=temp; } } } //系統(tǒng)自帶的快排 int cmp_int(const void* e1, const void* e2) { return *(int*)e1 - *(int*)e2; } //快速排序 hoare 版本 int GetMidIndex(int* a,int left,int right) { int mid=(left+right)/2; if(a[left]<a[mid]) { if(a[mid]<a[right]) return mid; else if(a[left]<a[right]) return right; else return left; } else { if(a[mid]>a[right]) return mid; else if(a[left]>a[right]) return right; else return left; } } int partSort(int* a,int left,int right) { int midi=GetMidIndex(a, left, right); Swap(&a[left], &a[midi]); int keyi=left; while(left<right) { //右邊找小 while(left<right&&a[right]>=a[keyi]) { --right; } //左邊找大 while(left<right&&a[left]<=a[keyi]) { ++left; } Swap(&a[right], &a[left]); } Swap(&a[right], &a[keyi]); return left; } void QuickSort(int* a,int begin,int end) { if(begin>=end) return; int key=partSort(a, begin, end); QuickSort(a, begin, key-1); QuickSort(a, key+1, end); } void QuickSort_1(int* a,int begin,int end) { if(begin>=end) return; if(end-begin+1<10) { InsertSort(a+begin, end-begin+1); return; } int key=partSort(a, begin, end); QuickSort(a, begin, key-1); QuickSort(a, key+1, end); } //歸并排序 void _MergeSort(int *a,int begin,int end,int *temp) { if(begin==end) return; int mid=(begin+end)/2; //[begin,mid][mid+1,end] _MergeSort(a, begin, mid, temp); _MergeSort(a, mid+1, end, temp); int begin1=begin,end1=mid; int begin2=mid+1,end2=end; int i=begin; while(begin1<=end1&&begin2<=end2) { if(a[begin1]<a[begin2]) { temp[i++]=a[begin1++]; } else { temp[i++]=a[begin2++]; } } while(begin1<=end1) { temp[i++]=a[begin1++]; } while(begin2<=end2) { temp[i++]=a[begin2++]; } memcpy(a+begin,temp+begin,sizeof(int)*(end-begin+1)); } void MergeSort(int *a,int n) { int* temp=malloc(sizeof(int)*n); _MergeSort(a, 0,n-1,temp); free(temp); } void _MergeSort_1(int *a,int begin,int end,int *temp) { if(begin==end) return; if(end-begin+1<10) { InsertSort(a+begin, end-begin+1); return; } int mid=(begin+end)/2; //[begin,mid][mid+1,end] _MergeSort(a, begin, mid, temp); _MergeSort(a, mid+1, end, temp); int begin1=begin,end1=mid; int begin2=mid+1,end2=end; int i=begin; while(begin1<=end1&&begin2<=end2) { if(a[begin1]<=a[begin2]) { temp[i++]=a[begin1++]; } else { temp[i++]=a[begin2++]; } } while(begin1<=end1) { temp[i++]=a[begin1++]; } while(begin2<=end2) { temp[i++]=a[begin2++]; } memcpy(a+begin,temp+begin,sizeof(int)*(end-begin+1)); } void MergeSort_1(int *a,int n) { int* temp=malloc(sizeof(int)*n); _MergeSort_1(a, 0,n-1,temp); free(temp); } void CountSort(int* a,int n) { int min=a[0],max=a[0]; for(int i=0;i<n;i++) { if(a[i]<min) min=a[i]; if(a[i]>max) max=a[i]; } int range=max-min+1; int* countA=(int*)malloc(sizeof(int)*range); memset(countA,0,sizeof(int)*range); //統(tǒng)計次數(shù) for(int i=0;i<n;i++) { countA[a[i]-min]++; } //排序 int k=0; for(int j=0;j<range;j++) { while(countA[j]--) { a[k++]=j+min; } } } void test1(void) { srand((unsigned int)time(NULL)); const int N=10000; int* a1=(int*)malloc(sizeof(int)*N); int* a2=(int*)malloc(sizeof(int)*N); int* a3=(int*)malloc(sizeof(int)*N); int* a4=(int*)malloc(sizeof(int)*N); int* a5=(int*)malloc(sizeof(int)*N); int* a6=(int*)malloc(sizeof(int)*N); int* a7=(int*)malloc(sizeof(int)*N); int* a8=(int*)malloc(sizeof(int)*N); int* a9=(int*)malloc(sizeof(int)*N); int* a10=(int*)malloc(sizeof(int)*N); int* a11=(int*)malloc(sizeof(int)*N); for(int i=0;i<N;i++) { a1[i]=rand()%10000; a2[i]=a1[i]; a3[i]=a1[i]; a4[i]=a1[i]; a5[i]=a1[i]; a6[i]=a1[i]; a7[i]=a1[i]; a8[i]=a1[i]; a9[i]=a1[i]; a10[i]=a1[i]; a11[i]=a1[i]; } int begin1=(int)clock(); BubbleSort(a1, N); int end1=(int)clock(); printf("冒泡排序所需的時間：%d(10^-3ms)\n",end1-begin1); int begin2=(int)clock(); SelectSort(a2, N); int end2=(int)clock(); printf("選擇排序所需的時間：%d(10^-3ms)\n",end2-begin2); int begin3=(int)clock(); AdjustDownSort(a3, N); int end3=(int)clock(); printf("堆排序所需的時間：%d(10^-3ms)\n",end3-begin3); int begin4=(int)clock(); InsertSort(a4, N); int end4=(int)clock(); printf("插入排序所需的時間：%d(10^-3ms)\n",end4-begin4); int begin5=(int)clock(); SellSort(a5, N); int end5=(int)clock(); printf("希爾排序所需的時間：%d(10^-3ms)\n",end5-begin5); int begin6=(int)clock(); qsort(a6, N, 4, cmp_int); int end6=(int)clock(); printf("快排排序所需的時間：%d(10^-3ms)\n",end6-begin6); int begin7=(int)clock(); QuickSort(a7, 0, N-1); int end7=(int)clock(); printf("Quick排序所需的時間：%d(10^-3ms)\n",end7-begin7); int begin10=(int)clock(); QuickSort_1(a10, 0, N-1); int end10=(int)clock(); printf("Quick+插入排序所需的時間：%d(10^-3ms)\n",end10-begin10); int begin8=(int)clock(); MergeSort(a8, N); int end8=(int)clock(); printf("歸并排序所需的時間：%d(10^-3ms)\n",end8-begin8); int begin9=(int)clock(); MergeSort_1(a9, N); int end9=(int)clock(); printf("歸并+插入排序所需的時間：%d(10^-3ms)\n",end9-begin9); int begin11=(int)clock(); CountSort(a11, N); int end11=(int)clock(); printf("計數(shù)排序所需的時間：%d(10^-3ms)\n",end11-begin11); } int main() { test1(); return 0; }結(jié)果
冒泡排序所需的時間：256675(10^-3ms)
選擇排序所需的時間：306183(10^-3ms)
堆排序所需的時間：1534(10^-3ms)
插入排序所需的時間：51008(10^-3ms)
希爾排序所需的時間：1690(10^-3ms)
快排排序所需的時間：955(10^-3ms)
Quick排序所需的時間：1235(10^-3ms)
Quick+插入排序所需的時間：1285(10^-3ms)
歸并排序所需的時間：1261(10^-3ms)
歸并+插入排序所需的時間：1207(10^-3ms)
計數(shù)排序所需的時間：204(10^-3ms)文章來源：http://www.zghlxwxcb.cn/news/detail-619164.html
??????如果大家還有不懂或者建議都可以發(fā)在評論區(qū)，我們共同探討，共同學(xué)習，共同進步。謝謝大家！ ?????????文章來源地址http://www.zghlxwxcb.cn/news/detail-619164.html
到了這里，關(guān)于常見的幾種排序的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
