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

引言

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

归并排序

该算法正如其名,围绕着两种策略进行。

指的是递归,利用二分法将整个序列划分成左右两个子序列,再将左子序列又二分为左右子序列,将右子序列同样也二分为左右子序列,整个二分过程体现在代码上就是递归调用的过程;

指的是合并,递归不能无限地进行下去,总是需要一个出口的,而显然二分的出口就在于当两个子序列均仅剩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种啦,更多的可以参考相关书籍获悉。下一章将给出所有简单排序算法+复杂排序算法在本人机器上、不同规模的数据下的实际运行时间,并给出公认的各算法时间复杂度与空间复杂度。

Leave a Comment.