《数据结构：7大排序算法(c实现)》由会员分享，可在线阅读，更多相关《数据结构：7大排序算法(c实现)（7页珍藏版）》请在金锄头文库上搜索。
1、冒泡排序、选择排序、插入排序、shell 排序、堆排序、快速排序、归并排序一、排序 ：将杂乱无章的数据元素，通过一定的方法按关键字顺序排列的过程排序分为内部排序、外部排序;若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且 ri 在 rj 之前，而在排序后的序列中，ri 仍在rj 之前，则称这种排序算法是稳定的；否则称为不稳定的。1. 冒泡排序时间复杂度：最好
2、的情况：表本身就是有序的，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)11 12 min = j;13 14 15 if(min!=i)16 17 swap(listi,listmin);18
3、 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
4、 i,j;6 for(i=1;itempj-)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 do8 9 increment = increment/3+1;10 for(i = increment;i=0j-=increment)16
5、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;jlistj)break;lists = listj;s = j;lists = temp;/堆排序void He
6、ap_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
7、 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;i=pivotKey)high-;swap(listlow,listhigh);while(lowhigh&listlow=pivotKey)low+;swap(listlow,listhigh);return low;void swap(int& a,int& b)int temp = a;a = b;b = temp;
