排序_快速排序|算法专题

# 思想

快速排序：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据比另一部分的所有数据要小，再按这种方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，使整个数据变成有序序列。

实现步骤：

选择一个基准元素target（一般选择第一个数）
将比target小的元素移动到数组左边，比target大的元素移动到数组右边
分别对target左侧和右侧的元素进行快速排序

从上面的步骤中我们可以看出，快速排序也利用了分治的思想（将问题分解成一些小问题递归求解）

下面是对序列6、1、2、7、9、3、4、5、10、8排序的过程：

# 解法

# 写法1

单独开辟两个存储空间left和right来存储每次递归比target小和大的序列

每次递归直接返回left、target、right拼接后的数组

浪费大量存储空间，写法简单

    function quickSort(array) {
      if (array.length < 2) {
        return array;
      }
      const target = array[0];
      const left = [];
      const right = [];
      for (let i = 1; i < array.length; i++) {
        if (array[i] < target) {
          left.push(array[i]);
        } else {
          right.push(array[i]);
        }
      }
      return quickSort(left).concat([target], quickSort(right));
    }

@前端进阶之旅: 代码已经复制到剪贴板

# 写法2

记录一个索引l从数组最左侧开始，记录一个索引r从数组右侧开始

在l<r的条件下，找到右侧小于target的值array[r]，并将其赋值到array[l]

在l<r的条件下，找到左侧大于target的值array[l]，并将其赋值到array[r]

这样让l=r时，左侧的值全部小于target，右侧的值全部小于target，将target放到该位置

不需要额外存储空间，写法思路稍复杂（有能力推荐这种写法）

    function quickSort(array, start, end) {
      if (end - start < 1) {
        return;
      }
      const target = array[start];
      let l = start;
      let r = end;
      while (l < r) {
        while (l < r && array[r] >= target) {
          r--;
        }
        array[l] = array[r];
        while (l < r && array[l] < target) {
          l++;
        }
        array[r] = array[l];
      }
      array[l] = target;
      quickSort(array, start, l - 1);
      quickSort(array, l + 1, end);
      return array;
    }

@前端进阶之旅: 代码已经复制到剪贴板

# 复杂度

时间复杂度：平均O(nlogn)，最坏O(n2)，实际上大多数情况下小于O(nlogn)

空间复杂度:O(logn)（递归调用消耗）

# 稳定性

不稳定

# 思想

实现步骤：

选择一个基准元素target（一般选择第一个数）
将比target小的元素移动到数组左边，比target大的元素移动到数组右边
分别对target左侧和右侧的元素进行快速排序

从上面的步骤中我们可以看出，快速排序也利用了分治的思想（将问题分解成一些小问题递归求解）

下面是对序列6、1、2、7、9、3、4、5、10、8排序的过程：

# 解法

# 写法1

单独开辟两个存储空间left和right来存储每次递归比target小和大的序列

每次递归直接返回left、target、right拼接后的数组

浪费大量存储空间，写法简单

    function quickSort(array) {
      if (array.length < 2) {
        return array;
      }
      const target = array[0];
      const left = [];
      const right = [];
      for (let i = 1; i < array.length; i++) {
        if (array[i] < target) {
          left.push(array[i]);
        } else {
          right.push(array[i]);
        }
      }
      return quickSort(left).concat([target], quickSort(right));
    }

@前端进阶之旅: 代码已经复制到剪贴板

# 写法2

记录一个索引l从数组最左侧开始，记录一个索引r从数组右侧开始

在l<r的条件下，找到右侧小于target的值array[r]，并将其赋值到array[l]

在l<r的条件下，找到左侧大于target的值array[l]，并将其赋值到array[r]

这样让l=r时，左侧的值全部小于target，右侧的值全部小于target，将target放到该位置

不需要额外存储空间，写法思路稍复杂（有能力推荐这种写法）

    function quickSort(array, start, end) {
      if (end - start < 1) {
        return;
      }
      const target = array[start];
      let l = start;
      let r = end;
      while (l < r) {
        while (l < r && array[r] >= target) {
          r--;
        }
        array[l] = array[r];
        while (l < r && array[l] < target) {
          l++;
        }
        array[r] = array[l];
      }
      array[l] = target;
      quickSort(array, start, l - 1);
      quickSort(array, l + 1, end);
      return array;
    }

@前端进阶之旅: 代码已经复制到剪贴板

# 复杂度

时间复杂度：平均O(nlogn)，最坏O(n2)，实际上大多数情况下小于O(nlogn)

空间复杂度:O(logn)（递归调用消耗）

# 稳定性

不稳定