C的数据结构八种排序算法的 代码及分析

1、二、选择排序初始状态：无序区为R1.n，有序区为空。第1趟排序在无序区R1.n中选出关键字最小的记录Rk，将它与无序区的第1个记录R1交换，使R1.1和R2.n分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。第i趟排序第i趟排序开始时，当前有序区和无序区分别为R1.i-1和Ri.n(1in-1)。该趟排序从当前无序区中选出关键字最小的记录Rk，将它与无序区的第1个记录Ri交换，使R1.i和Ri+1.n分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区.这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。优点：稳定，比较次数与冒泡排序一样；缺点：

2、相对之下还是慢。初始关键字 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 <iostream>using

3、 namespace std;void main()int i,j,k,t;int R8=49,38,65,97,76,13,27,49;for(i=0;i<7;i+)k=i;for(j=i+1;j<8;j+) if(Rj<Rk)k=j; if(k!=i) t=Ri;Ri=Rk;Rk=t; for(i=0;i<8;i+)cout<<Ri<<endl; 一、冒泡排序（小者上扬原则）已知一组无序数据a1、a2、an，需将其按升序排列。首先比较a1与a2的值，若a1大于a2则交换两者的值，否则不变。再比较a2与a3的值，若a2大于a3则交换两者的值，否

4、则不变。再#include <stdio.h> #include <stdlib.h> int main(void) int data10 = 73, 22, 93, 43, 55, 14, 28, 65, 39, 81; int temp1010 = ; int order10 = ; int i, j, k, n, lsd; k = 0; n = 1; printf("/n排序前: "); for(i = 0; i < 10; i+) printf("%d ", data); putchar('/n');

5、 while(n <= 10) for(i = 0; i < 10; i+) lsd = (data / n) % 10); templsdorderlsd = data; orderlsd+; printf("/n重新排列: "); for(i = 0; i < 10; i+) if(order != 0) for(j = 0; j < order; j+) datak = tempj; printf("%d ", datak); k+; order = 0; n *= 10; k = 0; putchar('/n

6、9;); printf("/n排序后: "); for(i = 0; i < 10; i+) printf("%d ", data); return 0; #include <stdio.h> #include <stdlib.h> int main(void) int data10 = 73, 22, 93, 43, 55, 14, 28, 65, 39, 81; int temp1010 = ; int order10 = ; int i, j, k, n, lsd; k = 0; n = 1; printf("

7、;/n排序前: "); for(i = 0; i < 10; i+) printf("%d ", data); putchar('/n'); while(n <= 10) for(i = 0; i < 10; i+) lsd = (data / n) % 10); templsdorderlsd = data; orderlsd+; printf("/n重新排列: "); for(i = 0; i < 10; i+) if(order != 0) for(j = 0; j < order; j+)

8、datak = tempj; printf("%d ", datak); k+; order = 0; n *= 10; k = 0; putchar('/n'); printf("/n排序后: "); for(i = 0; i < 10; i+) printf("%d ", data); return 0; #include <stdio.h> #include <stdlib.h> int main(void) int data10 = 73, 22, 93, 43, 55, 14,

9、28, 65, 39, 81; int temp1010 = ; int order10 = ; int i, j, k, n, lsd; k = 0; n = 1; printf("/n排序前: "); for(i = 0; i < 10; i+) printf("%d ", data); putchar('/n'); while(n <= 10) for(i = 0; i < 10; i+) lsd = (data / n) % 10); templsdorderlsd = data; orderlsd+; prin

10、tf("/n重新排列: "); for(i = 0; i < 10; i+) if(order != 0) for(j = 0; j < order; j+) datak = tempj; printf("%d ", datak); k+; order = 0; n *= 10; k = 0; putchar('/n'); printf("/n排序后: "); for(i = 0; i < 10; i+) printf("%d ", data); return 0; #includ

11、e <stdio.h> #include <stdlib.h> int main(void) int data10 = 73, 22, 93, 43, 55, 14, 28, 65, 39, 81; int temp1010 = ; int order10 = ; int i, j, k, n, lsd; k = 0; n = 1; printf("/n排序前: "); for(i = 0; i < 10; i+) printf("%d ", data); putchar('/n'); while(n <

12、;= 10) for(i = 0; i < 10; i+) lsd = (data / n) % 10); templsdorderlsd = data; orderlsd+; printf("/n重新排列: "); for(i = 0; i < 10; i+) if(order != 0) for(j = 0; j < order; j+) datak = tempj; printf("%d ", datak); k+; order = 0; n *= 10; k = 0; putchar('/n'); printf(

13、"/n排序后: "); for(i = 0; i < 10; i+) printf("%d ", data); return 0; 比较a3与a4，以此类推，最后比较an-1与an的值。这样处理一轮后，an的值一定是这组数据中最大的。再对a1an-1以相同方法处理一轮，则an-1的值一定是a1an-1中最大的。再对a1an-2以相同方法处理一轮，以此类推。共处理n-1轮后a1、a2、an就以升序排列了。优点：稳定，比较次数已知；缺点：慢，每次只能移动相邻两个数据，移动数据的次数多。初始关键字 49 38 65 97 76 13 27 49第一趟排序

