前面说到了三种简单的排序和归并排序，今天中午就开始来谈一谈我理解的快速排序。快速排序是前面冒泡排序的一个改进版本，我们在学习的时候可以对照两个来进行学习
一、 首先来个简单的需求
首先我们在了解快排之前，我们先来完成这样一个需求：在一个无序数组中随机选定一个值为基点，将数组的根据该基点进行排序，将比基点小的元素放在基点的左边，比基点大的元素放在基点的右边。
具体的操作如下：
1.1、 初始化数组和指针
假定我们得到这样一个数组：
| 序列号 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 数据 | 5 | 4 | 9 | 1 | 7 | 6 | 2 |
| 指针 | i⬆️ | j⬆️ |
temp=5
如上表格所示，给定一个无序数组，然后再给定两个指针i、j，分别将指针i，j拨向数组的首尾位置。然后再设置一个变量temp用来存储数组中的第一个元素5。也就是说将temp定义成我们前面的基点。
1.2、拨动指针
1> 首先我们先拨动指针j，从数组的末端开始查找 直到找到一个比temp要小的元素，找到之后将该值赋值给数组的首位。
| 序列号 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 数据 | 2 | 4 | 9 | 1 | 7 | 6 | 2 |
| 指针 | i⬆️ | j⬆️ |
temp=5
2> 然后再拨动指针i，从数组的开头开始查找，直到找到一个比temp要大的元素位置，并且将该值赋值给上面查到的数组位置。
| 序列号 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 数据 | 2 | 4 | 9 | 1 | 7 | 6 | 9 |
| 指针 | i⬆️ | j⬆️ |
temp=5
3> 重复上面两步操作，直到两指针指向同一个元素
| 序列号 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 数据 | 2 | 4 | 1 | 1 | 7 | 6 | 9 |
| 指针 | ij⬆️ |
temp=5
1.3、赋值
最后将temp赋值给指针i，j指向的位置，此时左边的元素肯定比该元素要小，右边的肯定比该元素要大，就满足了前面说的需求了。
| 序列号 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 数据 | 2 | 4 | 1 | 5 | 7 | 6 | 9 |
| 指针 | ij⬆️ |
temp=5
1.3、详细的代码如下：
function partition(arr,left,right){
let temp = arr[left];
while(left<right){
// 从右边开始查找
while(left<right&&arr[right]>=temp) right--;
// 如果指针没有相遇的情况下，找到就，就赋值
if(left<right) arr[left] =arr[right];
// 从左边开始查找
while(left<right&&arr[left]<=temp) left++;
// 如果指针没有相遇的情况下，找到就，就赋值
if(left<right) arr[right]=arr[left];
}
// 将temp赋值到最中间的元素
arr[left]=temp;
return arr;
}
二、 真正的快速排序来了
前面一章我们在使用归并排序的时候其实也讲到了分治，那么快速排序是不是也可以用分治来解决呢？
回答是肯定的，没错，快排的思想也是分治。
我们重新整理一下思想：
给定一个数组：
[5 ,4 ,9 ,1 ,7 ,6 ,2]
| | |
[2,4,1] 5 [7,6,9]
1 2 4 5 6 7 9
如上图所示，我们首先利用一次快排将比5小的数值放在5的左边，比5大的数值放在5的右边。然后我们可以将5左边的数列在进行快排，同样在该数列内2左边的肯定比2小，2右边的肯定比大。就这样不断的细分 就将原本无序的数列组合成了一个有序的数列了。
具体分治的代码如下：
function quickSort(arr,left,right){
if(left<right){
//找到中心的位置
let datas = partition(arr,left,right);
// 排序中心左边的数列
quickSort(arr,left,datas-1);
// 排序中心右边的数列
quickSort(arr,datas+1,right);
}
return arr;
}
全套代码如下：
function partition(arr,left,right){
let temp = arr[left];
while(left<right){
// 从右边开始查找
while(left<right&&arr[right]>=temp) right--;
// 如果指针没有相遇的情况下，找到就，就赋值
if(left<right) arr[left] =arr[right];
// 从左边开始查找
while(left<right&&arr[left]<=temp) left++;
// 如果指针没有相遇的情况下，找到就，就赋值
if(left<right) arr[right]=arr[left];
}
// 将temp赋值到最中间的元素
arr[left]=temp;
return left;
}
function quickSort(arr,left,right){
if(left<right){
//找到中心的位置
let datas = partition(arr,left,right);
// 排序中心左边的数列
quickSort(arr,left,datas-1);
// 排序中心右边的数列
quickSort(arr,datas+1,right);
}
return arr;
}
三、 其实还有更简单的排序方式
其实关于这个，我还想到了更简单的解决方法。思想大概就是寻找一个基点，我这里寻找的是数组的最后一项temp作为基点（当然你也可以选择其他的元素）。然后数组内剩下的元素进行遍历，并且将比temp小的元素放在一个新的数组内，比数组大的放在另一个新的数组内。然后再将两个新数组通过分治在进行快速排序，直到数组的长度为小于2时停止，最后将排序好的数组和基点进行组合，就得到了新的有序数列了。
具体的代码如下：
function quickSort(arr){
// 如果数组只有一项就直接放回了
if(arr.length<=1) return arr;
//取出元素的最后一项
let temp=arr.pop();
let left=[];
let right=[];
for(let i=0;i<arr.length;i++){
// 将比pivot
if(arr[i]<=temp) left.push(arr[i]);
else right.push(arr[i]);
}
return [...quickSort(left),...[temp],...quickSort(right)]
}
说在最后
快速排序也是面试经常会考的点，怎么说呢？有备无患吧。额，要睡觉了，只能睡5分钟了 中午不睡 下午崩溃呀！！
网友评论