一种改进的快速排序算法

快速排序思路

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

最基本的实现就是从后往前找比基准小的，找到之后从前往后找一个比基准大的。这样的实现，需要写两个循环,分别是从前往后和从后往前的实现。具体的实现，就不在这里讲了，主要讲一下改进后的快速排序算法。

本文主要讲的是一种改进的方法。

实现思路

选择最后一个数作为基准，从前往后循环，第一次遇到比基准小的数就和第一个数字进行位置交换，第二次遇到就和第二个数进行位置交换，以此类推，知道最后将基准交换过去。这样就只需要一次循环就能实现。

代码示例

function quickSort(arr, left, right) {
  if (left < right) {
    let standard = arr[right], i = left
    for (let j = left; j <= right; j++) {
      if (arr[j] <= standard) {
        let temp = arr[i]
        arr[i] = arr[j]
        arr[j] = temp
        i++
      }
    }
    quickSort(arr, left, i - 2)
    quickSort(arr, i, right)
  }
  return arr
}

如下面的数组：

0	1	2	4	5	6
10	9	5	7	11	8

基准x = 8，

1. 10 > 8 continue
2. 9 > 8 continue

3. 5 <= 8 所以5和第一个数10交换位置得到新数组
   | 0 | 1 | 2 | 4 | 5 | 6 |
   | :–: | :–: | :–: | :–: | :–: | :–: |
   | 5 | 9 | 10 | 7 | 11 | 8 |

4. 7 <= 8 所以7和第二个数9交换得到新数组

0	1	2	4	5	6
5	7	10	9	11	8

1. 最后 8<= 8 所以8和现在排在第三位的10交换位置

0	1	2	4	5	6
5	7	8	9	11	10

到这里以8为基准已经完成了第一次快速排序，接下来只要对前后两部分地柜调用同样的方法就行。

这里有几点需要注意：

• 判断条件一定是<=这样才能将基准放到中间的位置
• 需要增加一个当前交换到了第几个位置的变量
• 递归需要结束的条件，就是上面代码中的left right(需要执行快速排序的数组的其实和终止位置)