14、后 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 2738 49 49 65 76 97第七趟排序后 13 27 38 49 49 65 76 97最后排序结果 13 27 38 49 49 76 76 97#include <iostream>using namespace std;void main() int i,j,

15、k;int a8=49,38,65,97,76,13,27,49;for(i=7;i>=0;i-)for(j=0;j<i;j+)if(aj>aj+1)k=aj;aj=aj+1;aj+1=k; for(i=0;i<8;i+)cout<<ai<<endl; 三、插入排序已知一组，一组无序数据b1、b2、bm，需将其变成一个升序数列。先创建一个变量a。首先将不b1与b2,如果b1大于b2则交换位置，否则不变；再比较b2与b3，如果b3小于b2，则将b3赋值给a，再将a与b1比较，如果a小于b1；则将b2，b1依次后移；在将a放在b1处以此类推，直到排序

16、结束。初始关键字 49 3865 97 76 13 27 59a b1 b2 b3 b4 b5 b6 b7 b81-49 49 > 38 65 97 76 13 27 5938 49 49 .38 38 49 .2-38 38 49 < 65 97 76 13 27 593-38 38 49 65 <97 76 13 27 594-38 38 49 65 97> 76 13 27 5976 38 49 65 97 97.76 38 49 65 76 97.以此类推void insertSort(Type* arr,long len)long i=0,j=0;for(i=

17、1;i<len;i+)j=i;tmpData=arrj;/tmpData用来储存数据while(tmpData<arrj-1&&j>0)arrj=arrj-1;j-;arrj=tmpData;五、快速排序（确定初值，两边推进，移动条件：ai>=temp && aj<=temp）快速排序是冒泡排序的改进版，是目前已知的最快的排序方法。已知一组无序数据a1、a2、an，需将其按升序排列。首先任取数据ax作为基准。比较ax与其它数据并排序，使ax排在数据的第k位，并且使a1ak-1中的每一个数据<ax，ak+1an中的每一个数据&g

18、t;ax，然后采用分治的策略分别对a1ak-1和ak+1an两组数据进行快速排序。优点：极快，数据移动少；缺点：不稳定。分段插入排序void QuickSort(int *pData, int left, intright)int i, j;int middle,iTemp;i = left;j = right;middle =pData(left + right) / 2; /求中间值dowhile(pDatai < middle) && (i < right) /从左扫描大于中值的数i+;while(pDataj > middle) &&

19、(j > left) /从右扫描小于中值的数j-;if (i <=j) /找到了一对值/交换iTemp =pDatai;pDatai =pDataj;pDataj =iTemp;i+;j-; while (i<= j) ; /如果两边扫描的下标交错，就停止（完成一次）/当左边部分有值(left<j)，递归左半边if(left<j)QuickSort(pData,left,j); /当右边部分有值(right>i)，递归右半边if(right>i)QuickSort(pData,i,right); 四、缩小增量排序(希尔排序)由希尔在1959年提出，又称

20、希尔排序。已知一组无序数据a1、a2、an，需将其按升序排列。发现当n不大时，插入排序的效果很好。首先取一增量d(d<n)，将a1、a1+d、a1+2d列为第一组，a2、a2+d、a2+2d列为第二组，ad、a2d、a3d列为最后一组以次类推，在各组内用插入排序，然后取d'<d，重复上述操作，直到d=1。增量d(1, 3, 7,15, 31, , 2k-1)是使用最广泛的增量序列之一.优点：快，数据移动少；缺点：不稳定，d的取值是多少，应取多少个不同的值，都无法确切知道，只能凭经验来取。初始：d5 49 38 65 97 76 13 27 49 55 44 一趟结果13 2

21、7 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 <iostream>using namespace std; #define MAX 16 void shell_sort(int *x, int n) inth, j, k, t; for(h=n/2;h>0; h=h/2) /*控制增量*/ for(j=h; j<n; j+) /*这个实际上就是上面的直接插入排序*/ t= *(x+

22、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, aMAX; p= a; cout<<"InputMAX number for sorting :"<<endl;for(i=0; i<MAX; i+) cin>>*p+;p=a;shell_sort(p,MAX);for(p=a, i=0; i<MAX; i+) cout<<*p+<<endl

23、;cout<<endl;六、归并排序算法 合并排序（MERGESORT）是又一类不同的排序方法，合并的含义就是将两个或两个以上的有序数据序列合并成一个新的有序数据序列，因此它又叫归并算法。它的基本思想就是假设数组A有N个元素，那么可以看成数组A是又N个有序的子序列组成，每个子序列的长度为1，然后再两两合并，得到了一个 N/2 个长度为2或1的有序子序列，再两两合并，如此重复，值得得到一个长度为N的有序数据序列为止，这种排序方法称为2路合并排序。 例如数组A有7个数据，分别是： 49 38 65 97 76 13 27，那么采用归并排序算法的操作过程如图7所示： 初始值 49 38

