十六种经典排序算法

1、/头文件定义 #include stdafx.h #include #include #include #include #include void bubbleSort(int *a,int len);/冒泡算法 void UpdBubbleSort1(int *a,int len);/改进冒泡算法1 -找到一次循环的已排好序位置 void UpdbubbleSort2(int *a,int len); /改进冒泡算法2 -一次循环找到最大最小值 void quickSort_update(int *a, int len, int k); /改进快速排序-先使8的块基本有序-实测比一般快速排

2、序节约28%时间(59秒,1亿条随机数据，逆序数时间较长) void qsort_improve(int *a,int low,int high, int k);/改进快速排序子算法 void InsertSort(int *a, int n); /直接插入排序 void shellSort(int *a, int n);/直接插入排序威力加强版本-希尔排序(适用逆序数，1亿逆序数据93s 1亿随机数据223s) void ShellSort_local(int *a, int len, int dk); void HeapSort(int *H,int length); /堆排序-step1

3、:建堆 2：n/2个父节点堆有序 3、从堆尾元素依次和堆顶交换 void BuildingHeap(int *H, int length); /堆排序-子函数 (逆序数据50s,1亿条随机数据133秒) void HeapAdjust(int *H,int s, int length); /堆排序-子函数 unsigned long ulrand(void);/产生大的随机数 void selectSort(int *a, int n); /选择排序 int SelectMinKey(int *a, int n, int i); void SelectSort_double(int *r,in

4、t n); typedef int ElemType ; void MergeSort(ElemType *r, ElemType *rf, int lenght);/归并排序(1亿逆序：30s 1亿随机：46s ) void Merge(ElemType *r,ElemType *rf, int i, int m, int n); /65148-65149/* 总结提升算法效率方法 1、减小循环次数，大循环在里面，小循环再外面-循环次数多的话切换用时多， 2、侦测已完成任务，提前结束 3、递归算法占用的空间较大，容易溢出, 优点是算法复杂度低*/void QuickSort(int *a,i

5、nt low,int high); /(全完逆序100w数据40分钟-已验证)int LocalQuickSort(int *a,int low,int high); void Swap(int *p1,int *p2); void PrintArray(int *a,int len); void InitArray(int *a,int len); int first_posi=0; intprivotKey=0;int SortOkSign=0;/无/需交换的标志#define lenArr int lastChangePos=lenArr-1;/最后一次交换的位置 int gloData

