JAVA-快速排序
目次一、快速排序基本思想
二、快速排序的实现
1.Hoare法找基准值
2.挖坑法
3.前后指针法(了解)
三、快速排序的优化
1.三数取中法
2.递归到小的子区间时，可以考虑使用插入排序
四、非递归的写法
五、时间空间复杂度
一、快速排序基本思想
快速排序是Hoare于1962年提出的一种二叉树布局的互换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中全部元素均小于基准值，右子序列中全部元素均大于基准值，然后最左右子序列重复该过程，直到全部元素都排列在相应位置上为止。 我们此次实现拿数组的第一个元素做为基准值 https://i-blog.csdnimg.cn/direct/9deea3076466452fbc34d7d49024312f.png
right找到比tmp小的，left再找到比tmp大的就互换。如果交汇了就放入第一个元素，再把tmp放进来。 right必须先找left后找
https://i-blog.csdnimg.cn/direct/600d9a32e78f4102a6e5b2dba1cfc22f.png
把交汇处的下标给par，再分别从par两边重复之前的操纵。而且这不就是二叉树吗。那么就适适用递归来处理惩罚了
https://i-blog.csdnimg.cn/direct/7274e58f5d044046a00f058c4da78a77.png
二、快速排序的实现
public static void quickSort(int[] array) {
quick(array,0,array.length-1);
}
private static void quick(int[] array,int start,int end) {
//当start >= end了证明只有一个元素，或者没有左右树了也就不需要排序了
if(start >= end) {
return;
}
//按照基准值对array数组的 区间中的元素进行划分
//并返回当前基准值下标
int par = partitionHoare(array,start,end);
//遍历左边
quick(array,start,par-1);
//遍历右边
quick(array,par+1,end);
} 1.Hoare法找基准值
从逻辑上已经构造好了，就差具体的操纵了：
/**
* Hoare法
* @param array
* @param left
* @param right
* @return
*/
private static int partitionHoare(int[] array, int left,int right) {
//用来保存基准值下标
int i = left;
//记录基准值的值
int tmp = array;
//没交汇就继续循环
while (left < right) {
//left < right 必须写前面，防止6 7 8 9这种情况
//找到最右边小于基准值的值
while (left < right && array >= tmp){
right--;
}
//找到左边大于基准值的值
while (left < right && array <= tmp) {
left++;
}
//交换
swap(array,left,right);
}
//此时 left 和 right 交汇
swap(array,i,left);
//返回新的基准值下标
return left;
}
//交换函数
private static void swap(int[] array, int i, int j) {
int tmp = array;
array = array;
array = tmp;
} 测试代码：
public static void main(String[] args) {
int[] array = {10,9,7,2,3,8,1};
Sort.bubbleSort(array);
System.out.println(Arrays.toString(array));
} https://i-blog.csdnimg.cn/direct/5e73d88ef5c043b3aeec06883aa66aaf.png
出了刚才的Hoare法可以找基准值下面还有两种方法
2.挖坑法
先把基准值记录一下，再由right找到小于基准值的，然后left找到大于基准值的。两边来回填补。
最后tmp放入交汇处
https://i-blog.csdnimg.cn/direct/117e48025b3d4b40be187ce1273bf2eb.png
仔细的就会发现，这和Hoare法的数据顺序是不一样的。但也同样到达了效果
绘图的时候内里有一些空，其实是保存了原来数据的，但是为了更好的明白就没有保存。但是在代码上原有的数据一定会被覆盖。
代码：
/**
* 挖坑法
* @param array
* @param left
* @param right
* @return
*/
private static int partitionK(int[] array, int left,int right) {
//记录第一个坑，做为基准值
int tmp = array;
while (left < right) {
//找到最左边比基准值小的
while (left < right && array >= tmp) {
right--;
}
//左边小的数据先放入，已经挖好了坑tmp
array = array;
//找到最右边大于基准值的
while (left < right && array <= tmp) {
left++;
}
//放入右边的新坑
array = array;
}
//left 和 right 交汇，填空
array = tmp;
return left;
}
这是最紧张的一种方法，着重掌握
3.前后指针法(了解)
做选择题的时候可能会有。做题顺序： 挖坑法 > Hoare法 > 前后指针法
/**
* 前后指针法 (做为了解)
* @param array
* @param left
* @param right
* @return
*/
private static int partitionPre(int[] array, int left, int right) {
int prev = left ;
int cur = left+1;
while (cur <= right) {
if(array < array && array[++prev] != array) {
swap(array,cur,prev);
}
cur++;
}
swap(array,prev,left);
return prev;
}
快速排序如果不做优化，数据量大了以后他是很有可能会栈溢出的。
三、快速排序的优化
1.三数取中法
快排在能取到中间值时，最快。
https://i-blog.csdnimg.cn/direct/c082173078954d058f3b330293728e42.png
如果数组是一个有序的，那么就会开辟很多没必要的空间。浪费时间空间
https://i-blog.csdnimg.cn/direct/74c7ddefb55f40c88143682d9f524bee.png
那么三树取中就是：
用left 和 right 与 mid(数组中间下标的值) ，内里选居中的一个。做为基准值，并将他和left换一下
https://i-blog.csdnimg.cn/direct/d858f68d9b6d41d2a66f570316292733.png
此时3做为基准值https://i-blog.csdnimg.cn/direct/aec4975fa18b49f9b645d2e3b71ad99f.png
那么最后基准值就在中间位置
写一个函数找到三个数之间中间的谁人数的下标:
//返回的是中间值小标
private static int midTreeNum(int[] array,int left,int right) {
int mid = left + right / 2;
if(array < array) {
if(array < array) {
return left;
}else if(array < array) {
return right;
}else {
return mid;
}
}else {
if(array < array) {
return right;
}else if(array < array) {
return left;
}else {
return mid;
}
}
} 边看图边看代码，假设array < array 假设array >= array
https://i-blog.csdnimg.cn/direct/eb621633b54c4e9886c428a5dd5e62c3.png
public static void quickSort(int[] array) {
quick(array,0,array.length-1);
}
private static void quick(int[] array,int start,int end) {
if(start >= end) {
return;
}
//三数取中法
int index = midTreeNum(array,start,end);
swap(array,index,start);
int par = partitionK(array,start,end);
quick(array,start,par-1);
quick(array,par+1,end);
} 结果：
https://i-blog.csdnimg.cn/direct/5e73d88ef5c043b3aeec06883aa66aaf.png
2.递归到小的子区间时，可以考虑使用插入排序
我们知道在趋于有序的时候插入排序最快，可以到达O(n)
public static void insertSortRange(int[] array,int left ,int right) {
for (int i = left+1; i <= right; i++) {
int tmp = array;
int j = i-1;
for (; j >= left; j--) {
// if(array > tmp) { 不稳定的写法
if(array > tmp) {
array = array;
}else {
//防止第一次array>tmp，从而j--到-1，执行不到这条语句
// array = tmp;
break;
}
}
array = tmp;
}
}
public static void quickSort(int[] array) {
quick(array,0,array.length-1);
}
private static void quick(int[] array,int start,int end) {
if(start >= end) {
return;
}
//当分出来的,数组越小。递归的次数就越多了，但是趋于有序了就可以用插入排序
if(end - start + 1 <= 10) {
insertSortRange(array,start,end);
return;
}
//三数取中法
int index = midTreeNum(array,start,end);
swap(array,index,start);
int par = partitionK(array,start,end);
quick(array,start,par-1);
quick(array,par+1,end);
}
四、非递归的写法
public static void quickSortNot(int[] array) {
Stack<Integer> stack = new Stack<>();
int left = 0;
int right = array.length-1;
int par = partitionK(array,left,right);
if(par > left+1) {
stack.push(left);
stack.push(par-1);
}
if(par < right-1) {
stack.push(par+1);
stack.push(right);
}
while (!stack.isEmpty()) {
right = stack.pop();
left = stack.pop();
par = partitionK(array,left,right);
//保证左边至少有两个元素
if(par > left+1) {
stack.push(left);
stack.push(par-1);
}
//保证右边至少有两个元素
if(par < right-1) {
stack.push(par+1);
stack.push(right);
}
}
} 用栈来模仿，用栈后进先出的原理来模仿实现。
快速排序最好还是用递归来实现
五、时间空间复杂度
优化后的
<u><strong>时间复杂度:O(n*log2n)
空间复杂度:O(log2n)
稳定性:不稳定</strong></u>
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]