五大基本排序算法

1、一. 选择排序算法：算法基本原理：一次选定数组中的每一个数，记下当前位置并假设它是从当前位置开始后面数中的最小数min=i，从这个数的下一个数开始扫描直到最后一个数，并记录下最小数的位置min，扫描结束后如果min不等于i，说明假设错误，否则交换min与i位置上数。算法实现：#include /选择排序，如果第一个数字小于后面的则向后移动，依次类推该排序时不稳定的，时间复杂度是N平方void main()int array10 = 112,4,2,3,5,33,6,7,8,9;/定义一个数组int length = sizeof(array)/sizeof(array0);/得到数组的长度in

2、t k=0, s=0, i=0, j=0;/k保存临时结果，s，i，j为循环变量/选择排序开始for(i=0;ilength;i+)for(j=i+1;jarrayj)k=arrayi;arrayi=arrayj;arrayj=k;/选择排序结束，输出显示排序的结果for(s=0; slength; s+)printf(%d n,arrays);二.冒泡排序算法基本原理：对尚未排序的各元素从头到尾依次比较相邻的两个元素是否逆序（与欲排顺序相反），若逆序就交换这两元素，经过第一轮比较排序后便可把最大（或最小）的元素排好，然后再用同样的方法把剩下的元素逐个进行比较，就得到了你所要的顺序。算法实现：

3、#include /冒泡排序,开始的时候两个数进行比较，大的向后小的向前，第一次比较很容易的就把最大的一个数字放到了最后小的呢，继续向前，第二次当然也找到了第二个大的，放到倒数第二的位置，如此下去便可。这个是优化的冒泡排序方法，让k=j保存最后的那个数的下标，这样k后面的数都是排序好的了,这个排序是稳定的，时间复杂度是N平方void main()int array10 = 1,2,11,22,33,4,23,234,4,6;int length = sizeof(array)/sizeof(array0);int k=0, s=0, i=0, j=0, m=0;/冒泡排序开始for(i = l

4、ength-1;i0;i=k)for(j=0, k=0;jarrayj+1)/把比较出来大的数据向后移动m=arrayj;arrayj=arrayj+1;arrayj+1=m;k=j;/冒泡排序结束，输出显示排序的结果for(s=0; slength; s+)printf(%d n,arrays);三.快速排序算法基本原理：快速排序（Quicksort）是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程

5、可以递归进行，以此达到整个数据变成有序序列。算法实现：#include /快速排序开始，使用递归方法，取其中一个数（任意基本上都是以第一个为准），先从后面比较，如果这个数比后面的大交换之，如果不大继续比较直到大为止，如果大，则交换之，再到前面比较，如果前面的比这个数小交换之再和后面的比较，第一趟下来比它小的就在前面了，比它大的就在后面喽，然后再把该数组分成两部分使用递归，直到最后排序完成void paixu(int array, int low, int hight)int i,j,t,m;if(lowhight)i = low;j = hight;t = arraylow;while(ij)

6、while(it)/开始和后面的比较，如果后面的比他大继续，如果后面的比它小交换之j-;if(ij)/在没有越界（i是从前面开始，j是从后面开始）的情况下进行交换m=arrayi;arrayi=arrayj;arrayj=m;i+;/让前面的向后移动一个继续比较while(ij & arrayi=t)/和前面的比较，如果前面的小于等于该关键数据继续，如果大于交换之i+;if(ij)m=arrayj;arrayj=arrayi;arrayi=m;j-;arrayi=t;/第一次比较结束，把i放到中间的位置，也即在i前面都比i小，在i后面都比i大paixu(array, low, i-1);/前面

7、部分实现递归paixu(array, i+1, hight);/后面部分实现递归void main()int s=0;int array = 10,22,3,21,45,67,2,11,110,453;int length = sizeof(array)/sizeof(array0);paixu(array,s,length-1);for(s=0;slength;s+)printf(%d n,arrays);四.插入排序有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法插入排序法,插入排序的基本操作就是将一个数据

8、插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为()。是稳定的排序方法。插入算法（insertion sort）把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外，而第二部分就只包含这一个元素。在第一部分排序后，再把这个最后元素插入到此刻已是有序的第一部分里的正确位置中。包括：直接插入排序，折半插入排序，链表插入排序，Shell排序算法基本原理：假定这个数组的序是排好的,然后从头往后,如果有数比当前外层元素的值大,则将这个数的位置往后挪,直到当前外层元素的值大于或等于它前面的位置为止.这具算法在排完前k个数

9、之后,可以保证a1k是局部有序的,保证了插入过程的正确性.算法描述：一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：1. 从第一个元素开始，该元素可以认为已经被排序2. 取出下一个元素，在已经排序的元素序列中从后向前扫描3. 如果该元素（已排序）大于新元素，将该元素移到下一位置4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置5. 将新元素插入到该位置中6. 重复步骤2如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为二分查找排序。算法实现：#include void main()int ar

10、ray = 9,43,567,1,45,23,123,54,234,987;int length = sizeof(array)/sizeof(array0);int i,j,t,m;/插入排序开始for(i=1;i0)&(arrayj-1t)/如果前面的数比它大交换之m=arrayj-1;arrayj-1=arrayj;arrayj=m;j-;/交换完毕继续比较/插入排序结束for(i=0;ilength;i+)printf(%d n,arrayi);五.希尔排序希尔排序是基于插入排序的一种算法，在此算法基础之上增加了一个新的特性，提高了效率。希尔排序的时间复杂度为 O(N*(logN)2)

11、， 没有快速排序算法快 O(N*(logN)，因此中等大小规模表现良好，对规模非常大的数据排序不是最优选择。但是比O(N2）复杂度的算法快得多。并且希尔排序非常容易实现，算法代码短而简单。此外，希尔算法在最坏的情况下和平均情况下执行效率相差不是很多，与此同时快速排序在最坏的情况下执行的效率会非常差。专家门提倡，几乎任何排序工作在开始时都可以用希尔排序，若在实际使用中证明它不够快，再改成快速排序这样更高级的排序算法. 本质上讲，希尔排序算法的一种改进，减少了其复制的次数，速度要快很多。原因是，当N值很大时数据项每一趟排序需要的个数很少，但数据项的距离很长。当N值减小时每一趟需要和动的数据增多，此

12、时已经接近于它们排序后的最终位置。正是这两种情况的结合才使希尔排序效率比插入排序高很多。在直接插入排序算法中，每次插入一个数，使有序序列只增加1个节点，并且对插入下一个数没有提供任何帮助。如果比较相隔较远距离（称为增量）的数，使得数移动时能跨过多个元素，则进行一次比较就可能消除多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现了这一思想。算法先将要排序的一组数按某个增量d分成若干组，每组中记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分成一组，排序完成。下面的函数是一个希尔排序算法的一个实现，初次取序列的一半为增量，以后每次减半，直到增量为1。希尔排序是不稳定的。算法实现：#include void main()int array = 1,445,754,77,35,123,754,876,54,3;int len