数据结构（十）——排序

一、选择排序

1.简单选择排序

基本思想：假设排序表为[1,…,n]，第i趟排序即从[i,…,n]中选择关键字最小的元素与L[i]交换

eg：给定关键字序列{87，45，78，32，17，65，53，09}，用简单选择排序算法进行排序

代码实现：

void SelectSort(ElemType A[],int n){for(i=0;i<n-1;i++){min=i;for(j=i+1;j<n;j++){if(A[j]<A[min]){min=j;}}if(min!=i){swap(A[i],A[min]);}}
}

空间效率：O(1)

时间效率：O(n^2)

稳定性：稳定

2.堆排序

（1）构造大根堆

eg：下面的序列中，（）是堆

A.1,2,8,4,3,9,10,5    B.1,5,10,6,7,8,9,2    C.9,8,7,6,4,8,2,1    D.9,8,7,6,5,4,3,7

答案：A

（2）删除元素

输出栈顶元素后，将堆的最后一个元素与栈顶元素交换，此时堆的性质被破坏

（3）插入元素

对堆进行插入操作时，先将新结点放在堆的末端，再对这个新结点向上执行调整操作

空间效率：O(1)

时间效率：O(nlog2n)

稳定性：不稳定

eg：设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（B）方法可以达到目的

A.快速排序  B.堆排序  C.冒泡排序  D.希尔排序

二、归并排序

“归并”的含义是将两个或两个以上的有序表组合成一个新的有序表

2路归并排序：

空间效率：O(n)

时间效率：O(nlog2n)

稳定性：稳定

eg：一组记录值为（12，38，35，25，74，50，63，90），按2路归并排序方法对序列进行一趟归并后的结果是（12，38，25，35，50，74，63，90）

三、基数排序

基数排序不基于比较和移动进行排序，而是基于关键字各位的大小排序

个位：

十位：

百位：

空间效率：O(r)

时间效率：O(d(n+r))   d为趟数

稳定性：稳定

eg：如果将所有中国人按照生日（不考虑年份，只考虑月、日）来排序，那么使用下列排序算法中的（D）算法最快

A.归并排序  B.希尔排序  C.快速排序  D.基数排序

四、各种排序算法的比较

eg：在直接插入排序和快速排序中，若初始数据基本有序，则选用（直接插入排序）；在冒泡排序和堆排序中，若要求数据的稳定性，则选用（冒泡排序）

eg：以下四种排序方法中，需要附加的内存空间(空间复杂度)最大的是（D）

A.插入排序  B.选择排序  C.快速排序  D.归并排序

eg：一趟排序结束之后不一定能够选出一个元素放在其最终位置上的是（D）

A.简单选择排序  B.冒泡排序  C.快速排序  D.希尔排序

五、习题

 

答案：A

答案：√

答案：A

答案：A

答案：不是；7，18，21，41，58，63，29，43

答案：

第一趟：12，51，23，55，07，49，36，72，12'

第二趟：12，23，51，55，07，36，49，72，12'

第三趟：07，12，23，36，49，51，55，72，12'

第四趟：07，12，12'，23，36，49，51，55，72

答案：C

答案：快速排序；O(nlog2n)

答案：D