排序(2)-复杂排序算法

引言

本章记录一些平均时间效率更高的排序算法，他们的时间复杂度通常为O(nlogn)级别，但其实现都比较复杂，所以通常称之为复杂排序算法。约定还是同上一章一样，效率对比也同样是在下一章给出。

归并排序

该算法正如其名，围绕着归与并两种策略进行。
归指的是递归，利用二分法将整个序列划分成左右两个子序列，再将左子序列又二分为左右子序列，将右子序列同样也二分为左右子序列，整个二分过程体现在代码上就是递归调用的过程；
并指的是合并，递归不能无限地进行下去，总是需要一个出口的，而显然二分的出口就在于当两个子序列均仅剩1个或0个元素时，即有low >= high条件成立时，此时将对这两个序列进行合并，又因两个子序列已然是有序序列，所以可以直接采用经典的两有序序列合并的算法实现，完成后便得到了一段更长的有序序列，并返回上一层，进而再与它同层的另一半有序序列进行合并，直至返回最外层算法结束。
可以看出，归并排序利用递归深入到最底层，通过解决最简单的两单个元素合并得到新有序序列这个子问题，再供给其上层使用该子问题得到的答案，逐步完成了最初始的复杂问题求解。但值得提出的是，归并排序需要一个与原始序列空间大小相同的空数组存放归并结果，故其空间复杂度为O(n)。代码如下：

// 归并排序
void mergeSort(int[] seq) {
    int[] tmpSeq = new int[seq.length]; // 申请临时目的存储空间
    mergeSortInInterval(seq, tmpSeq, 0, seq.length - 1); // 指定区间排序
}
// 对seq的left-right区间进行归并排序
void mergeSortInInterval(int[] seq, int[] tmpSeq, int left, int right) {
    if (left < right) {
        int mid = (left + right) >> 1;
        mergeSortInInterval(seq, tmpSeq, left, mid); // 左半区间归并排序
        mergeSortInInterval(seq, tmpSeq, mid + 1, right); // 右半区间归并排序
        mergeIntervals(seq, tmpSeq, left, mid, right); // 合并左、右半有序区间
    }
}
// 合并seq的left-mid区间与mid+1-right区间
void mergeIntervals(int[] seq, int[] tmpSeq, int left, int mid, int right) {
    int index1 = left; // 左半区间游标（left为起始处）
    int index2 = mid + 1; // 右半区间游标（mid+1为起始处）
    int index = left; // 目的数组游标
    while (index1 <= mid && index2 <= right) {
        tmpSeq[index++] = seq[index1] < seq[index2] ? seq[index1++] : seq[index2++];
    }
    while (index1 <= mid) {
        tmpSeq[index++] = seq[index1++];
    }
    while (index2 <= right) {
        tmpSeq[index++] = seq[index2++];
    }
    // 更改至原序列
    for (int i = left; i <= right; i++)
        seq[i] = tmpSeq[i];
}

快速排序

快排序采用分治的思想，选择一个元素作为枢轴，设立一个low指针指向序列首部，一个high指针指向序列尾部，一趟排序过程中将大于枢轴的元素都归置于高端，小于枢轴的元素都归置于低端，一趟下来，枢轴的位置便得到了确定。然后又递归地采用快排序，分别排列小于枢轴的子序列，和大于枢轴的子序列。
不难看出，归置元素最终确定枢轴位置这个过程才是快排序的核心。其过程通常是这样的：选取枢轴，将其值用临时变量privotKey保存住，然后将其与low指针所指向元素交换，然后转而从high指针指向位置开始，逐步移动与枢轴进行比较，直到找到一个小于枢轴的元素，便将该元素覆盖至low指针当前所指位置上去，然后又转而从low指针指向的下一位置开始，逐步移动与枢轴进行比较，直到找到一个大于枢轴的元素，又将该元素覆盖至high指针当前所指位置上去，循环往复，直到low >= high。
之所以采用这种类似交替的方式，是因为我们希望用赋值操作取代频繁的交换操作，因为赋值是交换的原子操作，必然比交换快得多，那么显然，比如当找到一个大于枢轴的元素后，我们直接粗暴地将其覆盖至high指针所指位置，必然会造成high指针处本来有的元素被覆盖掉，从而丢失序列元素！那如何做才能避免呢？还记得为什么我们最初要先把枢轴交换到low位置吧，就是这个小操作起到了大作用！因为一趟下来，枢轴必然是最后一个被归置的元素，它的位置要到其它元素都考察过了才能被确定下来，所以我们将其移到low处，然后通过考察high直至找到一个小于枢轴的元素，此时覆盖low也就万无一失了，因为该值为枢轴值，已暂存到了privotKey变量，而注意此时high位置元素还是之前那个，所以下一次从low开始覆盖上一次high所在位置的元素也就顺理成章了，这样一环扣着一环覆盖下去，直到最后确定枢轴，再人为地用privotKey覆盖一次。
代码如下：

