数据结构课程设计排序算法总结

排序算法：

(1) 直接插入排序 (2) 折半插入排序(3) 冒泡排序 (4) 简单选择排序 (5) 快速排序 (6) 堆排序 (7) 归并排序

【算法分析】

（1）直接插入排序；它是一种最简单的排序方法，它的基本操作是将一个记录插入到已排好的序的有序表中，从而得到一个新的、记录数增加1的有序表。

（2）折半插入排序：插入排序的基本操作是在一个有序表中进行查找和插入，我们知道这个查找操作可以利用折半查找来实现，由此进行的插入排序称之为折半插入排序。折半插入排序所需附加存储空间和直接插入相同，从时间上比较，折半插入排序仅减少了关键字间的比较次数，而记录的移动次数不变。

（3）冒泡排序：比较相邻关键字，若为逆序（非递增），则交换，最终将最大的记录放到最后一个记录的位置上，此为第一趟冒泡排序；对前n-1记录重复上操作，确定倒数第二个位置记录；??以此类推，直至的到一个递增的表。

(4) 简单选择排序：通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i（1<=i<=n）个记录交换之。

(5) 快速排序:它是对冒泡排序的一种改进，基本思想是，通过一趟排序将待排序的记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。 (6) 堆排序: 使记录序列按关键字非递减有序排列，在堆排序的算法中先建一个“大顶堆”，即先选得一个关键字为最大的记录并与序列中最后一个记录交换，然后对序列中前n-1记录进行筛选，重新将它调整为一个“大顶堆”，如此反复直至排序结束。 (7) 归并排序:归并的含义是将两个或两个以上的有序表组合成一个新的有序表。假设初始序列含有n个记录，则可看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2或1的有序子序列；再两两归并，??，如此重复，直至得到一个长度为n的有序序列为止，这种排序称为2-路归并排序。

【算法实现】

（1）直接插入排序：

void InsertSort(SqList &L){ for(i=2;i<=L.length ;i++) if(L.elem[i]

L.elem[0]=L.elem [i]; //复制为哨兵 L.elem [i]=L.elem [i-1]; for(j=i-2;L.elem [j]>L.elem[0];j--) }

L.elem [j+1]=L.elem [j]; L.elem [j+1]=L.elem[0];

（2）折半插入排序：

void BInsertSort(SqList &L){ //对顺序表L作折半插入排序

for(i=2;i<=L.length ;i++){ L.elem[0]=L.elem [i]; low=1; high=i-1; }

（3）冒泡排序：

void BubbleSort(SqList &L){ for(i=L.length;i>=2;i--) for(j=1;j

(4) 简单选择排序：

void SelectSort(SqList &L){

for(int i=1;i<=L.length-1 ;i++){

j=SelectMinKey(L,i); //在L.elem[i..L.length]中选择最小记录 if(i!=j) L.elem [i]?L.elem [index];

if(L.elem[j]>L.elem [j+1]) L.elem [j]?L.elem [j+1];

}

while(low<=high){ m=(low+high)/2; }

for(j=i-1;j>=high+1;j--)

L.elem [j+1]=L.elem [j]; L.elem [high+1]=L.elem[0];

if(L.elem [0]>L.elem [m]) low=m+1; else high=m-1;

} }

(5) 快速排序:

int Partition(SqList &L,int low,int high){ //将L.elem[low...high]一分为二 pivot=L.elem[low]; while(low

while(low=pivot) high--;

L.elem[low] ?L.elem[high];

L.elem[low] ?L.elem[high];

}

return low; }

void QSort(SqList &L,int low,int high){

//对顺序表L中的子序列L.elem[low...high]进行快速排序 if(low

while(low

pivot=Partition(L,low,high); QSort(L,low,pivot-1); QSort(L,pivot+1,high); } }

void QuickSort(SqList &L) { //对顺序表L作快速排序

QSort(L,1,L.length); }

(6) 堆排序:

void HeapAdjust(SqList &L,int s,int m){

L.elem[0]=L.elem[s];

for(j=2*s;j<=m;j*=2){ if(j

if(!(L.elem[0]

s=j; }

L.elem[s]=L.elem[0];

}

void HeapSort(SqList &L){

for(i=L.length/2;i>0;i--)

HeapAdjust(L,i,L.length); for(i=L.length;i>1;i--){ LL.elem[1] ? L.elem[i]; }

(7) 归并排序:

void Merge(SqList L,SqList &L1,int i,int m,int n){ //将有序的L[i..m]和L[m+1..n]归并为有序的L1[i..n]

for(j=m+1,k=i;i<=m&&j<=n;++k) if(L.elem[i]

}

void MSort(SqList L,SqList &L1,int s,int t){ //将L[s..t]归并排序为L1[s..t]。 if(s==t) L1.elem[s]=L.elem[s];

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){ //对顺序表L作归并排序 MSort(L,L,1,L.length); }

【源代码】 见.cpp文件。 【算法分析】

算法 直接插入排序 折半插入排序 冒泡排序 简单选择排序 快速排序 堆排序 归并排序 时间复杂度 O(n*n) O(n*n) O(n*n) O(n*n) O(n*log2 n) O(n*log2 n) O(n*log2 n) 空间复杂度 O(1) O(1) O(1) O(1) O(O(log2 n))~O(n) O(1) O(1) 稳定性 稳定 较稳定 较稳定 较稳定 不稳定 不稳定 稳定 适用范围 n较小或待排记录基本有序 n较小 待排记录基本有序 n较小 n较大或待排记录基本有序 n较大 n较大，稳定性要求高 【总结】

简单排序中直接插入排序最好，快速排序最快，当文件为正序，直接插入排序和

冒泡排序均最佳。 排序算法的选择：

1. 若n（待排序的记录数）较小，可采用直接插入排序或选择排序。

当记录规模较小时，直接插入排序较好：否则因为选择移动的记录数少于直接插入，应选选择排序。

2. 若文件初始状态基本有序（正序），则应选用直接插入排序、冒泡排序或快速排序。

3. 若n较大，则应采用时间复杂度为O(nlgn)的排序算法：快速排序、堆排序极品归并排序。

当待排序的关键字是随机分布时，快速排序的平均时间最短；堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的；

若要求排序稳定，则可选用归并排序。