排序

我们数据结构常见的排序有四大种，四大种又分为七小种，如图所示

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

为了不破坏arr序列，我们定义了tem序列接收，然后最后把tem数组覆盖arr,
时间复杂度为n*logn

voidMergeSort(int*arr,intn){int*tem =(int*)malloc(sizeof(int)*n);_MergeSort(arr,0,n -1,tem);free(tem);}void_MergeSort(int*arr,intleft,intright,int*tem){if(left >=right){return;}intmid =(left +right)/2;_MergeSort(arr,left,mid,tem);_MergeSort(arr,mid+1,right,tem);intbegin1 =left;intbegin2 =mid +1;intend1 =mid;intend2 =right;intx =begin1;while(begin1 <=end1 &&begin2 <=end2){if(arr[begin1]<arr[begin2]){tem[x++]=arr[begin1++];}else{tem[x++]=arr[begin2++];}}while(begin1 <=end1){tem[x++]=arr[begin1++];}while(begin2 <=end2){tem[x++]=arr[begin2++];}for(inti =left;i <right;i++){arr[i]=tem[i];}}

最后总结一下所有排序时间

源码

Sort.h

#pragmaonce#include<stdio.h>#include<stdlib.h>#include<time.h>#include<assert.h>#include<stdbool.h>typedefintHeapType;typedefstructHeap{HeapType*a;intcapacity;intsize;}Heap;voidSeletSort(HeapType*arr,intn);voidInite(Heap*p);voidPush(Heap*p,HeapType x);voidPop(Heap*p);bool Empty(Heap*p);HeapType Top(Heap*p);voidPrint(Heap*p);voidDestry(Heap*p);voidSwap(HeapType*a,HeapType*b);voidAdjustUp(HeapType*a,intchild);voidAdjustDown(HeapType*a,intparent,intn);voidHeapSort(HeapType*arr,intn);voidBubbleSort(int*a,intn);voidswap(int*a,int*b);voidInsertSort(int*arr,intn);voidShellSort(int*arr,intn);intGetKeyi(int*arr,intleft,intright);voidQuickSort(int*arr,intleft,intright);voidMergeSort(int*arr,intn);void_MergeSort(int*arr,intleft,intright,int*tem);voidtest();

test.c

#define_CRT_SECURE_NO_WARNINGS1#include"Sort.h"#include"time.h"#include"stdlib.h"intmain(){test();return0;}

Sort.c

