同冒泡排序一样，快速排序也属于交换排序，通过元素之间的比较和交换位置来达到排序的目的
不同的是，冒泡排序在每一轮中只把1个元素冒泡到数列的一端，而快速排序则在每一轮挑选一个基准元素，并让其它比它大的元素移动的数列的一边，比它小的元素移动到数列的另一边，从而把数列拆解成两个部分
这种思路叫做分治法
流程：
每一轮的比较和交换都需要把数组全部元素都遍历一遍，时间复杂度是O(n),需要遍历logn轮，所以时间复杂度为O(nlogn)
基准元素的选择
最简单的方式是选择数列的第一个元素
这种选择在大多数情况下是没问题的，但是假如有一个原本逆序的数列，期望排序称为顺序的数列，则会出现时间复杂度退化称为O(n2)的情况
避免这种情况的做法是随机选取一个元素作为基准元素，并且让基准元素和列首元素交换位置
但是即使随机选择元素，也有极小的几率选择到数列的最大值或者最小值，所以虽然快速排序的平均时间复杂度是O(nlogn)，但是最坏的情况下时间复杂度是O(n2)
元素交换
设定基准元素之后，就是要把其他元素中小于基准元素的都交换到基准元素的一边，大于基准元素的都交换到基准元素的另一边，
具体实现有两种方法：
1. 双边循环法
· 2. 单边循环法
双边循环法
详细过程如下：
原始数组如下，要求对其从小到大排序
1. 首先，选择基准元素 pivot，并且设置两个指针 left 和 right，指向数列的最左和最右两个元素
2. 进行第一次循环，从 right 指针开始，让指针指向的元素和基准元素进行比较，如果大于 pivot，则指针向左移动，如果小于等于 pivot 则 right 指针停止移动，切换 left 指针
在当前数列中，1 < 4 所以right指针直接停止移动，
切换 left 指针，让指针指向的元素和基准元素进行比较，如果小于或等于 pivot，则指针向右移动，如果大于 pivot，则 left 指针停止移动
由于left指针开始指向基准元素，判断肯定相等，所以 left 右移一位，
由于 7 > 4 则 left 指针停下，这时让 left 和 right 指针所指向的元素进行交换
3. 接下来重新切换到 right 指针 进行第二次循环，后续步骤如下：
代码如下
1 /** 2 * @param {Array<number>} arr 待交换的数组 3 * @param {number} startIndex 起始下标 4 * @param {number} endIndex 结束下标 5 * @returns {number} 返回基准元素位置 6 * @description 分治 双边循环法 7 */ 8 function partition(arr: Array<number>, startIndex: number, endIndex: number):number { 9 // 取第一个位置的元素作为基准元素 10 const pivot = arr[startIndex]; 11 // left 指针 12 let left = startIndex; 13 // right 指针 14 let right = endIndex; 15 16 17 while(left != right) { 18 // 控制right指针左移 19 while(left < right && arr[right] > pivot) { 20 right-- 21 } 22 // 控制left指针右移 23 while(left < right && arr[left] <= pivot) { 24 left++ 25 } 26 // 如果指针不重合 交换left right 指针所指元素 27 if(left < right) { 28 let p = arr[left]; 29 arr[left] = arr[right]; 30 arr[right] = p; 31 } 32 } 33 // pivot 和重合点交换 34 arr[startIndex] = arr[left]; 35 arr[left] = pivot; 36 /* 37 这里有个问题思索了很久：怎么保证交换的left元素 一定是小于 或者 大于 基准元素 38 细想下来：如上代码 left 或者 right 其中一个停止，另一个 移动过来重合 39 如果 left => right 则 right一定为 小于= pivot 的元素 40 如果 left <= right 则 一定为 小于= pivot的元素 41 */ 42 return left 43 } 44 45 46 47 function quickSort(arr: Array<number>, startIndex: number, endIndex: number) { 48 if(startIndex >= endIndex) { 49 return 50 } 51 // 得到基准元素的位置 52 let pivotIndex = partition(arr, startIndex, endIndex); 53 // 根据基准元素 分为两部分递归排序 54 quickSort(arr, startIndex, pivotIndex - 1); 55 quickSort(arr, pivotIndex + 1, endIndex); 56 } 57 58 59 60 function main() { 61 let arr = [4, 2, 6, 2, 2, 2, 2, 8]; 62 quickSort(arr, 0, arr.length - 1 ); 63 console.log(arr) 64 } 65 main() 66 67 68 69
单边循环法
给出原始数组，要求对其从小到大进行排序：
选的基准元素 pivot，同时设置一个 mark 指针指向数列起始位置，这个 mark 指针代表 小于基准元素的区域边界
接下来，从基准元素的下一个位置开始遍历数组，
如果遍历到的元素大于基准元素，就继续往后遍历
如果遍历到的元素小于基准元素，则需要做两件事情：
第一、把 mark 指针右移 1 位，因为小于 pivot 的区域边界增大了 1
第二、让最新遍历到的元素和 mark 指针所在位置的元素交换位置，因为最新遍历的元素属于小于 pivot 的区域
首先遍历到元素 7，7 > 4，所以继续遍历
接下来遍历到元素 3，3 < 4，所以 mark 指针右移 1 位
随后，让元素 3 和 mark 指针所在位置的元素交换，因为 3 归属小于 pivot 区域
后续步骤如下:
代码如下:
1 /** 2 * @param {Array<number>} arr 待交换的数组 3 * @param {number} startIndex 起始位置 4 * @param {number} endIndex 结束位置 5 * @description 分治 单边循环法 6 */ 7 function partition(arr: Array<number>, startIndex: number, endIndex: number):number { 8 // 拿到基准元素 9 let pivot = arr[startIndex]; 10 // 边界 11 let mark = startIndex; 12 13 14 for (let index = startIndex; index <= endIndex; index++) { 15 if(arr[index] < pivot) { 16 mark++; 17 let p =arr[mark]; 18 arr[mark] = arr[index]; 19 arr[index] = p 20 } 21 } 22 23 24 arr[startIndex] = arr[mark]; 25 arr[mark] = pivot; 26 return mark 27 } 28 29 30 function quickSort(arr: Array<number>, startIndex: number, endIndex: number){ 31 if(startIndex >= endIndex) { 32 return 33 } 34 35 36 const pivotIndex = partition(arr, startIndex, endIndex); 37 38 39 quickSort(arr, startIndex, pivotIndex - 1); 40 quickSort(arr, pivotIndex + 1, endIndex) 41 } 42 43 44 function main() { 45 let arr = [4, 4, 6, 5, 3, 2, 8, 1]; 46 quickSort(arr, 0, arr.length - 1); 47 console.log(arr) 48 } 49 50 51 main(); 52
非递归实现
1 /** 2 * @param {Array<number>} arr 待排序的数组 3 * @param {number} startIndex 起始位置 4 * @param {number} endIndex 结束位置 5 * @returns 基准元素下标 6 * @description 分治 单边循环法 7 */ 8 function partition(arr: Array<number>, startIndex: number, endIndex: number) { 9 // 基准元素 10 let pivot = arr[startIndex] 11 // 边界 12 let mark = startIndex 13 14 15 for (let index = startIndex; index <= endIndex; index++) { 16 if(arr[index] < pivot) { 17 mark++; 18 let p = arr[mark]; 19 arr[mark] = arr[index]; 20 arr[index] = p 21 } 22 }; 23 24 25 arr[startIndex] = arr[mark]; 26 arr[mark] = pivot; 27 return mark 28 } 29 30 31 interface StackItem { 32 startIndex: number; 33 endIndex: number; 34 } 35 36 37 function quickSort(arr: Array<number>, startIndex: number, endIndex: number) { 38 // 用一个栈来代替递归的调用栈 39 let quickSortStack:Array<StackItem> = []; 40 // 起止下标 41 let obj:StackItem = { 42 startIndex, 43 endIndex 44 }; 45 quickSortStack.push(obj); 46 // 当栈为空时结束 47 while(quickSortStack.length) { 48 let item = quickSortStack.pop() as StackItem; 49 let { startIndex, endIndex } = item 50 let pivotIndex = partition(arr, startIndex, endIndex); 51 // 如果一边有两个 或者两个以上的元素 则继续入栈 52 if(startIndex < pivotIndex - 1) { 53 quickSortStack.push({ 54 startIndex, 55 endIndex: pivotIndex - 1 56 }) 57 } 58 if(endIndex > pivotIndex + 1) { 59 quickSortStack.push({ 60 startIndex : pivotIndex + 1, 61 endIndex: endIndex 62 }) 63 } 64 } 65 } 66 67 68 function main() { 69 let arr = [4, 4, 6, 5, 3, 2, 8, 1]; 70 quickSort(arr, 0, arr.length - 1); 71 console.log(arr) 72 } 73
摘要总结自: 漫画算法 小灰的算法之旅