数据结构与算法第九章

排序算法稳定性：若元素\(i,j满足key_i=key_j,i<j\)，排序后\(i在j前面\),则称此排序算法稳定。

内排序，外排序：内排序指排序期间数据元素全部存放在内存的排序。

直接插入排序

第\(i-1\)趟：插入第\(i\)个元素时，前\(i-1\)个元素已排好序，将其排序码与前面元素的排序码从后往前顺次比较，进行插入，并移动已排序好的元素。

最好情况：每趟比较1次，移动0次。

最坏情况：比较次数与元素移动次数均为\(O(n^2)\)

是稳定排序算法。

折半插入排序

在插入\(V_i\)时，采取折半搜索寻找插入位置。能优化比较次数为\(O(n\log n)\)，但移动次数最差仍可达到\(O(n^2)\)

希尔排序

（1）选取\(Gap\)，将序列分为\(\displaystyle Gap\)组，每一组中包括\(a_i,a_{i+gap},\cdots,a_{i+j\cdot gap},i\in[1,gap],i+j\cdot gap\le n\)

（2）对组间元素进行插入排序。完成后\(Gap=Gap/2\)

（3）重复操作（2），直到当前操作完成且\(Gap=1\)

算法时间复杂度为\(O(n^{1.25})(n^{1.25}\sim 1.6n^{1.25})\)，不稳定排序算法。

快速排序

（1）任取待排序元素序列某元素为基准，按其排序码大小，将整个元素序列划分为左右两个子序列，左侧排序码小于等于基准元素排序码，右侧则大于

（2）基准元素应当排在其中间，即确定了最终安放位置

（3）对两个子序列重复进行（1）

快速排序算法时间复杂度取决于递归树高度

算法最优时间复杂度\(O(n\log n)\)，最差时间复杂度\(O(n^2)\)

选择排序

（1）在未排序元素中选出排序码最小的元素

（2）若不是此未排序元素序列的第一个，将二者交换，重复（1）

时间复杂度为\(O(n^2)\)

锦标赛排序

（1）将\(n\)个元素的排序码作为叶节点，两两比较得到父亲结点，最后将形成一共有\(2n-1\)个结点的完全二叉树，称此为胜者树。

（2）输出root

（3）再沿胜者路径到达叶结点，即此元素本身结点，将其清空（置为INF或-INF），再向上比较得到新胜者树，回到（2）

胜者树高度为\(\lceil \log_2n\rceil\)，构建胜者树：\(O(n)\)，更新胜者树与输出结果：\(O(n\log n)\)，总时间复杂度\(O(n\log n)\)

是稳定的排序算法，需要使用较多额外存储：\(O(n)\)

堆排序

（1）根据初始数据，利用堆调整算法siftdown形成初始堆

（2）输出堆顶，将堆顶元素与待排序元素最后一位进行交换，此时为堆中第\(n\)号元素

（3）再对前\(n-1\)个元素进行siftdown操作，回到（2）

需要升序排序则构建最大堆。

算法时间复杂度为\(O(n\log n)\)，空间复杂度为\(O(1)\)，是不稳定排序算法。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
template <class T>
void HeapSort (dataList<T>& L) 
{
//对表L.Vector[0]到L.Vector[n-1]进行排序, 使得表中各个元素按其排序码非递减有序
    int i, n = L.length();
    for (i = (n-2)/2; i >= 0; i--)//将表转换为堆
        siftDown (L, i, n-1);   
    for (i = n-1; i >= 0; i--)//对表排序
        L.Swap(0, i),siftDown (L, 0, i-1);
};
template <class T>
siftDown (dataList<T>& L, const int start, const int m)
{
//私有函数: 从结点start开始到m自上向下比较, 如果子女的值大于双亲的值, 则相互交换, 将一个集合局部调整为最大堆。
    int i = start;  
    int j = 2*i+1;//j是i的左子女
    Element<T> temp = L[i];//暂存子树根结点
    while (j <= m) 
    {//逐层比较
        if (j < m && L[j] < L[j+1]) j++;//让j指向两子女中的大者
        if (temp >= L[j]) break;//temp排序码大不调整
        else 
        {//否则子女中的大者上移
            L[i] = L[j];
            i = j;  
            j = 2*j+1;//i下降到子女位置
        }
    }
    L[i] = temp; //temp放到合适位置
};
排序方法 最好比较次数 最差比较次数 最好移动次数 最差移动次数 稳定性 最好附加存储 最差附加存储
直接插入排序 \(O(n)\) \(O(n^2)\) 0 \(O(n^2)\) Y 1 1
折半插入排序 \(O(n\log n)\) \(O(n\log n)\) 0 \(O(n^2)\) Y 1 1
冒泡排序 \(O(n)\) \(O(n^2)\) 0 \(O(n^2)\) Y 1 1
快速排序 \(O(n\log n)\) \(O(n^2)\) 小于\(O(n\log n)\) \(O(n^2)\) N \(O(n\log n)\) \(O(n)\)
简单选择排序 \(O(n^2)\) \(O(n^2)\) 0 \(O(n)\) N 1 1
锦标赛排序 \(O(n\log n)\) \(O(n\log n)\) \(O(n\log n)\) \(O(n\log n)\) Y \(O(n)\) \(O(n)\)
堆排序 \(O(n\log n)\) \(O(n\log n)\) \(O(n\log n)\) \(O(n\log n)\) N 1 1
归并排序 \(O(n\log n)\) \(O(n\log n)\) \(O(n\log n)\) \(O(n\log n)\) Y \(O(n)\) \(O(n)\)