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

《数据结构：7大排序算法(C实现)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、冒泡排序、选择排序、插入排序、shell排序、堆排序、快速排序、归并排序一、排序：将杂乱无章的数据元素，通过一定的方法按关键字顺序排列的过程　　排序分为内部排序、外部排序;　　若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。　　反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序　假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，　即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。　

2、　1.冒泡排序　　　　时间复杂度：最好的情况：表本身就是有序的，n-1次比较,时间复杂度为O(n);最坏的情况：表是逆序的，此时需要比较1+2+3+...(n-1)=(n(n-1))/2,时间复杂度为O(n2)　　　　优点：简单、稳定　　　　缺点：慢，每次只能移动相邻两个数据，效率低　　　1//冒泡排序2voidBubble_Sort(int*list,intcount)3{4intflag=true;5inti=0,j=0;6for(i=0;i<=count&&flag;i++)7{8flag=false;9for(j=count-1;j>=i;j--)10{11

3、if(list[j]

4、1;jlist[j])11{12min=j;13}14}15if(min!=i)16{17swap(list[i],list[min]);18}1920}21}　　3.插入排序　　　　时间复杂度：最好情况：表本身就是有序的，比较次数是n-1次，没有移动记录,时间复杂度为O(n)；最坏情况：表本身是无序的，比较次数是2+3+4+...+n=(n+2)(n-1)/2,移动次数也达到最大　　　　值为(n+4)(n-1)/2次，所以时间复杂度为O(n2);如果根据概论相同的原则，平均比较和移动次数约为n2/4;　　　　优点

5、：比选择，冒泡排序性能要好一些　　　　缺点：效率较低1//插入排序2voidInsert_Sort(int*list,intcount)3{4inttemp;/*此处充当哨兵，不在list数组里面单独占一个单位*/5inti,j;6for(i=1;itemp&&j>=0;j--)12{13list[j+1]=list[j];14}15list[j+1]=temp;16}17}18}　　4.shell排序　　　　时间复杂度：O

6、(n3/2)　　　　优点：跳跃式移动，使得排序效率提高　　　　缺点：不是一种稳定的排序算法　　　　1　　//shell排序2voidShell_Sort(int*list,intcount)3{4inti,j;5inttemp;6intincrement=count;7do8{9increment=increment/3+1;10for(i=increment;i=0&&list[j]>temp;j

7、-=increment)16{17list[j+increment]=list[j];18}19list[j+increment]=temp;2021}2223}2425}while(increment>1);26}　　5.堆排序　　　　时间复杂度：O(nlogn)　　　　优点：性能上远远超过冒泡、选择、插入的时间复杂度O(n2)　　　　缺点：不是一种稳定的排序算法　　　　c++实现：//调整为一个堆voidHeap_Adjust(int*list,ints,intm){inttemp=list[s];for(intj=2*s+1;j<=m;j=2*j+1){i