#define_CRT_SECURE_NO_WARNINGS1#include"Sort.h"voidtest(){srand((unsigned)time(0));constintN =100000;int*a1 =(int*)malloc(sizeof(int)*N);//创建100000个空间的数组int*a2 =(int*)malloc(sizeof(int)*N);//创建100000个空间的数组int*a3 =(int*)malloc(sizeof(int)*N);//创建100000个空间的数组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);for(inti =0;i <N;i++){a1[i]=rand();//循环100000次，每次赋予a1数组随机值a2[i]=a1[i];//赋值值来自上次一数组a3[i]=a1[i];a4[i]=a1[i];a5[i]=a1[i];a6[i]=a1[i];a7[i]=a1[i];}intbegin1 =clock();InsertSort(a1,N);intend1 =clock();intbegin2 =clock();ShellSort(a2,N);intend2 =clock();intbegin3=clock();SeletSort(a3,N);intend3 =clock();intbegin4 =clock();HeapSort(a4,N);intend4 =clock();intbegin5 =clock();BubbleSort(a5,N);intend5 =clock();intbegin6=clock();QuickSort(a6,0,N-1);intend6 =clock();intbegin7 =clock();MergeSort(a7,N -1);intend7 =clock();printf("InsertSort:%d\n",end1 -begin1);printf("ShellSort:%d\n",end2 -begin2);printf("SelectSort:%d\n",end3 -begin3);printf("HeapSort:%d\n",end4 -begin4);printf("BubbleSort:%d\n",end5 -begin5);printf("QuickSort:%d\n",end6 -begin6);printf("MergeSort:%d\n",end7 -begin7);}voidswap(int*a,int*b){inttmp =*a;*a =*b;*b =tmp;}voidBubbleSort(int*a,intn){for(inti =0;i <n -1;i++){intxz =0;for(intj =0;j <n -i -1;j++){if(a[j]>a[j +1]){swap(&a[j],&a[j +1]);xz =1;}}if(xz ==0){break;}}}voidInsertSort(int*arr,intn){for(inti =0;i <n -1;i++){intend =i;inttem =arr[end +1];while(end >=0){if(arr[end]>tem){arr[end +1]=arr[end];end--;}else{break;}}arr[end +1]=tem;}}voidShellSort(int*arr,intn){intgap =n;while(gap >1){gap =gap /3+1;for(inti =0;i <n -gap;i++){intend =i;inttem =arr[end +gap];while(end >=0){if(arr[end]>tem){arr[end +gap]=arr[end];end -=gap;}else{break;}}arr[end +gap]=tem;}}}voidSeletSort(int*arr,intn){intend =n -1;intbegin =0;intmax,min;max =min =0;while(begin <end){max =min =begin;for(inti =begin +1;i <=end;i++){if(arr[i]>arr[max]){max =i;}if(arr[i]<arr[min]){min =i;}}if(max ==begin){max =min;}Swap(&arr[min],&arr[begin]);Swap(&arr[max],&arr[end]);begin++;end--;}}voidInite(Heap*p){p->a =NULL;p->capacity =p->size =0;}voidPush(Heap*php,HeapType x){assert(php);if(php->size ==php->capacity){intnewcapacity =php->capacity ==0?4:php->capacity *2;HeapType*tmp =(HeapType*)realloc(php->a,newcapacity *sizeof(HeapType));if(tmp ==NULL){perror("realloc fail");return;}php->a =tmp;php->capacity =newcapacity;}php->a[php->size]=x;php->size++;AdjustUp(php->a,php->size -1);}voidPop(Heap*p){Swap(&p->a[0],&p->a[p->size -1]);p->size--;AdjustDown(p->a,0,p->size);}bool Empty(Heap*p){returnp->size ==0;}HeapType Top(Heap*p){returnp->a[0];}voidPrint(Heap*p){{while(!Empty(p)){printf("%d ",Top(p));Pop(p);}}}voidSwap(HeapType*a,HeapType*b){inttem =*a;*a =*b;*b =tem;}voidAdjustUp(HeapType*a,intchild){intparent =(child -1)/2;while(child >0){if(a[child]<a[parent]){Swap(&a[child],&a[parent]);child =parent;parent =(child -1)/2;}else{break;}}}voidAdjustDown(HeapType*a,intparent,intn){intchild =parent *2+1;while(child <n){if(child +1<n &&a[child]>a[child +1]){child =child +1;}if(a[parent]>a[child]){Swap(&a[parent],&a[child]);parent =child;child =child *2+1;}else{break;}}}voidHeapSort(HeapType*arr,intn){for(inti =(n -1-1)/2;i >=0;i--){AdjustDown(arr,i,n);}intend =n -1;for(inti =end;i >0;i--){Swap(&arr[0],&arr[end]);AdjustDown(arr,0,end);end--;}}intGetKeyi(int*arr,intleft,intright){intkeyi =left;left++;while(right>=left){while(left<=right&&arr[right]>arr[keyi]){right--;}while(left <=right &&arr[left]<arr[keyi]){left++;}if(left <=right){swap(&arr[right--],&arr[left++]);}}swap(&arr[keyi],&arr[right]);returnright;}voidQuickSort(int*arr,intleft,intright){if(left >=right){return;}intkeyi =GetKeyi(arr,left,right);QuickSort(arr,left,keyi -1);QuickSort(arr,keyi+1,right);}voidMergeSort(int*arr,intn){int*tem =(int*)malloc(sizeof(int)*n);_MergeSort(arr,0,n -1,tem);free(tem);}void_MergeSort(int*arr,intleft,intright,int*tem){if(left >=right){return;}intmid =(left +right)/2;_MergeSort(arr,left,mid,tem);_MergeSort(arr,mid+1,right,tem);intbegin1 =left;intbegin2 =mid +1;intend1 =mid;intend2 =right;intx =begin1;while(begin1 <=end1 &&begin2 <=end2){if(arr[begin1]<arr[begin2]){tem[x++]=arr[begin1++];}else{tem[x++]=arr[begin2++];}}while(begin1 <=end1){tem[x++]=arr[begin1++];}while(begin2 <=end2){tem[x++]=arr[begin2++];}for(inti =left;i <right;i++){arr[i]=tem[i];}}