24、65 97 76 13 27 第一次合并之后38 49 65 97 13 76 27 第二次合并之后38 49 65 97 13 27 76 第三次合并之后13 27 38 49 65 76 97 合并算法的核心操作就是将一维数组中前后相邻的两个两个有序序列合并成一个有序序列。合并算法也可以采用递归算法来实现，形式上较为简单,但实用性很差。合并算法的合并次数是一个非常重要的量,根据计算当数组中有3到4个元素时,合并次数是2次,当有5到8个元素时,合并次数是3次,当有9到16个元素时,合并次数是4次，按照这一规律,当有N个子序列时可以推断出合并的次数是X(2 >=N,符合此条件的最小那个X

25、)。其时间复杂度为：O(nlogn).所需辅助存储空间为：O(n)归并排序： #include <stdio.h> void merge(int a,int p,int q,int r) int n1=q-p+1,n2=r-q,i,j,k; int l1002,R1002; for (i=1;i<=n1;i+)li=ap+i-1; for (j=1;j<=n2;j+)Rj=aq+j; Rn2+1=ln1+1=999999; i=j=1; for (k=p;k<=r;k+) if (li<=Rj) ak=li; i+; else ak=Rj; j+; void

26、 mergesort(int a,int p,int r) int q; if (p<r) q=(p+r)/2; mergesort(a,p,q); mergesort(a,q+1,r); merge(a,p,q,r); int main() int a1001,t,n,i; scanf("%d",&t); while (t-) scanf("%d",&n); for(i=1;i<=n;i+)scanf("%d",&ai); mergesort(a,1,n); for (i=1;i<=n;i+

27、) printf("%d",ai); if (i!=n)printf(" "); printf("/n"); return 0; 七、 堆排序根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆。 根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大根堆。n个关键字序列Kl，K2，Kn称为堆，当且仅当该序列满足如下性质(简称为堆性质)： (1) kiK2i且kiK2i+1 或(2)KiK2i且kiK2i+1(1i <!-if !vml-><!-endif->)堆排序利用了大根堆(或

28、小根堆)堆顶记录的关键字最大(或最小)这一特征，使得在当前无序区中选取最大(或最小)关键字的记录变得简单。（1）用大根堆排序的基本思想 先将初始文件R1.n建成一个大根堆，此堆为初始的无序区 再将关键字最大的记录R1(即堆顶)和无序区的最后一个记录Rn交换，由此得到新的无序区R1.n-1和有序区Rn，且满足R1.n-1.keysRn.key 由于交换后新的根R1可能违反堆性质，故应将当前无序区R1.n-1调整为堆。然后再次将R1.n-1中关键字最大的记录R1和该区间的最后一个记录Rn-1交换，由此得到新的无序区R1.n-2和有序区Rn-1.n，且仍满足关系R1.n-2.keysRn-1.n.k

29、eys，同样要将R1.n-2调整为堆。直到无序区只有一个元素为止。（2）大根堆排序算法的基本操作： 初始化操作：将R1.n构造为初始堆； 每一趟排序的基本操作：将当前无序区的堆顶记录R1和该区间的最后一个记录交换，然后将新的无序区调整为堆(亦称重建堆)。注意：只需做n-1趟排序，选出较大的n-1个关键字即可以使得文件递增有序。用小根堆排序与利用大根堆类似，只不过其排序结果是递减有序的。堆排序和直接选择排序相反：在任何时刻，堆排序中无序区总是在有序区之前，且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止。3.具体算法template<class T>heapsort(T r,i

30、nt n) /n为文件的实际记录数，r0没有使用int i,m;node x;for(i=/2;i>=1;i-)heappass(r,i,n); /初建堆/以下for语句为输出堆顶元素、调整堆操作for(m=n-1;m>=1;m-)/逻辑堆尾下标m不断变小 cout<<r1.key<<" "x=r1;r1=rm+1;rm+1=x; /堆顶与堆尾元素对换heappass(r,1,m);/恢复堆cout<<r1.key<<endl;/heapsort4.直接选择排序中，为了从R1.n中选出关键字最小的记录，必须进行n-

31、1次比较，然后在R2.n中选出关键字最小的记录，又需要做n-2次比较。事实上，后面的n-2次比较中，有许多比较可能在前面的n-1次比较中已经做过，但由于前一趟排序时未保留这些比较结果，所以后一趟排序时又重复执行了这些比较操作.堆排序可通过树形结构保存部分比较结果，可减少比较次数。八、基数排序 基数排序的基本思想是：从低位到高位依次对Kj(j=d-1，d-2，0)进行箱排序。在d趟箱排序中，所需的箱子数就是基数rd，这就是"基数排序"名称的由来。假设原来有一串数值如下所示： 73, 22, 93, 43, 55, 14, 28, 65, 39, 81 首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中： 0 1 81 2 22 3 73 93 43 4 14 5 55 65 6 7 8 28 9