2022年数据结构课程设计排序算法总结 .pdf

《2022年数据结构课程设计排序算法总结 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构课程设计排序算法总结 .pdf（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、排序算法：(1) 直接插入排序 (2) 折半插入排序(3) 冒泡排序 (4) 简单选择排序 (5) 快速排序(6) 堆排序 (7) 归并排序【算法分析】（1）直接插入排序；它是一种最简单的排序方法，它的基本操作是将一个记录插入到已排好的序的有序表中，从而得到一个新的、记录数增加1 的有序表。（2）折半插入排序：插入排序的基本操作是在一个有序表中进行查找和插入，我们知道这个查找操作可以利用折半查找来实现，由此进行的插入排序称之为折半插入排序。折半插入排序所需附加存储空间和直接插入相同，从时间上比较， 折半插入排序仅减少了关键字间的比较次数，而记录的移动次数不变。（3）冒泡排序 ：比较相邻关键字，

2、若为逆序（非递增），则交换，最终将最大的记录放到最后一个记录的位置上，此为第一趟冒泡排序；对前 n-1 记录重复上操作，确定倒数第二个位置记录； , 以此类推，直至的到一个递增的表。(4)简单选择排序：通过 n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i （1=i=n ）个记录交换之。(5)快速排序 : 它是对冒泡排序的一种改进，基本思想是， 通过一趟排序将待排序的记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。(6)堆排序 : 使记录序列按关键字非递减有序排列，在堆排序的算法中先建一

3、个“大顶堆”，即先选得一个关键字为最大的记录并与序列中最后一个记录交换，然后对序列中前n-1 记录进行筛选，重新将它调整为一个“大顶堆”，如此反复直至排序结束。(7)归并排序 : 归并的含义是将两个或两个以上的有序表组合成一个新的有序表。假设初始序列含有n 个记录， 则可看成是n 个有序的子序列，每个子序列的长度为1，然后两两归并，得到 n/2 个长度为 2 或 1 的有序子序列； 再两两归并， , ，如此重复， 直至得到一个长度为 n 的有序序列为止，这种排序称为2-路归并排序。【算法实现】（1）直接插入排序：void InsertSort(SqList &L) for(i=2;i=L.le

4、ngth ;i+) if(L.elemiL.elem0;j-) L.elem j+1=L.elem j; L.elem j+1=L.elem0; （2）折半插入排序：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 11 页 - - - - - - - - - void BInsertSort(SqList &L) / 对顺序表L 作折半插入排序for(i=2;i=L.length ;i+) L.elem0=L.elem i; low=1; high=i-1; while(

5、lowL.elem m) low=m+1; else high=m-1; for(j=i-1;j=high+1;j-) L.elem j+1=L.elem j; L.elem high+1=L.elem0; （3）冒泡排序：void BubbleSort(SqList &L) for(i=L.length;i=2;i-) for(j=1;jL.elem j+1) L.elem j? L.elem j+1; (4)简单选择排序：void SelectSort(SqList &L) for(int i=1;i=L.length-1 ;i+) j=SelectMinKey(L,i); /在 L.el

