算法（四）--快速排序算法（四）--快速排序

快速排序基本思想

快速排序（Quicksort）是对冒泡排序的一种改进。
快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序。
图示如下：

文章图片
快速排序递归图.png
废话不多说，上代码：

/** * 交换数组中索引a和索引b的值得位置 * @param {* 需要改变的数组} arr * @param {* 第一个值得索引} a * @param {* 第二个值得索引} b */ function swap(arr, a, b) { var temp = arr[a]; arr[a] = arr[b]; arr[b] = temp; } /** * 快速排序号称20世界最有影响算法之一 * @param {* 需要排序的数组} arr * @param {* 数组长度} n */ this.quickSort = (arr, n) => { var _this = this __quickSort(arr, 0, n - 1) function __quickSort(arr, l, r) {if (l >= r) { return } //基本上所有的高级排序在底层都可以采用插入排序进行优化 // if (r - l <= 10) { //_this.insertionSort2(arr, l, r) //return // } let p = __partition(arr, l, r) __quickSort(arr, l, p - 1) __quickSort(arr, p + 1, r) } //对arr进行partition操作返回一个索引下标 p //满足 arr[l,p1]里面所有的值都小于 arr[p] , arr[p+1,r]里面所有的值都大于 arr[p] function __partition(arr, l, r) { let n = parseInt(Math.random() * (r - l + 1) + l, 10) swap(arr, l, n) let v = arr[l] let p = l // arr[l+1...p] < v < arr[p+1...r)r这边是开区间因为r本身是被考察的对象 for (let i = l + 1; i <= r; i++) { if (arr[i] < v) { swap(arr, p + 1, i) p++ } } swap(arr, l, p) return p } }

代码解析：
1.快排排序都有一个partition的过程，利用考察对象对数组进行分割。
2.递归，重复partition操作即可。
3.针对partition函数里面let n = parseInt(Math.random() * (r - l + 1) + l, 10) swap(arr, l, n)的这段代码。这是为了保证每次选取的参考对象的随机性，如果每次选择第一个当做参考对象，那么当我们用这种方式排序的时候就会出现一个极端情况，如图：

文章图片
最差的快速排序.png
使用随机后把这种概率下降到极低的情况。让代码更为完善。
当然没有最好，只有更好。当我们用上面的代码去排序一个重复值很多的数组时，就会出现耗时很长的情况，因为以上代码吧等于考察对象的值都分到大于考察对象的数组里面，会导致趋于最差情况的排序。解决代码如下：

/** * 快速排序解决多个重复值得情况 * @param {* 需要排序的数组} arr * @param {* 数组长度} n */ this.quickSort2 = (arr, n) => { var _this = this __quickSort(arr, 0, n - 1) function __quickSort(arr, l, r) { if (l >= r) { return } //基本上所有的高级排序在底层都可以采用插入排序进行优化 // if (r - l <= 10) { //_this.insertionSort2(arr, l, r) //return // } let p = __partition(arr, l, r) __quickSort(arr, l, p - 1) __quickSort(arr, p + 1, r) } //对arr进行partition操作返回一个索引下标 p //满足 arr[l,p1]里面所有的值都小于 arr[p] , arr[p+1,r]里面所有的值都大于 arr[p] function __partition(arr, l, r) { let n = Math.floor(Math.random() * (r - l + 1) + l, 10) swap(arr, l, n) let v = arr[l] let i = l + 1, p = r while (true) { while (i <= r && arr[i] < v) { i++ } while (p >= l + 1 && arr[p] > v) { p-- } if (i > p) { break } swap(arr, i, p) i++ p-- } swap(arr, l, p) return p } }

【算法（四）--快速排序】代码思路：
从数组的左右两边分别和考察对象进行比较，左边选取<的值，右边选取>的值，一轮循环结束后交换循环结束时的两个值的位置，就算这两个值是相等也交换位置，这样基本保证了左右两边拥有相等值数量基本相同。还是用两张图来比较一下两种partition的区别

文章图片
partition1.png

文章图片
partition2图示.png
相信有了图示应该好理解一些了。
快速排序还有一种方式可以很好的解决这个问题，我们叫它三路快速排序，先看代码：

/** * 3路快速排序解决多个重复值得情况 * @param {* 需要排序的数组} arr * @param {* 数组长度} n */ this.quickSort3Ways = (arr, n) => { var _this = this __quickSort(arr, 0, n - 1) function __quickSort(arr, l, r) {// if (l >= r) { //return // } //基本上所有的高级排序在底层都可以采用插入排序进行优化 if (r - l <= 15) { _this.insertionSort2(arr, l, r) return } //partition操作 let n = Math.floor(Math.random() * (r - l + 1) + l, 10) swap(arr, l, n) let v = arr[l] let lt = l; // arr[l+1...lt] < v let gt = r + 1; // arr[gt...r] > v let i = l + 1; // arr[lt...i] == vwhile (i < gt) { if (arr[i] < v) { swap(arr, i, lt + 1) lt++ i++ } else if (arr[i] > v) { swap(arr, i, gt - 1) gt-- } else { i++ } } swap(arr, l, lt)__quickSort(arr, l, lt - 1) __quickSort(arr, gt, r) }}

这次我们先上图来理解这种三路快速排序