数据结构：7大排序算法(C实现).docx

冒泡排序、选择排序、插入排序、shell排序、堆排序、快速排序、归并排序一、排序 ：将杂乱无章的数据元素，通过一定的方法按关键字顺序排列的过程排序分为内部排序、外部排序;若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序 假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变， 即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的； 否则称为不稳定的。1. 冒泡排序时间复杂度：最好的情况：表本身就是有序的，n-1次比较,时间复杂度为O(n);最坏的情况：表是逆序的，此时需要比较 1+2+3+.(n-1) = (n(n-1)/2,时间复杂度为O(n2)优点：简单、稳定缺点：慢，每次只能移动相邻两个数据，效率低 1 /冒泡排序 2 void Bubble_Sort(int *list,int count) 3 4 int flag = true; 5 int i = 0,j = 0; 6 for(i=0;i=i;j-)10 11 if(listjlistj-1)12 13 swap(listj,listj-1);14 flag = true;15 16 17 18 19 2. 选择排序时间复杂度：O(n2) ：无论最好、最坏情况，都需要比较 (n(n-1)/2次，最好的情况交换次数为0，最坏的情况交换次数为n-1优点：交换移动数据次数相当少，性能上略优于冒泡排序缺点：效率低 1 /选择排序 2 void Select_Sort(int *list,int count) 3 4 int min,i,j; 5 for(i=0;icount;i+) 6 7 min = i; 8 for(j=i+1;jlistj)11 12 min = j;13 14 15 if(min!=i)16 17 swap(listi,listmin);18 19 20 21 3. 插入排序时间复杂度：最好情况：表本身就是有序的，比较次数是n-1次，没有移动记录,时间复杂度为O(n)；最坏情况：表本身是无序的，比较次数是2+3+4+.+n = (n+2)(n-1)/2,移动次数也达到最大值为 (n+4)(n-1)/2次，所以时间复杂度为O(n2);如果根据概论相同的原则，平均比较和移动次数约为n2/4;优点：比选择，冒泡排序性能要好一些缺点：效率较低 1 /插入排序 2 void Insert_Sort(int *list,int count) 3 4 int temp;/*此处充当哨兵，不在list数组里面单独占一个单位*/ 5 int i,j; 6 for(i=1;icount;i+) 7 8 if(listitemp&j=0;j-)12 13 listj+1 = listj;14 15 listj+1 = temp;16 17 18 4. shell排序时间复杂度：O(n3/2)优点：跳跃式移动，使得排序效率提高缺点：不是一种稳定的排序算法 1 /shell排序 2 void Shell_Sort(int *list,int count) 3 4 int i,j; 5 int temp; 6 int increment = count; 7 do 8 9 increment = increment/3+1;10 for(i = increment;icount;i+)11 12 if(listi=0&listjtemp;j-=increment)16 17 listj+increment = listj;18 19 listj+increment = temp;20 21 22 23 24 25 while(increment1);26 5. 堆排序时间复杂度：O(nlogn)优点：性能上远远超过冒泡、选择、插入的时间复杂度O(n2)缺点：不是一种稳定的排序算法c+实现：/调整为一个堆void Heap_Adjust(int *list,int s,int m) int temp = lists; for(int j=2*s+1;j=m;j = 2*j+1) if(listjlistj+1&jlistj) break; lists = listj; s = j; lists = temp;/堆排序void Heap_Sort(int *list,int len) /创建一个大顶堆 for(int s = len/2-1;s=0;s-) Heap_Adjust(list,s,len-1); /排序 for(int i = len-1;i = 1;i-) swap(list0,listi); Heap_Adjust(list,0,i-1); 6. 归并排序时间复杂度：O(nlogn)优点：效率高、稳定缺点：占用内存较多c+实现：/将有个有序数组排序void Merge(int *list,int start,int mid,int end) const int len1 = mid -start +1; const int len2 = end -mid; const int len = end - start +1; int i,j,k; int * front = (int *)malloc(sizeof(int)*len1); int * back = (int *)malloc(sizeof(int)*len2); for(i=0;ilen1;i+) fronti = liststart+i; for(j=0;jlen2;j+) backj = listmid+j+1; for(i=0,j=0,k=start;ilen1&jlen2&kend;k+) if(frontibackj) listk = fronti; i+; else listk = backj; j+; while(ilen1) listk+ = fronti+; while(jlen2) listk+ = backj+; /归并排序 void Merge_Sort(int *list,int count) MSort(list,0,count-1); /归并排序 void MSort(int *list,int start,int end) if(startend) int mid = (start+end)/2; MSort(list,0,mid); MSort(list,mid+1,end); Merge(list,start,mid,end); 7. 快速排序时间复杂度：O(nlogn)(平均情况)优点：目前来说最快的排序算法，现在的快排算法大多是快速排序算法的改进算法缺点：跳跃式，不稳定 /快速排序 void Quick_Sort(int *list,int count) Qsort(list,0,count-1); /快速排序 void Qsort(int *list,int low,int high) int pivot; if(lowhigh) pivot =Partition(list,low,high); Qsort(list,low,pivot-1); Qsort(list,pivot+1,high); int Partition(int *list,int low,int high) int pivotKey; pivotKey = listlow; while(lowhigh) while(low=piv