#include<stdio.h> #include<time.h> #include <stdlib.h>const int maxx=20010; int a[11][maxx];void swap(int *x,int *y) {int z=*x;*x=*y;*y=z; } /*--------------插入排序--------------*/ void zjcrsort()//直接插入排序 {int b[11][maxx];for(int i=0;i<10;i++)for(int j=0;j<20000;j++) b[i][j]=a[i][j];//按照a數組去初始化b數組for(int k=0;k<10;k++){int begin=clock(); int cnt1=0,cnt2=0;//比較次數和移動次數for(int i=1;i<20000;i++){int j=i;int temp=b[k][i];while(j>0&&temp<b[k][j-1])//依次移動數組順序 {cnt1++,cnt2++;b[k][j]=b[k][j-1];j--;}b[k][j]=temp;}int end=clock();printf("直接插入排序對第%d個樣例的排序時間為:%d\n",k+1,end-begin);} } /*------------希爾排序-------------*/ void shellsort()//希爾排序 {int b[11][maxx];for(int i=0;i<10;i++)for(int j=0;j<20000;j++) b[i][j]=a[i][j];//按照a數組去初始化b數組for(int k=0;k<10;k++){int begin=clock();int cnt1=0,cnt2=0;//比較次數和移動次數int gap;for(gap=20000/2;gap>0;gap/=2)//每次的增量，遞減趨勢{for(int i=gap;i<20000;i++)//每次增量下，進行幾組插入排序{for(int j=i;j-gap>=0&&b[k][j-gap]>b[k][j];j-=gap)//每個元素組中進行直接插入排序{swap(&b[k][j-gap], &b[k][j]);cnt1++,cnt2++;//移動和比較次數加一 }}}int end=clock();printf("希爾排序對第%d個樣例的排序時間為:%d\n",k+1,end-begin);} } /*--------簡單選擇排序----------*/ void chocsort()//簡單選擇排序 {int b[11][maxx];for(int i=0;i<10;i++)for(int j=0;j<20000;j++) b[i][j]=a[i][j];//按照a數組去初始化b數組for(int k=0;k<10;k++){int begin=clock();int cnt1=0,cnt2=0;//比較次數和移動次數for(int i=0;i<200000-1;i++){int _min=i;//記錄最小元素位置 for(int j=i+1;j<20000;j++){if(b[k][j]<b[k][_min]){cnt1++;_min=j;//更換最小元素位置 }}if(_min!=i){cnt2++;swap(&b[k][i],&b[k][_min]);//交換位置 }}int end=clock();printf("簡單選擇排序對第%d個樣例的排序時間為:%d\n",k+1,end-begin);}} /*------冒泡排序-------*/ void mpsort()//冒泡排序 {int b[11][maxx];for(int i=0;i<10;i++)for(int j=0;j<20000;j++) b[i][j]=a[i][j];//按照a數組去初始化b數組for(int k=0;k<10;k++){int begin=clock(); int cnt1=0,cnt2=0;//比較次數和移動次數for(int i=0;i<20000-1;i++)//排序的總輪數 {for(int j=0;j<20000-1-i;j++)//每輪排序的個數{if(b[k][j]>b[k][j+1]){cnt1++;cnt2++;swap(&b[k][j],&b[k][j+1]);}}}int end=clock();printf("冒泡排序對第%d個樣例的排序時間為:%d\n",k+1,end-begin);} } /*--------快速排序---------*/ void quicksort(int l,int r,int *cnt1,int *cnt2,int xx[][maxx],int k)//快速排序函數 {int i,j,t,temp;if(l>r) return ;//不符合排序條件，直接返回temp=xx[k][l];//temp中存的是基準數i=l;j=r;while(i!=j){//先找右邊的數字while(xx[k][j]>=temp&&i<j) j--;//再找左邊的數字while(xx[k][i]<=temp&&i<j) i++;if(i<j) swap(&xx[k][i],&xx[k][j]);}xx[k][l]=xx[k][i];xx[k][i]=temp;//最終將基準數歸位quicksort(l,i-1,cnt1,cnt2,xx,k);//繼續處理左邊的，這里是一個遞歸的過程quicksort(i+1,r,cnt1,cnt2,xx,k);//繼續處理右邊的 ，這里是一個遞歸的過程 } void Qsort()//快速排序 {int b[11][maxx];for(int i=0;i<10;i++)for(int j=0;j<20000;j++) b[i][j]=a[i][j];//按照a數組去初始化b數組for(int k=0;k<10;k++){int begin=clock();int cnt1=0,cnt2=0;//比較次數和移動次數quicksort(0,9999,&cnt1,&cnt2,b,k);int end=clock();printf("快速排序對第%d個樣例的排序時間為:%d\n",k+1,end-begin);} } /*------基數排序-------*/ int max(int date[],int n){//此函數用于求解所給數組中最大數有幾位int max=0;for(int i=0;i<n;i++){int count=1,tem=date[i];while(tem/10!=0){//計算每個數的位數，用count計數tem=tem/10;count++;}if(count>max)max=count;//把最大位數賦值max}return max; } void basesort(int date[],int n){int max1=max(date,n);//取得最大位數int num=1;for(int i=0;i<max1;i++){//位數決定排序循環次數int count[10];//聲明count為了統計每個桶放了幾個數int temp[10][maxx];//temp相當于桶，前一個數標記第幾個籃子，后一個為了標記放的個數for(int f=0;f<10;f++){//對聲明數組初始化count[f]=0;}for(int g=0;g<10;g++){//對聲明數組初始化for(int z=0;z<n;z++){temp[g][z]=0;}}for(int j=0;j<n;j++){int fg=date[j]/num;//num是變量，因為每次循環比較的位是不同的int k=fg%10;count[k]++;int te=count[k]-1;temp[k][te]=date[j];//把數據放k桶的te位上存儲}int b=0;for(int h=0;h<10;h++){if(count[h]>0){//h>0說明h桶內有數字存儲for(int v=0;v<count[h];v++){//count[h]是h桶的存儲個數date[b]=temp[h][v];//把桶內排好的數全都倒給要排序的數組，進行下輪排序b++;}}}num=num*10;} } void Jssort()//基數排序 {int b[maxx];for(int k=0;k<10;k++){for(int i=0;i<20000;i++) b[i]=a[k][i];int begin=clock();basesort(b,20000);int end=clock();printf("基數排序對第%d個樣例的排序時間為:%d\n",k+1,end-begin);} } /*---------歸并排序---------*/ void merge_sort(int *list, int length) {int i, left_min, left_max, right_min, right_max, next;int *tmp = (int*)malloc(sizeof(int) * length);if (tmp == NULL){fputs("Error: out of memory\n", stderr);abort();}for (i = 1; i < length; i *= 2) // i為步長，1,2,4,8……{for (left_min = 0; left_min < length - i; left_min = right_max){right_min = left_max = left_min + i;right_max = left_max + i;if (right_max > length)right_max = length;next = 0;while (left_min < left_max && right_min < right_max)tmp[next++] = list[left_min] > list[right_min] ? list[right_min++] : list[left_min++];while (left_min < left_max)list[--right_min] = list[--left_max];while (next > 0)list[--right_min] = tmp[--next];}}free(tmp); } void Gbsort()//歸并排序 {int b[maxx];for(int k=0;k<10;k++){for(int i=0;i<20000;i++) b[i]=a[k][i];int begin=clock();merge_sort(b,20000);int end=clock();printf("歸并排序對第%d個樣例的排序時間為:%d\n",k+1,end-begin);} } /*----------堆排序-----------*/ void heapAdjust(int *b,int s,int len) {int temp=b[s];for(int j=2*s;j<=len;j*=2){if(j<len && b[j]<b[j+1])j++;if(b[j]>temp){b[s]=b[j];s=j;}elsebreak;}b[s]=temp; } void heapSort(int *b,int len) {for(int i=len/2;i>=1;i--){heapAdjust(b,i,len);}for(int i=len;i>1;i--){swap(&b[1],&b[i]);heapAdjust(b,1,i-1);} } void Dsort()//堆排序 {int b[maxx];for(int k=0;k<10;k++){for(int i=0;i<20000;i++) b[i+1]=a[k][i];int begin=clock();heapSort(b,20000);int end=clock();printf("堆排序對第%d個樣例的排序時間為:%d\n",k+1,end-begin);} } int main() {freopen("1.txt","r",stdin);//文件輸入for(int i=0;i<10;i++)for(int j=0;j<20000;j++) scanf("%d",&a[i][j]);printf("文件讀入完成\n");printf("***直接插入排序***\n");zjcrsort();printf("***希爾排序***\n");shellsort();printf("***簡單選擇排序***\n");chocsort();printf("***冒泡排序***\n");mpsort();printf("***快速排序***\n");Qsort();printf("***基數排序***\n");Jssort();printf("***堆排序***\n");Dsort();printf("***歸并排序***\n");Gbsort();return 0; }

努力加油a啊，(^o)/~

總結

以上是生活随笔為你收集整理的八种基本排序方式（插入排序，希尔排序，选择排序，冒泡排序，快速排序，堆排序，归并排序，基数排序）代码模板以及时间复杂度的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。