6、emi.L.length中选择最小记录if(i!=j) L.elem i? L.elem index; (5)快速排序: int Partition(SqList &L,int low,int high) / 将 L.elemlow.high一分为二pivot=L.elemlow; while(lowhigh) while(low=pivot) high-; L.elemlow? L.elemhigh; while(lowhigh&L.elemhigh=pivot) low+; L.elemlow? L.elemhigh; return low; void QSort(SqList &L,in

7、t low,int high) / 对顺序表L 中的子序列L.elemlow.high进行快速排序if(lowhigh) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 11 页 - - - - - - - - - pivot=Partition(L,low,high); QSort(L,low,pivot-1); QSort(L,pivot+1,high); void QuickSort(SqList &L) / 对顺序表L 作快速排序QSort(L,1,L.lengt

8、h); (6)堆排序: void HeapAdjust(SqList &L,int s,int m) L.elem0=L.elems; for(j=2*s;j=m;j*=2) if(jm&L.elemjL.elemj+1) j+; if(!(L.elem00;i-) HeapAdjust(L,i,L.length); for(i=L.length;i1;i-) LL.elem1? L.elemi; HeapAdjust(L,1,i-1); (7)归并排序: void Merge(SqList L,SqList &L1,int i,int m,int n) / 将有序的Li.m和 Lm+1.n归

9、并为有序的L1i.n for(j=m+1,k=i;i=m&j=n;+k) if(L.elemiL.elemj) L1.elemk=L.elemi+; else L1.elemk=L.elemj+; if(i=m) L1k.n =Li.m;if(j=n) L1k.n =Lj.n; void MSort(SqList L,SqList &L1,int s,int t) / 将 Ls.t归并排序为L1s.t。if(s=t) L1.elems=L.elems; else m=(s+t)/2; MSort(L,L2,s,m); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - -

10、 - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 11 页 - - - - - - - - - MSort(L,L2,m+1,t); Merge(L2,L1,s,m,t); void MergeSort(SqList &L) / 对顺序表L 作归并排序MSort(L,L,1,L.length); 【源代码】见.cpp 文件。【算法分析】算法时间复杂度空间复杂度稳定性适用范围直接插入排序O(n*n) O(1) 稳定n 较小或待排记录基本有序折半插入排序O(n*n) O(1) 较稳定n 较小冒泡排序O(n*n) O(1) 较稳定待排记录基本有序简单选择

11、排序O(n*n) O(1) 较稳定n 较小快速排序O(n*log2 n) O(O(log2 n)O(n) 不稳定n 较大或待排记录基本有序堆排序O(n*log2 n) O(1) 不稳定n 较大归并排序O(n*log2 n) O(1) 稳定n 较大，稳定性要求高【总结】简单排序中直接插入排序最好，快速排序最快， 当文件为正序， 直接插入排序和冒泡排序均最佳。排序算法的选择：1. 若 n（待排序的记录数）较小，可采用直接插入排序或选择排序。当记录规模较小时，直接插入排序较好：否则因为选择移动的记录数少于直接插入，应选选择排序。2. 若文件初始状态基本有序 （正序） ，则应选用直接插入排序、 冒泡排

12、序或快速排序。3. 若 n 较大，则应采用时间复杂度为O(nlgn)的排序算法： 快速排序、 堆排序极品归并排序。当待排序的关键字是随机分布时，快速排序的平均时间最短；堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的；若要求排序稳定，则可选用归并排序。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 11 页 - - - - - - - - - 源代码：#include #include typedef struct /顺序表

13、存储结构 int * elem; int length; SqList; int main(void) SqList L; SqList L1; void InsertSort(SqList &L); /直接插入排序 void BInsertSort(SqList &L); /折半插入排序 void BubbleSort(SqList &L); /冒泡排序 void SelectSort(SqList &L); /简单选择排序void QuickSort(SqList &L); /快速排序 void QSort(SqList &L,int low,int high); int Partitio

14、n(SqList &L,int low,int high); void HeapSort(SqList &L); /堆排序 void HeapAdjust(SqList &L,int s,int m); void MergeSort(SqList &L); /归并排序 void MSort(SqList L,SqList &L1,int s,int t); void Merge(SqList L,SqList &L1,int i,int m,int n); int n; int * p; printf(请输入顺序表的长度：); scanf(%d,&n); if(p=(int *)malloc(

15、n+1)*sizeof(int)=0) /动态分配顺序表存储空间 printf(Not able to allocate memory.n); exit(1); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 11 页 - - - - - - - - - L.elem=p; L.length=n; if(p=(int *)malloc(n+1)*sizeof(int)=0) /动态分配顺序表存储空间 printf(Not able to allocate memory.n

16、); exit(1); L1.elem=p; L1.length=n; printf(请输入 %d 个整数： n,n); /输入一组待排序的数据 for(int i=1;i=L.length;i+) scanf(%d,&L.elemi); printf(选择排序算法： n); printf(1 直接插入排序 n); printf(2 折半插入排序 n); printf(3 冒泡排序 n); printf(4 简单选择排序 n); printf(5 快速排序 n); printf(6 堆排序 n); printf(7 归并排序 n); int change=0; scanf(%d,&change

17、); switch(change) case 1: InsertSort(L);break; case 2: BInsertSort(L);break; case 3: BubbleSort(L);break; case 4: SelectSort(L);break; case 5: QuickSort(L);break; case 6: HeapSort(L);break; case 7: MergeSort(L);break; default:break; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - -

18、 - - - - - 第 6 页，共 11 页 - - - - - - - - - printf(排序后为： ); for(i=1;i=L.length;i+) printf(%6d,L.elemi); printf(n); return 0; void InsertSort(SqList &L) int i=0,j=0; for(i=2;i=L.length ;i+) if(L.elemiL.elem0;j-) L.elem j+1=L.elem j; L.elem j+1=L.elem0; void BInsertSort(SqList &L) int i=0,j=0,low=0,high

19、=0,m=0; for(i=2;i=L.length ;i+) L.elem0=L.elem i; low=1; high=i-1; while(lowL.elem m) low=m+1; else high=m-1; for(j=i-1;j=high+1;j-) L.elem j+1=L.elem j; L.elem high+1=L.elem0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 11 页 - - - - - - - - - void BubbleSor

20、t(SqList &L) int i=0,j=0; for(i=L.length;i=2;i-) for(j=1;jL.elem j+1) L.elem0=L.elem j; L.elem j=L.elem j+1; L.elem j+1=L.elem0; void SelectSort(SqList &L) int index=0; for(int i=1;i=L.length-1 ;i+) index=i; for(int j=i+1;j=L.length ;j+) if(L.elem jL.elem index) index=j; if(i!=index) L.elem0=L.elem

21、i; L.elem i=L.elem index; L.elem index=L.elem0; /快排int Partition(SqList &L,int low,int high) /将 L.elemlow.high一分为二 int pivot=0; /用子表第一个记录作枢轴 pivot=L.elemlow; while(lowhigh) while(low=pivot) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 11 页 - - - - - - - - - h

22、igh-; L.elem0=L.elemlow; L.elemlow=L.elemhigh; L.elemhigh=L.elem0; while(lowhigh&L.elemhigh=pivot) low+; L.elem0=L.elemlow; L.elemlow=L.elemhigh; L.elemhigh=L.elem0; return low; void QSort(SqList &L,int low,int high) /对顺序表 L 中的子序列 L.elemlow.high进行快速排序 int pivot=0; if(lowhigh) pivot=Partition(L,low,h

23、igh); QSort(L,low,pivot-1); QSort(L,pivot+1,high); void QuickSort(SqList &L) QSort(L,1,L.length); /堆排void HeapAdjust(SqList &L,int s,int m) int j=0; L.elem0=L.elems; for(j=2*s;j=m;j*=2) if(jm&L.elemjL.elemj+1) j+; if(!(L.elem00;i-) HeapAdjust(L,i,L.length); for(i=L.length;i1;i-) L.elem0=L.elem1; L.e

24、lem1=L.elemi; L.elemi=L.elem0; HeapAdjust(L,1,i-1); /归并void Merge(SqList L,SqList &L1,int i,int m,int n) int j=0,k=0,p=0,q=0; for(j=m+1,k=i;i=m&j=n;+k) if(L.elemiL.elemj) L1.elemk=L.elemi+; else L1.elemk=L.elemj+; if(i=m) for(p=k,q=i;q=m;p+,q+) L1.elemp=L.elemq; if(j=n) for(p=k,q=j;q=n;p+,q+) L1.ele

25、mp=L.elemq; void MSort(SqList L,SqList &L1,int s,int t) SqList L2; int * p; if(p=(int *)malloc(t-s+1)*sizeof(int)=0) /动态分配顺序表存储空间名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 11 页 - - - - - - - - - printf(Not able to allocate memory.n); exit(1); L2.elem=p; L2.length=t-s+1; int m=0; if(s=t) L1.elems=L.elems; else m=(s+t)/2; MSort(L,L2,s,m); MSort(L,L2,m+1,t); Merge(L2,L1,s,m,t); void MergeSort(SqList &L) MSort(L,L,1,L.length); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 11 页 - - - - - - - - -