高级排序算法-快速排序

高级排序算法-快速排序

这个方法的代码参考leecode平台的大佬——liweiwei1419的文章,原文出处:https://leetcode.cn/leetbook/read/learning-algorithms-with-leetcode/55szu2/

本文语言用的是C++:

快速排序实现一:

//leecode第912题快速排序一实现
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int len = nums.size();
        quickSort(nums, 0, len - 1);
        return nums;
    }

private: 
    void quickSort(vector<int>& nums, int left, int right) {
        // 注意:这里包括 > 的情况,与归并排序不同,请通过调试理解这件事情
        if (left >= right) {
            return;
        }
        int p = partition(nums, left, right);
        quickSort(nums, left, p - 1);
        quickSort(nums, p + 1, right);
    }

    int partition(vector<int>& nums, int left, int right) {
        // 随机选择一个元素作为切分元素
        int randomIndex = rand() % (right - left + 1) + left;//生成随机数的范围[left~right]
        swap(nums, randomIndex, left);

        int pivot = nums[left];
        // 循环不变量: lt 意即 less than
        // [left + 1, lt] < pivot,
        // [lt + 1, i) >= pivot
        int lt = left;
        // 注意,这里取等号
        for (int i = left + 1; i <= right; i++) {
            if (nums[i] < pivot) {
                // 交换当前元素与 lt 的位置
                lt++;
                swap(nums, i, lt);
            }
        }
        // 最后这一步要记得交换到起始位置
        swap(nums, left, lt);
        return lt;
    }

    void swap(vector<int>& nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
};


快速排序实现二(指针对撞):

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int len = nums.size();
        quickSort(nums, 0, len - 1);
        return nums;
    }

private: 
    void quickSort(vector<int>& nums, int left, int right) {
        // 注意:这里包括 > 的情况,与归并排序不同,请通过调试理解这件事情
        if (left >= right) {
            return;
        }
        int p = partition(nums, left, right);
        quickSort(nums, left, p - 1);
        quickSort(nums, p + 1, right);
    }

/**
     * 目标:与切分元素相等的元素均匀地分布在切分元素最终所在位置的两侧
     * 这个定义非常重要,直接影响我们的算法初始值定义
     * [left + 1, le) 全部小于标定点
     * (ge, right] 全部大于标定点
     * 在指针对撞的过程中,和标定点相同的元素就被挤到了中间
     *
     * @param nums
     * @param left
     * @param right
     * @return
     */
    int partition(vector<int>& nums, int left, int right) {
        // 随机选择一个元素作为切分元素
        int randomIndex = rand() % (right - left + 1) + left;//生成随机数的范围[left~right]
        swap(nums, randomIndex, left);

        // 循环不变量,le = less equals,ge = greater equals
        // all in [left + 1, le) <= pivot
        // all in (ge, right] >= pivot
        // le > ge 的时候终止
        int pivot = nums[left];
        int le = left + 1;
        int ge = right;
        while (true) {
            // 注意:这里一定是 nums[le] < pivot,等于 pivot 的元素是被交换过来得到的
            while (le <= ge && nums[le] < pivot) {
                le++;
            }
            // 此时 le 来到第 1 个大于等于 pivot 的位置
            while (le <= ge && nums[ge] > pivot) {
                ge--;
            }
            // 此时 ge 来到第 1 个小于等于 pivot 的位置
            if (le > ge) {
                break;
            }

            swap(nums, le, ge);
            le++;
            ge--;
        }
        swap(nums, left, ge);
        return ge;
    }

    void swap(vector<int>& nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
};

相关推荐

  1. 高级排序算法-快速排序

    2024-04-03 08:40:01       5 阅读
  2. 排序算法——快速排序

    2024-04-03 08:40:01       26 阅读
  3. 排序算法——快速排序

    2024-04-03 08:40:01       26 阅读
  4. 排序算法-快速排序

    2024-04-03 08:40:01       29 阅读

最近更新

  1. leetcode705-Design HashSet

    2024-04-03 08:40:01       5 阅读
  2. Unity发布webgl之后打开streamingAssets中的html文件

    2024-04-03 08:40:01       5 阅读
  3. vue3、vue2中nextTick源码解析

    2024-04-03 08:40:01       6 阅读
  4. 高级IO——React服务器简单实现

    2024-04-03 08:40:01       5 阅读
  5. 将图片数据转换为张量(Go并发处理)

    2024-04-03 08:40:01       4 阅读
  6. go第三方库go.uber.org介绍

    2024-04-03 08:40:01       6 阅读
  7. 前后端AES对称加密 前端TS 后端Go

    2024-04-03 08:40:01       7 阅读

热门阅读

  1. Jenkins 自动化更新 Stable Diffusion 介绍

    2024-04-03 08:40:01       2 阅读
  2. maya移除节点 修改节点

    2024-04-03 08:40:01       4 阅读
  3. 上传.PDF文件转为.DOCX文件

    2024-04-03 08:40:01       3 阅读
  4. 音响或耳机音频处理常用的芯片

    2024-04-03 08:40:01       4 阅读
  5. 微信小程序中路由跳转方式

    2024-04-03 08:40:01       3 阅读
  6. Python网络爬虫(二):Requests库

    2024-04-03 08:40:01       2 阅读
  7. SQLAlchemy 的数据库引擎engine与连接对象Connection

    2024-04-03 08:40:01       2 阅读
  8. Knife4j配置使用笔记

    2024-04-03 08:40:01       2 阅读
  9. nodejs的express负载均衡

    2024-04-03 08:40:01       5 阅读
  10. 每天学习一个Linux命令之dpkg

    2024-04-03 08:40:01       4 阅读
  11. linux扩展正则表达式之+

    2024-04-03 08:40:01       3 阅读