《C的数据结构八种排序算法的 代码及分析.docx》由会员分享，可在线阅读，更多相关《C的数据结构八种排序算法的 代码及分析.docx（13页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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 using namespace std;v
3、oid main()int i,j,k,t;int R8=49,38,65,97,76,13,27,49;for(i=0;i7;i+)k=i;for(j=i+1;j8;j+) if(RjRk)k=j; if(k!=i) t=Ri;Ri=Rk;Rk=t; for(i=0;i8;i+)coutRiendl; 一、冒泡排序（小者上扬原则）已知一组无序数据a1、a2、an，需将其按升序排列。首先比较a1与a2的值，若a1大于a2则交换两者的值，否则不变。再比较a2与a3的值，若a2大于a3则交换两者的值，否则不变。再#include #include int main(void) int data10
4、 = 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 = 10) for(i = 0; i 10; i+) lsd = (data / n) % 10); templsdorderlsd = data; orderlsd+; printf(/n重新排列: ); for(i =
5、 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; #include #include int main(void) int data10 = 73, 22, 93, 43, 55, 14, 28, 65, 39, 81; int temp1010 =
6、; 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+; printf(/n重新排列: ); for(i = 0; i 10; i+) if(order != 0) for(j = 0; j order; j+) datak
7、 = 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 #include 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; print
8、f(/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+) datak = tempj; printf(%d , datak); k+; order = 0; n *= 10; k =
9、0; putchar(/n); printf(/n排序后: ); for(i = 0; i 10; i+) printf(%d , data); return 0; #include #include 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); putcha
10、r(/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+) datak = tempj; printf(%d , datak); k+; order = 0; n *= 10; k = 0; putchar(/n); printf(/n排序后: ); for(i = 0; i 10; i+) prin
11、tf(%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第一趟排序后 38 49 65 76 13 27 49 97第二趟排序后 38 49 65 13 27 49 76 97第三趟排序后 38
12、 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 using namespace std;void main() int i,j,k;int a8=49,38,65,97,76,13,27,49;for(i=7;i=0;i-)for(j=0;jaj+1)k=aj;aj=aj+1;aj+1=
13、k; for(i=0;i8;i+)coutai 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 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=1;ilen;i+)j=i;tmpData=arrj;/tmpData用来储存数据while(tmpData0)arrj=arrj-1;j-;arrj=tmpData;五、快速排
14、序（确定初值，两边推进，移动条件：ai=temp & aj=temp）快速排序是冒泡排序的改进版，是目前已知的最快的排序方法。已知一组无序数据a1、a2、an，需将其按升序排列。首先任取数据ax作为基准。比较ax与其它数据并排序，使ax排在数据的第k位，并且使a1ak-1中的每一个数据ax，然后采用分治的策略分别对a1ak-1和ak+1an两组数据进行快速排序。优点：极快，数据移动少；缺点：不稳定。分段插入排序void QuickSort(int *pData, int left, intright)int i, j;int middle,iTemp;i = left;j = right;mi
15、ddle =pData(left + right) / 2; /求中间值dowhile(pDatai middle) & (i middle) & (j left) /从右扫描小于中值的数j-;if (i =j) /找到了一对值/交换iTemp =pDatai;pDatai =pDataj;pDataj =iTemp;i+;j-; while (i= j) ; /如果两边扫描的下标交错，就停止（完成一次）/当左边部分有值(leftj)，递归左半边if(lefti)，递归右半边if(righti)QuickSort(pData,i,right); 四、缩小增量排序(希尔排序)由希尔在1959年提
16、出，又称希尔排序。已知一组无序数据a1、a2、an，需将其按升序排列。发现当n不大时，插入排序的效果很好。首先取一增量d(dn)，将a1、a1+d、a1+2d列为第一组，a2、a2+d、a2+2d列为第二组，ad、a2d、a3d列为最后一组以次类推，在各组内用插入排序，然后取dd，重复上述操作，直到d=1。增量d(1, 3, 7,15, 31, , 2k-1)是使用最广泛的增量序列之一.优点：快，数据移动少；缺点：不稳定，d的取值是多少，应取多少个不同的值，都无法确切知道，只能凭经验来取。初始：d5 49 38 65 97 76 13 27 49 55 44 一趟结果13 27 49 55 4
17、4 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 using namespace std; #define MAX 16 void shell_sort(int *x, int n) inth, j, k, t; for(h=n/2;h0; h=h/2) /*控制增量*/ for(j=h; j=0 & t*(x+k); k-=h) *(x+k+h)= *(x+k); *(x+k+h)= t; void main() int*p
18、, i, aMAX; p= a; coutInputMAX number for sorting :endl;for(i=0; i*p+;p=a;shell_sort(p,MAX);for(p=a, i=0; iMAX; i+) cout*p+endl;cout=N,符合此条件的最小那个X)。其时间复杂度为：O(nlogn).所需辅助存储空间为：O(n)归并排序： #include 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;
19、 for (j=1;j=n2;j+)Rj=aq+j; Rn2+1=ln1+1=; i=j=1; for (k=p;k=r;k+) if (li=Rj) ak=li; i+; else ak=Rj; j+; void mergesort(int a,int p,int r) int q; if (pr) 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+)s
20、canf(%d,&ai); mergesort(a,1,n); for (i=1;i=n;i+) printf(%d,ai); if (i!=n)printf( ); printf(/n); return 0; 七、 堆排序根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆。 根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大根堆。n个关键字序列Kl，K2，Kn称为堆，当且仅当该序列满足如下性质(简称为堆性质)： (1) kiK2i且kiK2i+1 或(2)KiK2i且kiK2i+1(1i )堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征
21、，使得在当前无序区中选取最大(或最小)关键字的记录变得简单。（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.keys，同样要将R1.n-2调整为堆。直到无序
22、区只有一个元素为止。（2）大根堆排序算法的基本操作： 初始化操作：将R1.n构造为初始堆； 每一趟排序的基本操作：将当前无序区的堆顶记录R1和该区间的最后一个记录交换，然后将新的无序区调整为堆(亦称重建堆)。注意：只需做n-1趟排序，选出较大的n-1个关键字即可以使得文件递增有序。用小根堆排序与利用大根堆类似，只不过其排序结果是递减有序的。堆排序和直接选择排序相反：在任何时刻，堆排序中无序区总是在有序区之前，且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止。3.具体算法templateheapsort(T r,int n) /n为文件的实际记录数，r0没有使用int i,m;node x
23、;for(i=/2;i=1;i-)heappass(r,i,n); /初建堆/以下for语句为输出堆顶元素、调整堆操作for(m=n-1;m=1;m-)/逻辑堆尾下标m不断变小 coutr1.key ;x=r1;r1=rm+1;rm+1=x; /堆顶与堆尾元素对换heappass(r,1,m);/恢复堆coutr1.keyendl;/heapsort4.直接选择排序中，为了从R1.n中选出关键字最小的记录，必须进行n-1次比较，然后在R2.n中选出关键字最小的记录，又需要做n-2次比较。事实上，后面的n-2次比较中，有许多比较可能在前面的n-1次比较中已经做过，但由于前一趟排序时未保留这些比较
24、结果，所以后一趟排序时又重复执行了这些比较操作.堆排序可通过树形结构保存部分比较结果，可减少比较次数。八、基数排序 基数排序的基本思想是：从低位到高位依次对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 39 接下来将这些桶子中的数值重新串接起来，成为以下的数列： 8
25、1, 22, 73, 93, 43, 14, 55, 65, 28, 39 接着再进行一次分配，这次是根据十位数来分配： 0 1 14 2 22 28 3 39 4 43 5 55 6 65 7 73 8 81 9 93 接下来将这些桶子中的数值重新串接起来，成为以下的数列： 14, 22, 28, 39, 43, 55, 65, 73, 81, 93 这时候整个数列已经排序完毕；如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。 LSD的基数排序适用于位数小的数列，如果位数多的话，使用MSD的效率会比较好，MSD的方式恰与LSD相反，是由高位数为基底开始进行分配，其他的演算方
26、式则都相同。 * C #include #include 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 = 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(/n排序后: ); for(i = 0; i 10; i+) printf(%d , data); return 0;