快速排序
快速排序是冒泡排序的优化，与冒泡排序不同的是，使用了分治法，进行优化。会随机选取一个值pivot（基准元素），与其它值进行比较，将小于这个值的值全部放到一边，大于这个值的值放到另一边。然后再对两边的序列区间重复进行此操作，直至成为有序队列为止。
- 时间复杂度为：nlogn
- 空间复杂度为：logn
- 是不稳定的排序方法
快排的实现
单边循环法
比如对于初始序列：[8, 9, 6, 3, 2, 7]
实现过程思路：
- 使用一个mark指针，用来表示小于基准元素的区域边界，初始时，指向pivot（基准元素，一般我们可以取第1位），也就是mark指向8，[8(mark), 9, 6, 3, 2, 7]
- 从基准元素下一位x开始遍历，如果x > pivot，也就是9 > 8，不做任何操作，，[8(mark), 9(x), 6, 3, 2, 7]，继续遍历
- 遍历的下一位, [8(mark), 9, 6(x), 3, 2, 7]，此时6 < 8，代表着这个数要移动到pivot的左侧，所以此时mark往右移一位，用来放置这个数，然后x和mark指向的数进行位置交换，也就是6和9交换，得到[8, 6(mark), 9(x), 3, 2, 7]
- 继续[8, 6(mark), 9, 3(x), 2, 7]，x = 3，x < pivot，mark向右移一位指向9，3和mark指向的数9交换，交换后得到 [8, 6, 3(mark), 9(x), 2, 7]
- 继续，[8, 6, 3(mark), 9, 2(x), 7], x = 2, 2 < 8，mark+1指向9，9与2交换，得到[8, 6, 3, 2(mark), 9(x), 7]
- 继续[8, 6, 3, 2(mark), 9, 7(x)]，7 < 8，mark+1指向9，9与7交换，得到[8(pivot), 6, 3, 2, 7(mark), 9(x)]，此时x已是遍历的最后一位，所以这时将pivot与mark位置进行交换, [7, 6, 3, 2, 8, 9]，这样就完成了第一轮的快排，此时8左边的数都是小于8的，右边的数都是大于8的
- 再递归对8左右两边序列[7,6,3,2]、[9]进行1-6步骤进行快速，直至成为整个数组变成有序队列
/*
* 快速排序
* 单边循环法的递归实现
*/
function singleQuickSort(arr, startIndex, endIndex) {
// 健壮性判断
if(!Array.isArray(arr)) throw new Error("请输入一个数组")
if(!arr.length) return []
if(startIndex >= endIndex) return;
// 基准元素
let pivot = arr[startIndex];
// 标记指针,用于表示小于基准元素的区域边界
let mark = startIndex;
for(let i = startIndex + 1; i <= endIndex; i++) {
if(arr[i] < pivot) {
mark++;
[ arr[mark], arr[i] ] = [ arr[i], arr[mark] ]
}
}
[ arr[startIndex], arr[mark] ] = [ arr[mark], arr[startIndex] ]
singleQuickSort(arr, startIndex, mark - 1)
singleQuickSort(arr, mark + 1, endIndex)
return arr
}
const arr = singleQuickSort([8, 9, 6, 3, 2, 7], 0, 5)
console.log(arr) // [ 2, 3, 6, 7, 8, 9 ]
双边循环法
双边循环法，顾名思义，就是用双指针的方法来遍历元素
实现过程：
如：[8, 2, 6, 3, 9, 7]
- 假如随机值定基准元素pivot为第一个数8，定义一个左指针（指向第一个数），和一个右指针（指向最后一个），则8先与最后一个值进行比较，8比7大，所以两值交换位置[7, 2, 6, 3, 9, 8]
- 此时左指针往右移一位，2与8比，2比8小，位置不变，左指针继续往右移动一位
- 此时左指针往右移一位，6与8比，6比8小，位置不变，左指针继续往右移动一位
- 3和8比，左指针继续往右移动一位
- 9和8比，交换位置[7, 2, 6, 3, 8, 9]，此时左指针不变，右指针向左移一位，至此左右指针相同，第一轮比较结束，注意，结束的条件是左指针位置大于等于右指针；比8小的数都在8的左边，比8大的数都在8的右边
- 对左边[7, 2, 6, 3]和右边的序列[9]分别再重复1-4步，直至都成为有序序列
/*
* 快速排序
* 双边循环法的递归实现
*/
function doubleQuickSort(arr, startIndex, endIndex) {
// 健壮性判断
if(!Array.isArray(arr)) throw new Error("请输入一个数组")
if(!arr.length) return []
if(startIndex >= endIndex) return arr;
// 基准元素
const pivot = arr[startIndex]
// 左指针
let left = startIndex
// 右指针
let right = endIndex
// 只要左右指针不重合，就会继续循环
while(left != right) {
// 从最右边开始比较，如果right元素大于基准元素，则右指针向左移一位
while(left < right && pivot <= arr[right]) {
right--;
}
// 如果右边元素小于基准元素，则交换位置，然后左指针向右移一位
if(arr[right] < pivot) {
[ arr[left], arr[right] ] = [ arr[right], arr[left] ]
left++;
}
// 然后开始比较基准元素和左边元素，如果左边元素小于基准元素，左指针向右移一位
while(left < right && pivot >= arr[left]) {
left++;
}
// 如果左边元素大于基准元素，则交换位置，然后右指针向左移一位
if(arr[left] > pivot) {
[ arr[left], arr[right] ] = [ arr[right], arr[left] ]
right--;
}
}
// 当left===right时，就是基准元素所在的最终位置,此时 arr[left] === arr[right] === pivot;
// 递归遍历左边和右边的无序队列
doubleQuickSort(arr, startIndex, left-1)
doubleQuickSort(arr, left + 1, endIndex)
return arr;
}
const arr2 = doubleQuickSort([8, 9, 6, 3, 2, 7], 0, 5)
console.log(arr2) // [ 2, 3, 6, 7, 8, 9 ]
排序算法系列文章传送门(未完，持续更新中)：
排序算法-1（javascript） 冒泡、选择、插入、希尔排序的实现
排序算法-2（javascript） 快速排序的实现
排序算法-3（javascript） 堆排序的实现
排序算法-4（javascript） 归并排序的实现
