快速排序动态过程演示
快排的思路很简单, 选择一个基准元素, 把比这个元素大的放到右边, 小的放到左边, 这样就分成了两组
然后对左边的那一组和右边的那一组分别再进行上面的操作
递归进行,如果一组元素的长度为1, 就是递归的出口了
考试时候一般要求给出快速排序分划交换的过程
开始: 50, 79, 8, 56, 32, 41, 85, 26, 70
要注意由于教科书上采用的是两个指针从左右扫描分组的交换策略
因此在排序的过程中并不是简单地分成两组
顺序需要与程序实际运行的一致
这也是快排不稳定的原因吧
如果采取新建数组来分别存储两个分组
那么快排是稳定的
只是空间复杂度会更高一些
第一趟: [26, 8,41, 32 ] 50 [56, 85, 79, 70]
第二趟: [8] 26 [41, 32] 50 56 [85, 79, 70]
第三趟: 8 26 [32] 41 50 56 [70, 79] 85
第四趟: 8 26 32 41 50 56 70 [79] 85
第五趟: 8 26 32 41 50 56 70 79 85
JavaScript实现如下:
/*
* 快速排序, 不使用另外的数组, 在原数组上原地排序
*
* @param array - 待排序的数组
* @param start - 排序的起始位置下标
* @param end - 排序的结束位置下标
*/
function quickSort(array, start, end)
{
// 递归出口
if(end <= start)
{
return
}
const datum = array[start] // 取最左边的元素作为基准变量
let left = start // 左指针
let right = end + 1 // 右指针
while(left < right)
{
// 从左边开始向右找一个比基准元素大的元素, 注意要防止越界
left ++
while(array[left] < datum && left < end)
{
left ++
}
// 从右边开始向左找一个比基准元素小的元素
// 向左寻找的过程中不会越界, 临界情况是右指针移动到基准元素位置
right --
while(array[right] > datum)
{
right --
}
// 交换这两个元素
if(left < right)
{
swap(array, left, right)
}
}
// 临界情况下, 右指针移动到基准元素位置
// 这个时候, 就不必再交换基准元素了, 直接分组即可
// 左边的那一组元素个数肯定为 -1, 会直接到达递归出口
if(datum < right)
{
// 交换基准元素, 将原数组分成两组
swap(array, datum, right)
}
// 分别对两组进行递归
quickSort(array, start, right - 1)
quickSort(array, right + 1, end)
}
