8种排序
一、冒泡排序（小者上扬原则）
已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。首先比较a[1]与a[2]的值，若a[1]大于a[2]则交换两者的值，否则不变。再比较a[2]与a[3]的值，若a[2]大于a[3]则交换两者的值，否则不变。再比较a[3]与a[4]，以此类推，最后比较a[n-1]与a[n]的值。这样处理一轮后，a[n]的值一定是这组数据中最大的。再对a[1]~a[n-1]以相同方法处理一轮，则a[n-1]的值一定是a[1]~a[n-1]中最大的。再对a[1]~a[n-2]以相同方法处理一轮，以此类推。共处理n-1轮后a[1]、a[2]、……a[n]就以升序排列了。
优点：稳定，比较次数已知；
缺点：慢，每次只能移动相邻两个数据，移动数据的次数多。
初始关键字 [49 38 65 97 76 13 27 49] 第一趟排序后 [38 49 65 76 13 27 49] 97 第二趟排序后 [38 49 65 13 27 49] 76 97 第三趟排序后 [38 49 13 27 49] 65 76 97 第四趟排序后 [38 13 27 49] 49 65 76 97 第五趟排序后 [38 13 27] 49 49 65 76 97 第六趟排序后 [13 27]38 49 49 65 76 97 第七趟排序后 [13] 27 38 49 49 65 76 97 最后排序结果 13 27 38 49 49 76 76 97 #include
int i,j,k;
int a[8]={49,38,65,97,76,13,27,49}; for(i=7;i>=0;i--) {
for(j=0;j if(a[j]>a[j+1]) { k=a[j]; a[j]=a[j+1]; a[j+1]=k; } } } for(i=0;i<8;i++) cout< } 二、选择排序 ①初始状态：无序区为R[1..n]，有序区为空。 ②第1趟排序 在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。 …… ③第i趟排序 第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R[i..n](1≤i≤n-1)。该趟排序从当前无序区中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[i]交换，使R[1..i]和R[i+1..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区.这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。 优点：稳定，比较次数与冒泡排序一样； 缺点：相对之下还是慢。 初始关键字 [49 3865 97 76 13 27 49] 第一趟排序后 13 ［38 65 97 76 49 27 49] 第二趟排序后 13 27 ［65 97 76 49 38 49] 第三趟排序后 13 2738 [97 76 49 65 49] 第四趟排序后 13 2738 49 [49 97 65 76] 第五趟排序后 13 2738 49 49 [97 97 76] 第六趟排序后 13 2738 49 49 76 [76 97] 第七趟排序后 13 2738 49 49 76 76 [ 97] 最后排序结果 13 2738 49 49 76 76 97 #include int i,j,k,t; int R[8]={49,38,65,97,76,13,27,49}; for(i=0;i<7;i++) { k=i; for(j=i+1;j<8;j++) if(R[j] t=R[i];R[i]=R[k];R[k]=t; } } for(i=0;i<8;i++) cout< 三、插入排序 已知一组，一组无序数据b[1]、b[2]、……b[m]，需将其变成一个升序数列。先创建一个变量a。首先将不b[1]与b[2],如果b[1]大于b[2]则交换位置，否则不变；再比较b[2]与b[3]，如果b[3]小于b[2]，则将b[3]赋值给a，再将a与b[1]比较，如果a小于b[1]；则将b[2]，b[1]依次后移；在将a放在b[1]处以此类推，直到排序结束。 初始关键字 [49 3865 97 76 13 27 59] a b[1] b[2] b[3] b[4] b[5] b[6] b[7] b[8] 1-----49 49 > 38 65 97 76 13 27 59 38 49 49 ………. 38 38 49 ………. 2-----38 38 49 < 65 97 76 13 27 59 3-----38 38 49 65 <97 76 13 27 59 4----38 38 49 65 97> 76 13 27 59 76 38 49 65 97 97…….. 76 38 49 65 76 97…….. 以此类推 void insertSort(Type* arr,long len) { long i=0,j=0; for(i=1;i tmpData=arr[j];//tmpData用来储存数据 while(tmpData0) { arr[j]=arr[j-1]; j--; } arr[j]=tmpData; } } 四、缩小增量排序(希尔排序) 由希尔在1959年提出，又称希尔排序。 已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。发现当n不大时，插入排序的效果很好。首先取一增量d(d 缺点：不稳定，d的取值是多少，应取多少个不同的值，都无法确切知道，只能凭经验来取。 初始：d＝5 49 38 65 97 76 13 27 49 55 44 一趟结果 13 27 49 55 44 49 38 65 97 76 d=3 |----------------------|----------------------|---------------------| 二趟结果 13 44 49 38 27 49 55 65 97 76 d=1 三趟结果 13 27 38 44 49 49 55 65 76 97 #include void shell_sort(int *x, int n) { inth, j, k, t; for(h=n/2;h>0; h=h/2) /*控制增量*/ { for(j=h; j t= *(x+j); for(k=j-h; (k>=0 && t<*(x+k)); k-=h) { *(x+k+h)= *(x+k); } *(x+k+h)= t; } } } void main() { int*p, i, a[MAX]; p= a; cout<<\for(i=0; i shell_sort(p,MAX); for(p=a, i=0; i cout<<*p++< cout< 五、快速排序（确定初值，两边推进，移动条件：a[i]>=temp && a[j]<=temp） 快速排序是冒泡排序的改进版，是目前已知的最快的排序方法。 已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。首先任取数据a[x]作为基准。比较a[x]与其它数据并排序，使a[x]排在数据的第k位，并且使a[1]~a[k-1]中的每一个数据a[x]，然后采用分治的策略分别对a[1]~a[k-1]和a[k+1]~a[n] 两组数据进行快速排序。 优点：极快，数据移动少； 缺点：不稳定。 分段插入排序 void QuickSort(int *pData, int left, intright) { int i, j; int middle,iTemp; i = left; j = right; middle =pData[(left + right) / 2]; //求中间值 do { while((pData[i] < middle) && (i < right)) //从左扫描大于中值的数 i++; while((pData[j] > middle) && (j > left)) //从右扫描小于中值的数 j--; if (i <=j) //找到了一对值 { //交换 iTemp =pData[i]; pData[i] =pData[j]; pData[j] =iTemp; i++; j--; } } while (i<= j) ; //如果两边扫描的下标交错，就停止（完成一次） //当左边部分有值(left QuickSort(pData,left,j); //当右边部分有值(right>i)，递归右半边 if(right>i) QuickSort(pData,i,right); } 六、归并排序算法 合并排序（MERGESORT）是又一类不同的排序方法，合并的含义就是将两个或两个以上的有序数据序列合并成一个新的有序数据序列，因此它又叫归并算法。它的基本思想就是假设数组A有N个元素，那么可以看成数组A是又N个有序的子序列组成，每个子序列的长度为1，然后再两两合并，得到了一个 N/2 个长度为2或1的有序子序列，再两两合并，如