浅析快速排序算法
浅析快速排序算法
快速排序（Quick Sort）采用了分治（Divide and Conquer）和递归（Recursion）的思想
一、算法描述
- 选定Pivot中心轴；
- 将大于Pivot的数字放在Pivot的右边；
- 将小于Piovt的数字放在Pivot的左边；
- 分别对左右子序列重复前三步操作。
二、举个栗子
例如对数组 [19 55 8 16 2 6] 进行快速排序，我们选取19为Pivot，将大于19的放在Pivot的右边，小于19的放在Pivot的左边。
设置L为左下标，R为右下标。分别移动L和R，最后L和R会在数组某个位置相遇，相遇之后就把Pivot放在相遇的位置。
第一趟：移动R下标，可以发现R所指的元素是6，6<19 所以把6放在最左边。
第二趟：交替移动L下标，可以发现L所指元素是55，55>19 所以把55放在最右边。
第三趟：移动R下标，可以发现R所指元素是2，2<19 所以把2放在最左边。
第四趟：移动L下标，可以发现L所指元素是8，8<19 所以8不需要移动，因为他本来就在左边。
第五趟：如果没有对该数进行移动，那么继续移动当前下标。所以继续移动L下标。可以发现L所指元素是16，16<19 所以16不需要移动，因为他本来就在左边。
第六趟：没有对该数进行移动，所以继续移动L下标。最终L下标和R下标进行相遇重合。这个时候就把19放在两个下标重合的位置。
经过上面这样我们就完成了第一次排序。完成第一次排序我们可以发现左子序列全部比19小，右子序列全部比19大。
接下来在分别对左子序列和右子序列（当序列长度为1，则不需要继续排序，所以右子序列不需要排序）重复以上操作进行排序。最后使得整个数组有序。
三、算法实现
import java.util.Arrays;
public class quicksort {
public static void main(String[] args) {
int arr[] = {19, 55, 8, 16 ,2 ,6};
sort(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
// arr是要排序的数组，arr[low] - arr[high]是要排序的哪一段
public static void sort(int[] arr,int low, int high){
if (low >= high){
return;
}
// L,R
int L = low;
int R = high;
//Pivot
int Pivot = arr[L];
while (L < R){
while (arr[R] > Pivot && L<R){
R --;
}
if (L < R){
int t ;
t = arr[R];
arr[R] = arr[L];
arr[L] = t;
}
while (arr[L] <= Pivot && L<R){
L ++;
}
if (L < R){
int t;
t = arr[L];
arr[L] = arr[R];
arr[R] = t;
}
}
//对基准左侧的集合重复操作
sort(arr,low,L-1);
//对基准右侧的集合重复操作
sort(arr,L+1,high);
}
}输出：
四、算法分析
时间复杂度：O(nlogn)
空间复杂度：快速排序在每次分割的过程中，需要 1 个空间存储基准值。而快速排序的大概需要 logn次的分割处理，所以空间复杂度是 logn。
稳定性：快速排序无法保证相等的元素的相对位置不变，因此它是不稳定的排序算法
五、适用场景
一般应用中，比其他排序快得多，适用于数组长度比较大的情况，对于小数组，快速排序比插入排序慢。
腾讯云开发者
