作者：敲代码の流川枫
博客主页：流川枫的博客
专栏：和我一起学java
语录：Stay hungry stay foolish
工欲善其事必先利其器，给大家介绍一款超牛的斩获大厂offer利器——牛客网
点击免费注册和我一起刷题吧
文章目录
1. 算法思想
2. 算法图解
3. 代码实现
4. 快排特点及性能
1. 算法思想
快速排序的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据比另一部分的所有数据要小，再按这种方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，使整个数据变成有序序列
步骤：
1. 选定Pivot为中心轴
2. 将大于Pivot的数字放在Pivot的右边
3. 将小于Pivot的数字放在Pivot的左边
4. 分别对左右子序列重复前三步操作
2. 算法图解
int[] array = {25,100,9,20,1,8};以数组array为例图解快速排序
1. 为了方便起见，我们每次都选取最左边的数字为中心轴Pivot，要把小于19的数字放在19左边，把大于19的数字放在19右边，如何达到目的呢？我们设置了L和R两个下标如图
2. L从左向右移动，一旦发现比Pivot大的数字，将它放在该序列右边；R从右向左移动，一旦发现有数字小于Pivot，则把数字放到该序列左边，最终LR会在某个位置相遇重合，将Pivot放在这个位置，至此第一次排序结束。此时左边的数全小于Pivot，右边的数全大于Pivot，形成左右子序列
R指向8，8<25，将它放到序列左边L处
L和R交替移动，L指向100，100>25，将它移动到序列右边R处
R和L交替移动，R向左移动，指向1，1<25，将它移动到序列左边L处
L和R交替移动，L指向9，9<25，将它放在原位，L继续移动
L向左移动指向20，20<25，将他放在原位，L继续左移
L和R相遇，将Povit放在相遇的位置，并且分出来了左右子序列如图：
3. 现在对左子序列和右子序列进行同样的操作，因为右子序列只有一个数，默认有序
4. 对右子序列继续排序：
5. 至此排序完成：
3. 代码实现
代码：
public class QuickSort {
private int[] array;
public QuickSort(int[] array){
this.array = array;
}
public void sort() {
quickSort(array,0,array.length-1);
}
public void print() {
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
}
public void quickSort(int[] array,int left,int right) {
if(left<right){
int Povit = array[left];
int L = left;
int R = right;
while(L<R){
while(L < R && array[R]>Povit){
R--;
}
if(L < R) {
array[L] = array[R];
L++;
}
while(L < R && array[L] < Povit){
L++;
}
if(L < R){
array[R] = array[L];
R--;
}
}
array[R] = Povit;
quickSort(array,left,R-1);
quickSort(array,R+1,right);
}
}
}
class SortTest {
public static void main(String[] args) {
testQuickSort();
}
/**
* 快速排序
*/
private static void testQuickSort() {
int[] array = {25,100,9,20,1,8};
QuickSort quickSort = new QuickSort(array);
quickSort.sort();
quickSort.print();
}
}
结果：
4. 快排特点及性能
特点：
快速排序是在冒泡排序的基础上改进而来的，冒泡排序每次只能交换相邻的两个元素，而快速排序是跳跃式的交换
快速排序是一个不稳定的算法，在经过排序之后，可能会对相同值的元素的相对位置造成改变
快速排序基本上被认为是相同数量级的所有排序算法中，平均性能最好的
性能：
时间复杂度
快速排序在最坏情况下的时间复杂度和冒泡排序一样，是
O(n2)，实际上每次比较都需要交换，但是这种情况并不常见，思考一下如果每次比较都需要交换，那么数列的平均时间复杂度是O(nlogn)，事实上在大多数时候，排序的速度要快于这个平均时间复杂度。这种算法实际上是一种分治法思想，也就是分而治之，把问题分为一个个的小部分来分别解决，再把结果组合起来空间复杂度
快速排序只是使用数组原本的空间进行排序，所以所占用的空间应该是常量级的，但是由于每次划分之后是递归调用，所以递归调用在运行的过程中会消耗一定的空间，在一般情况下的空间复杂度为
O(logn)，在最差的情况下，若每次只完成了一个元素，那么空间复杂度为O(n)。所以我们一般认为快速排序的空间复杂度为O(logn)
“ 本期的分享就到这里了， 记得给博主一个三连哈，你的支持是我创作的最大动力！
相关文章