// 快速排序
void quickSort(int[] seq) {
    quickSortInInterval(seq, 0, seq.length - 1); // 指定区间排序
}
// 按规定区间low-high对seq进行快速排序
void quickSortInInterval(int[] seq, int low, int high) {
    if (low < high) {
        int mid = getMiddle(seq, low, high);
        quickSortInInterval(seq, low, mid - 1); // 对左半区间快排序
        quickSortInInterval(seq, mid + 1, high); // 对右半区间快排序
    }
}
// 获取枢轴落脚位置
int getMiddle(int[] seq, int low, int high) {
    int privotKey = getPrivotKey(seq, low, high); // 枢轴值
    while (low < high) {
        while (low < high && seq[high] >= privotKey)
            high--;
        seq[low] = seq[high]; // 移至低位
        while (low < high && seq[low] <= privotKey)
            low++;
        seq[high] = seq[low]; // 移至高位
    }
    seq[low] = privotKey; // 枢轴归位
    return low;
}

需说明一点的是，如果我们“每趟”选的枢轴恰好对应的是最大或最小元素，那么此时快排将退化为冒泡排序，时间复杂度降为O(n)（注意：有的书上写的是当序列恰好为正序或逆序，这种情况成立的前提是，我们要保证是直接取low处的元素作为枢轴，而不是其它位置元素，所以这种说法不具一般性）。因此为了避免这种特殊情况出现，我们通常采用的策略有两种：

• 随机取：利用伪随机函数任取序列的某一位置作为枢轴
• 三者取中：比较序列首部、中部和尾部三个位置的元素大小，取大小位于中间者作为枢轴

该部分代码如下：

// 取枢轴运算
int getPrivotKey(int[] seq, int low, int high) {
    int privot;
    // 1.取低端
    // privot = low;
    // 2.随机取
    // privot = new Random().nextInt(high - low + 1);
    // 3.三者取中
    int mid = (low + high) / 2; //中间位置
    int[] threeSeq = {seq[low], seq[mid], seq[high]};
    insertSortWithGap(threeSeq, 0, 1);
    if(threeSeq[1] == seq[low]) privot = low;
    else if(threeSeq[1] == seq[mid]) privot = mid;
    else privot = high;
    // 把枢轴交换到低端处方便操作
    swap(seq, low, privot);
    return seq[low];
}

堆排序

堆首先是一棵完全二叉树，即只有最下面的两层结点度能够小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。满足这个条件以后，还要保证这棵树的所有子树都满足父节点元素大于两个子节点元素，这样的完全二叉树才能被称为堆（大顶堆）。
既然是完全二叉树，那么它必然满足下面的性质（假设树编号从0开始，此时某父节点下标为i，某子节点下标为j）：

• 父节点i的左子节点下标为2i + 1
• 父节点i的右子节点下标为2i + 2
• 子节点j的父节点下标为(j – 1) / 2

