最优雅的算法——快速排序

快速排序：探索两种流行的方法

快速排序，这个听起来有点技术性的术语，实际上是一个既高效又优雅的算法，它能够将一堆混乱的数据快速整理得井井有条。今天，我们将通过一种轻松愉快的方式，一起揭开快速排序的神秘面纱，并探索两种流行的实现方法。
话不多说，开始战斗

快速排序的魔法：基本原理

想象一下，你有一副乱序的扑克牌，你想要快速地将它们按照大小排列。快速排序的魔法就在于，你每次都从牌堆中挑出一张牌作为“基准牌”，然后根据这张牌将其他牌分成两堆：一堆比它小，一堆比它大。这样，每次你都能迅速地将牌堆分成更小的部分，然后重复这个过程，直到所有的牌都被有序地排列好。

方法一：三数取中法

代码解析与注释

void quick_sort(int* data, int ns) {
    // 初始化变量，end代表数组的最后一个元素的索引
    int end = ns - 1;
    // left和right分别代表当前分区的左右边界
    int left = 0;
    int right = end;
    // 选择中间元素作为基准值，这是一种常见的选择基准的方法
    int mid_val = data[end / 2];
    while (left <= right) {
        // 从左向右找，直到找到一个大于等于基准值的元素
        while (data[left] < mid_val)
            left++;
        // 从右向左找，直到找到一个小于等于基准值的元素
        while (data[right] > mid_val)
            right--;
        // 如果left小于right，说明找到了一对可以交换的元素
        if (left < right) {
            int temp = data[left];
            data[left] = data[right];
            data[right] = temp;
            // 移动指针，继续寻找下一对可以交换的元素
            left++;
            right--;
        }
        // 如果left和right相遇，说明这一轮没有找到可以交换的元素
        else if (left == right) {
            left++;
            right--;
        }
    }
    // 如果左边还有元素，递归地对左边的子数组进行快速排序
    if (left < end)
        quick_sort(data + left, end - left + 1);
    // 如果右边还有元素，递归地对右边的子数组进行快速排序
    if (right > 0)
        quick_sort(data, right + 1);
}

方法二：单基准法

代码解析与注释

int purtition(int* dat, int low, int high) {
    // 选择数组的第一个元素作为基准
    int pivot = dat[low];
    while (low < high) {
        // 从右向左找，直到找到一个小于基准值的元素
        while (low < high && dat[high] >= pivot)
            high--;
        // 将找到的元素放到左边
        dat[low] = dat[high];
        // 从左向右找，直到找到一个大于基准值的元素
        while (low < high && dat[low] <= pivot)
            low++;
        // 将找到的元素放到右边
        dat[high] = dat[low];
    }
    // 基准元素归位
    dat[low] = pivot;
    return low; // 返回基准元素的最终位置
}

void quick_s(int* dat, int low, int high) {
    int mid;
    // 如果区间无效，直接返回
    if (low >= high)
        return;
    // 进行分区操作，并获取基准元素的最终位置
    mid = purtition(dat, low, high);
    // 对基准左边的子数组递归进行快速排序
    quick_s(dat, low, mid - 1);
    // 对基准右边的子数组递归进行快速排序
    quick_s(dat, mid + 1, high);
}

void quick_sort2(int* dat, int ns) {
    // 从整个数组开始进行快速排序
    quick_s(dat, 0, ns - 1);
}

总结

快速排序就像是一个魔术师，它用巧妙的手法将混乱变得有序。三数取中法和单基准法都是这个魔术师的拿手好戏，它们各有千秋，但都能达到同样的效果——快速地将数据排序。希望这篇文章能让你对快速排序有了更生动、更清晰的理解。如果你对快速排序还有任何疑问，或者想要了解更多的算法知识，欢迎在评论区交流讨论！