它的基本思想是： 选择一个基准数，通过一趟排序将要排序的数据分割成独立的两部分； 其中左部分数据小于这个基准数,右边部分数据都大于这个基准数,也就是右部分大于左部分。然后，再按此方法对这两部分数据分别进行排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 简单讲每次一个小排序都会选出等于区,然后排小于区和大于区
快排分两种
- 经典快排 比较基准为数组最后一个数
- 随机快排 比较基准为数组内随机一个数
快排时间复杂度O(N*logN) 额外空间复杂度O(logN)
快排额外空间复杂度来自存储等于区域的数组
一经典快排
代码语言：javascript复制package com.day1.sort;
import com.day1.comparator.ArrayComparator;
public class QuickSort extends ArrayComparator {
public static void quickSort(int[] arr,int L,int R){ //在L到R上排序
if(L<R){
int[] ints = partition(arr, L, R);
quickSort(arr,L,ints[0]-1);
quickSort(arr,ints[1] 1,R);
}
}
//以最后一个位置上的数做划分
//将小于最后一个数的放左边,大于最后一个数的放右边,等于的放中间
//返回排序后等于最后一个数的的左索引和右索引
public static int[] partition(int[] arr, int L, int R) {
int less = L - 1; //小于arr[R]的最后一个索引
int more = R; //大于arr[R]的第一个索引
int curr=L;
while (curr < more) {
if (arr[curr] < arr[R]) {
swap(arr, less, curr );
} else if (arr[curr] >arr[R]) {
swap(arr, --more, curr);
} else {
curr ;
}
}
swap(arr,R,curr);
return new int[] { less 1, more};
}
}快速排序的时间复杂度在最坏情况下是O(N2)，平均的时间复杂度是O(N*lgN)。 这句话很好理解：假设被排序的数列中有N个数。遍历一次的时间复杂度是O(N)，需要遍历多少次呢？至少lg(N 1)次，最多N次。
- 为什么最少是lg(N 1)次？快速排序是采用的分治法进行遍历的，我们将它看作一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的定义，它的深度至少是lg(N 1)。因此，快速排序的遍历次数最少是lg(N 1)次。
- 为什么最多是N次？这个应该非常简单，还是将快速排序看作一棵二叉树，它的深度最大是N。因此，快读排序的遍历次数最多是N次。
由此可见 经典快排会随着我们数据的情况不同时间复杂度不同,这就造成了可能出现极端情况
二随机快排
跟经典快排不同的情况是我们的比较基准不是最后一个数,而是随机选一个数字.
与经典排序相比只多了一行代码`
代码语言：javascript复制 swap(arr, L (int) (Math.random() * (R - L 1)), R);在L~R数组里随机取一个数放到最后作为比较基准
全文代码
代码语言：javascript复制package com.day1.sort;
import com.day1.comparator.ArrayComparator;
public class QuickSort extends ArrayComparator {
public static void quickSort(int[] arr,int L,int R){ //在L到R上排序
if (L<R){
//在L~R数组里随机取一个数放到最后作为比较基准
swap(arr, L (int) (Math.random() * (R - L 1)), R);
int[] ints = partition(arr, L, R);
quickSort(arr,L,ints[0]-1);
quickSort(arr,ints[1] 1,R);
}
}
//以最后一个位置上的数做划分
//将小于最后一个数的放左边,大于最后一个数的放右边,等于的放中间
//返回排序后等于最后一个数的的左索引和右索引
public static int[] partition(int[] arr, int L, int R) {
int less = L - 1; //小于arr[R]的最后一个索引
int more = R; //大于arr[R]的第一个索引
int curr=L;
while (curr < more) {
if (arr[curr] < arr[R]) {
swap(arr, less, curr );
} else if (arr[curr] >arr[R]) {
swap(arr, --more, curr);
} else {
curr ;
}
}
swap(arr,R,curr);
return new int[] { less 1, more};
}
}对partition()函数有疑问可以查看荷兰国旗问题
点击: 荷兰国旗问题