知道有上面性质以后就好办了，我们可以直接用一个一维数组表示整个堆，虽然物理结构上并非一个树形结构，但我们只要保证父子节点间的下标关系，大小关系，它在逻辑上便是一个堆。
那具体如何实现呢？显然，最初我们面对的一个原始序列它多半都不是个堆，那么我们就需要把它调整成一个堆（称为建堆）。那从哪里开始调整呢？我们要调整的是父节点与子节点的大小关系，那么我们不妨从后往前数，从第一个父节点开始调整它与其子节点的大小关系，这样逐个调整之前的所有父节点，直到调整完根节点后便建好了整个堆。此时堆顶已是整个序列的最大元素了，很明显我们只要把它取下来（称为顶元筛下），把它与当前堆的最后一个元素交换（称为尾元筛上），即把最大元素归位并确定下来了。而此时因为尾元的筛上，导致了堆的破坏，我们必须从根节点再逐一向下递归地调整子树。这样循环往复，第二次是次大元素归位，直到所有元素归位。
代码如下：

// 堆排序
void heapSort(int[] seq) {
    // 建堆：从第一个父节点开始调整子堆，直到所有父节点调整完
    for (int i = (seq.length - 1) / 2; i >= 0; i--)
        heapAdjust(seq, i, seq.length - 1);
    // 顶元筛下，尾元筛上
    for (int i = seq.length - 1; i > 0; i--) {
        swap(seq, 0, i); // 筛上、筛下
        heapAdjust(seq, 0, i - 1); // 重新调整堆
    }
}
// 将start-end之间的堆调整为大顶堆
void heapAdjust(int[] seq, int start, int end) {
    int topKey = seq[start]; // 暂存住堆顶下标
    for (int i = 2 * start + 1; i <= end; i = 2 * start + 1) {
        // 选出子节点较大者
        int larger = i;
        if (i + 1 <= end && seq[i + 1] > seq[i])
            larger = i + 1;
        if (topKey >= seq[larger])
            break; // 堆顶已是最大
        seq[start] = seq[larger]; // 较大者移到堆顶
        start = larger; // 游标下移
    }
    seq[start] = topKey; // 顶元归位
}

基数排序

基数排序就是按照子关键字来排序的方法，按照子关键字权重的大小，从小到大进行分配和收集的过程：

• 分配：根据子关键字的值，将值相同的元素归置于该子关键字对应的桶中
• 收集：按子关键字值从小到大的顺序，依次从各个桶中提取元素至新数组

那么几轮（子关键字权重数量决定）分配和收集下来，将自然形成一个从小到大的有序序列。需要说明的是，在实际编程实现的过程中，我们并不需要真的将元素分配至桶中的过程，而可以用统计子关键字值的数量并存入桶中来取代，因为我们并不关心元素在一个桶中的顺序，那么疑问又来了，这样我们又如何收集呢？那不可避免的，我们必须再计算一次元素的子关键字值，然后定位到对应的桶，并根据桶指定的下标存放位置，存入新数组中，然后下标下移。还有若干细节处理，详见代码：

// 基数排序
// radix: 基数最大值
// range: 子关键字数量
void radixSort(int[] seq, int radix, int range) {
    int[] buckets = new int[radix]; // 桶数组：长度为radix，存放对应于radix的元素个数
    int[] tmpSeq = new int[seq.length]; // 暂存数组
    for (int i = 0, weight = 1; i < range; i++) {
        
        Arrays.fill(buckets, 0); //清空桶
        System.arraycopy(seq, 0, tmpSeq, 0, seq.length); //复制序列
        
        //统计原序列中对应桶关键字的个数，入桶
        for(int j = 0; j < tmpSeq.length; j++){
            int subKey = (tmpSeq[j] / weight) % radix;
            buckets[subKey]++; 
        }
        
        //计算桶中个数达到的最大下标
        for(int j = 1; j < buckets.length; j++){
            buckets[j] = buckets[j] + buckets[j-1];
        }
        
        //遍历tmpSeq，提取关键字，并按照桶中指定下标存入原序列
        for (int j = tmpSeq.length - 1; j >= 0; j--){
            int subKey = (tmpSeq[j] / weight) % radix;
            seq[buckets[subKey] - 1] = tmpSeq[j];
            buckets[subKey]--;
        }
        
        //计算下一轮的关键字权重
        weight *= radix;
    }
}

结语

复杂排序算法就记录这4种啦，更多的可以参考相关书籍获悉。下一章将给出所有简单排序算法+复杂排序算法在本人机器上、不同规模的数据下的实际运行时间，并给出公认的各算法时间复杂度与空间复杂度。