八大内部排序如下：

　　插入排序：直接插入排序、希尔排序

　　选择排序：简单选择排序、堆排序

　　交换排序：冒泡排序、快速排序

　　归并排序

　　基数排序

不同条件下，排序方法的选择

　　(1)若n较小(如n≤50)，可采用直接插入或直接选择排序。

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

　　(2)若文件初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序为宜；

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

　　快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；

　　堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。

　　若要求排序稳定，则可选用归并排序。但本章介绍的从单个记录起进行两两归并的  排序算法并不值得提倡，通常可以将它和直接插入排序结合在一起使用。先利用直接插入排序求得较长的有序子文件，然后再两两归并之。因为直接插入排序是稳定 的，所以改进后的归并排序仍是稳定的。

排序算法的稳定性

　　1） 稳定的：如果存在多个具有相同排序码的记录，经过排序后，这些记录的相对次序仍然保持不变，则这种排序算法称为稳定的。

　　插入排序、冒泡排序、归并排序、分配排序（桶式、基数）都是稳定的排序算法。

　　2）不稳定的：否则称为不稳定的。

　　直接选择排序、堆排序、希尔排序、快速排序都是不稳定的排序算法。

课后习题

【2019年真题】选择一个排序算法时，除算法的时空效率外，下列因素中，还需要考虑的是

I.数据的规模     Ⅱ.数据的存储方式 Ⅲ.算法的稳定性    V.数据的初始状态

A. 仅Ⅲ          B. 仅I、Ⅱ C. 仅Ⅱ、Ⅲ、IV    D. I、Ⅱ、Ⅲ、Ⅳ

参考答案：D

【2016年真题】对10TB的数据文件进行排序，应使用的方法是（）

1. 希尔排序
2. 堆排序
3. 快速排序
4. 归并排序

参考答案：D

【2016年真题】已知由n（n>=2）个正整数构成的集合A={a_k，0<=k<n}，将其划分为两个不相交的子集A₁和A₂，元素个数分别是n₁和n₂,，A₁和A₂中元素之和分别为S₁和S₂。设计一个尽可能高效的划分算法，满足|n₁-n₂|最小且|s₁-s₂|最大。要求：

1. 给出算法的基本设计思想。
2. 根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
3. 说明你所设计算法的平均时间复杂度和空间复杂度。

参考答案：

1. 算法的基本设计思想

由题意知，将最小的⌊n/2⌋个元素放在A₁中，其余的元素放在A₂中，分组结果即可满足题目要求。仿照快速排序的思想，基于枢轴将n个整数划分为两个子集。根据划分后枢轴所处的位置i分别处理：

1. 若i=⌊n/2⌋，则分组完成，算法结束；
2. 若i<⌊n/2⌋，则枢轴及之前的所有元素均属于A1，继续对i之后的元素进行划分；
3. 若i>⌊n/2⌋，则枢轴及之后的所有元素均属于A2，继续对i之前的元素进行划分；

基于该设计思想实现的算法，无需对全部元素进行排序，其平均时间复杂度是O(n)，空间复杂度是O(1)。

2. 算法实现

int setPartition(int a[], int n) {  
    int pivotkey,low=0,low0=0,high=n-1;  
    int high0=n-1,flag=1,k=n/2,i;  
    int s1=0,s2=0;  
    while (flag) {  
        pivotkey=a[low]; //选择枢轴  
        while (low < high) {//基于枢轴对数据进行划分  
            while (low < high && a[high] >= pivotkey)  
                --high;  
            if (low!=high) a[low]=a[high];  
            while (low<high && a[low]<=pivotkey)  
                ++low;  
            if (low!=high)a[high]=a[low];  
        }  
        a[low]=pivotkey;  
        if (low==k-1) //如果枢轴是第n/2小元素，划分成功  
            flag = 0;  
        else { //否则继续划分  
            if (low<k-1) {  
                low0=++low;  
                high=high0;  
            }  
            else {  
                high0=--high;  
                low=low0;  
            }  
        }  
    }  
    for (i = 0; i < k; i++) s1+=a[i];  
    for (i = k; k < n; i++) s2+=a[i];  
    return s2 - s1;  
}  

 

3. 算法的平均时间复杂度和空间复杂度

该算法的平均时间复杂度为O(n)，空间复杂度为O(1)。

【2013年真题】已知一个整数序列A=(a₀,a₁,...,a_n-1)， 其中0<=a_i<n(0<=i<n) 。若存在a_p1=a_p2=...=a_pm=x且m>n/2(0<=p_k<n,1<=k<=m)，则称x为A的主元素。例如A=( 0， 5，5，3，5，7，5，5 )，侧 5 为主元素；又如 A= ( 0，5，5，3，5，1，5，7 )，则 A 中没有主元素。假设 A 中的 n 个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出 A 的主元素。若存在主元素，则输出该元素；否则输出-1。要求：

（1）给出算法的基本设计思想。

（2）根据设计思想，采用 C 或 C++或 Java 语言描述算法，关键之处给出注释。

（3）说明你所设计算法的时间复杂度和空间复杂度。

参考答案：

（1）给出算法的基本设计思想：

算法的策略是从前向后扫描数组元素，标记出一个可能成为主元素的元素 Num。然 后重新计数，确认 Num 是否是主元素。

算法可分为以下两步：

① 选取候选的主元素：依次扫描所给数组中的每个整数，将第一个遇到的整数 Num 保存到 c 中，记录 Num 的出现次数为 1；若遇到的下一个整数仍等于 Num，则计数加 1， 否则计数减 1；当计数减到 0 时，将遇到的下一个整数保存到 c 中，计数重新记为 1， 开始新一轮计数，即从当前位置开始重复上述过程，直到扫描完全部数组元素。

② 判断 c 中元素是否是真正的主元素：再次扫描该数组，统计 c 中元素出现的次数，若大于 n/2，则为主元素；否则，序列中不存在主元素。

（2）算法实现：

int Majority (int A[ ], int n ) {  
    int i, c, count=1; // c 用来保存候选主元素，count 用来计数  
    c = A[0]; // 设置 A[0]为候选主元素  
    for (i=1; i<n; i++) // 查找候选主元素  
        if (A[i] = = c)  
            count++; // 对 A 中的候选主元素计数  
        else if (count > 0) // 处理不是候选主元素的情况  
            count--;  
        else // 更换候选主元素，重新计数  
        {  
            c = A[i];  
            count = 1;  
        }  
    if (count > 0)  
        for (i=count=0; i<n; i++) // 统计候选主元素的实际出现次数  
            if ( A[i] = = c )  
                count++;  
    if (count> n/2) return c; // 确认候选主元素  
    else return -1; // 不存在主元素  
}  

（3）说明算法复杂性：

参考答案中实现的程序的时间复杂度为 O（n），空间复杂度为 O（1）。