6、=0;int k=0,m=0,n=0,x=0; int *p= (int *) malloc(lenArr*sizeof(int);int blenArr;int main()/int len=5; if(p=NULL) printf(malloc Error); return 0; clock_t start_2,end_2; /InitArray(p,lenArr); / start_1=clock(); /开始时间start_1,end_1, / InsertSort(p,lenArr); / UpdbubbleSort2(p,lenArr); / QuickSort(p,0,lenAr

7、r-1); /PrintArray(p,lenArr); / quickSort_update(p,lenArr-1,10); /InsertSort(p,lenArr); / HeapSort(p,lenArr);/ MergeSort(p,b,lenArr);/ end_1=clock(); /结束时间 InitArray(p,lenArr); / PrintArray(p,lenArr); start_2=clock(); /结束时间 / shellSort(p,lenArr); / bubbleSort(p,lenArr); HeapSort(p,lenArr); end_2=cloc

8、k(); / PrintArray(p,lenArr);double db2=(double)(end_2-start_2)/CLOCKS_PER_SEC;printf(n排序时间%lf,db2);return 0;/改进冒泡算法 -检测已排序好的尾部段，不再排序 void UpdBubbleSort1(int *a,int len)int tempInt=0; for(int j=len;j0;j-) int min_posi=(j-1)lastChangePos?(j-1):lastChangePos;for(int i=0;iai+1)tempInt=ai;ai=ai+1;ai+1=te

9、mpInt; SortOkSign=1; lastChangePos=i+1;if(0=SortOkSign)break;/将rim和rm +1 n归并到辅助数组rfin void Merge(ElemType *r,ElemType *rf, int i, int m, int n) int j,k; for(j=m+1,k=i; i=m & j =n ; +k) if(rj ri) rfk = rj+; else rfk = ri+; while(i = m) rfk+ = ri+; while(j = n) rfk+ = rj+; void MergeSort(ElemType *r,

10、ElemType *rf, int lenght) for(int g=0;glenArr;g+) rfg=rg; int len = 1; ElemType *q = r; / ElemType *tmp ; while(len lenght) int s = len; len = 2 * s ; int i = 0; while(i+ len =lenght) Merge(q, rf, i, i+ s-1, i+ len-1 ); /对等长的两个子表合并 i = i+ len; if(i + s-1=lenght-1) Merge(q, rf, i, i+ s -1, lenght -1)

11、; /对不等长的两个子表合并 /tmp = q; q = rf; rf = tmp; /交换q,rf，以保证下一趟归并时，仍从q 归并到rf for(int g=0;g 0; -i) /交换堆顶元素H0和堆中最后一个元素 int temp = Hi; Hi = H0; H0 = temp; /每次交换堆顶元素和堆中最后一个元素之后，都要对堆进行调整 HeapAdjust(H,0,i); /printf(n第%d次排序结果:,length-i);/ PrintArray(p,lenArr); void BuildingHeap(int *H, int length) /堆排序-子函数 /最后一个

12、有孩子的节点的位置 i= (length -1) / 2 for (int i = (length -1) / 2 ; i = 0; -i) HeapAdjust(H,i,length); void HeapAdjust(int *H,int s, int length) /堆排序-子函数 int tmp = Hs; int child = 2*s+1; /左孩子结点的位置。(i+1 为当前调整结点的右孩子结点的位置) while (child length) if(child+1 length & HchildHchild+1) / 如果右孩子大于左孩子(找到比当前待调整结点大的孩子结点)

13、+child ; if(HsHchild) / 如果较大的子结点大于父结点 Hs = Hchild; / 那么把较大的子结点往上移动，替换它的父结点 s = child; / 重新设置s ,即待调整的下一个结点的位置 child = 2*s+1; else / 如果当前待调整结点大于它的左右孩子，则不需要调整，直接退出 break; Hs = tmp; / 当前待调整的结点放到比其大的孩子结点位置上 int SelectMinKey(int *a, int n, int i) int k = i; for(int j=i+1 ;j aj) k = j; return k; void Selec

14、tSort_double(int *r,int n) int i ,j , min ,max, tmp; for (i=0 ;i = n/2;i+) / 做不超过n/2趟选择排序 min = i; max = i ; /分别记录最大和最小关键字记录位置 for (j= i+1; j rmax) max = j ; continue ; if (rj rmin) min = j ; /该交换操作还可分情况讨论以提高效率 if(max=i)&(min=n-i-1)tmp = rmin; rmin = rmax; rmax = tmp; elsetmp = ri; ri = rmin; rmin =

15、 tmp; tmp = rn-i-1; rn-i-1 = rmax; rmax = tmp; /* * 选择排序 * */ void selectSort(int *a, int n) int key, tmp; for(int i = 0; i n; +i) key = SelectMinKey(a, n,i); /选择最小的元素 if(key != i) tmp = ai; ai = akey; akey = tmp; /最小元素与第i位置元素互换 void ShellSort_local(int *a, int len, int dk)for( k=0;kdk;k+)for( n=dk+

16、k;n=0)&(x= 1) ShellSort_local(a, n, dk); dk = dk/2; void quickSort_update(int *a, int len, int k) qsort_improve(a,0,len,k);/先调用改进算法Qsort使之基本有序 /再用插入排序对基本有序序列排序 for(int i=1; i=len;i+) int tmp = ai; int j=i-1; while(tmp k ) /长度大于k时递归, k为指定的数 int pivot = LocalQuickSort(a, low, high); / 调用的Partition算法保持

17、不变 qsort_improve(a, low, pivot - 1,k); qsort_improve(a, pivot + 1, high,k); void InsertSort(int *a, int len) for(int i= 1; ilen; i+) int j= i-1; int x = ai; /复制为哨兵，即存储待排序元素 while(x aj) /查找在有序表的插入位置 aj+1 = aj; j-; /元素后移 aj+1 = x; /插入到正确位置 /print(a,n,i); /打印每趟排序的结果 / -快速排序 void QuickSort( int *a,int l

18、ow,int high) if(lowhigh) first_posi=LocalQuickSort(a,low,high); QuickSort(a,low,first_posi-1); QuickSort(a,first_posi+1,high); int LocalQuickSort(int *a,int low,int high) privotKey=alow;fflush(stdin); while(lowhigh) while(low=privotKey) -high; Swap(&alow,&ahigh); while(lowhigh&alow0;j-) for(int i=0;

19、iai+1) tempInt=ai; ai=ai+1; ai+1=tempInt; SortOkSign=1; if(0=SortOkSign) break; /冒泡-两端冒泡，减小循环次数-尚未证实算法效率提高 void UpdbubbleSort2(int *a,int len)int tempInt=0; int high_Posi=len-1; int low_Posi=0; while(low_Posihigh_Posi) for(int i=low_Posi;iai+1) tempInt=ai; ai=ai+1; ai+1=tempInt; SortOkSign=1; for(int j=high_Posi-1;jlow_Posi;j-) if(ajaj-1) tempInt=aj; aj=aj-1; aj-1=tempInt; SortOkSign=1; high_Posi-; low_