一网打尽快排
快速排序作为十大经典排序算法之一,在面试场中屡屡出现,不是要求手写快速排序,就是快速排序的变种,为了方便复习,特此总结快速排序
1.初出茅庐
给定一个数组arr，和一个数num，请把小于等于num的数放在数组的左边，大于num的数放在数组的右边。
要求额外空间复杂度O(1)，时间复杂度O(N)
- 用rightBound记录小于等于num区域的右边界,初始值为-1
- 从头遍历数组,如果arr[i] <=num, 那么把arr[i]和小于等于区域的下一个数交换,也就是让arr[i]和下标为rightBound + 1的数交换,然后i++,rightBound++;
- 如果arr[i] > num, 则只让i++;
代码:
public static void test1(int [] arr , int num){
int rightBound = -1,i = 0;
while (i <arr.length){
if(arr[i] <= num) swap(arr,++rightBound,i++);
else i++;
}
}
public static void swap(int [] arr, int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
output:
3 5 4 3 5 7 6 8
2.小试牛刀
荷兰国旗问题
给定一个数组arr，和一个数num，请把小于num的数放在数组的 左边，等于num的数放在数组的中间，大于num的数放在数组的 右边。要求额外空间复杂度O(1)，时间复杂度O(N)
这题是上一题的加强版
- 用rightBound记录小于num区域的右边界,初始值为-1,用leftBound记录大于区域的左边界,初始值为arr.length;
- 从头遍历数组,如果arr[i] <num, 那么把arr[i]和小于等于区域的下一个数交换,也就是让arr[i]和下标为rightBound + 1的数交换,然后i++,rightBound++;
- 如果arr[i] = num, 则只让i++;
- arr[i] > num, 那么把arr[i]和大于区域的下一个数交换,也就是让arr[i]和下标为leftBound - 1的数交换,然后i原地不动,leftBound–;
- 当i等于leftBound时循环结束
(为什么i要原地不动,因为arr[i]和下标为leftBound - 1的数交换后,此时i下标对应的数不知道大小,需要再次比较)
解法的实质是利用双指针把数组中等于num的数往中间挤
代码
public static void heLanFlag(int [] arr, int num){
int rightBound = -1, leftBound = arr.length;
int i = 0;
while(i < leftBound){
if(arr[i] < num) swap(arr,++rightBound,i++);
else if(arr[i] == num) i++;
else swap(arr,--leftBound,i);
}
}
public static void swap(int [] arr, int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
output:
3 3 4 5 5 7 8 6
3.炉火纯青(快排)
利用荷兰国旗进行分区,分为3个区域(< ,= , >)比分为2个区域(<= 和 >)要快
这种算法最坏情况下复杂度是O(n2)
因为
1,4,3,5,7,6,8,9这种情况,进行快排,每次拿数组最后一个数进行划分,划分后没有右侧大于区域,即都只搞定当前一个数,最坏时间复杂度是O(n2)
代码
public static void quickSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
quickSort(arr, 0, arr.length - 1);
}
public static void quickSort(int[] arr, int l, int r) {
if (l < r) {
//int[] p 容量为2,返回的是等于区域的左右边界
int[] p = partition(arr, l, r);
quickSort(arr, l, p[0] - 1);
quickSort(arr, p[1] + 1, r);
}
}
public static int[] partition(int[] arr, int l, int r) {
int rightBound = l - 1;
int leftBound = r;
while (l < leftBound) {
if (arr[l] < arr[r]) {
swap(arr, ++rightBound, l++);
} else if (arr[l] > arr[r]) {
swap(arr, --leftBound, l);
} else {
l++;
}
}
swap(arr, leftBound, r);
//返回的是相等值的左,右边界
return new int[] { rightBound + 1, leftBound };
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
4.登峰造极(随机快排)
上面的快速排序由于每次都是拿区域内的最后一个数组按照荷兰国旗的方式进行划分(这里称为分区),因此如果当数据状况是1,4,3,5,7,6,8,9,拿9进行划分,划分区域后只有两个区域,那么时间复杂度会达到O(n2);
因此快速排序改进版是基于随机的思想
从数组中等概率选择一个数与区域的最后一个数进行交换,然后再按照交换后数组的最后一个数进行分区,这样好情况和坏情况就是等概率的!!
因次只需要在前者的基础上随机选择选择一个数即可
public static double random()
返回一个double值为正号，大于等于0.0 ，小于1.0 。返回的值是从该范围（大约）均匀分布而伪随机选择的。
public static void quickSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
quickSort(arr, 0, arr.length - 1);
}
public static void quickSort(int[] arr, int l, int r) {
if (l < r) {
//Math.random() 返回double大于或等于 0.0并小于 1.0 。
swap(arr, l + (int) (Math.random() * (r - l + 1)), r);
int[] p = partition(arr, l, r);
quickSort(arr, l, p[0] - 1);
quickSort(arr, p[1] + 1, r);
}
}
public static int[] partition(int[] arr, int l, int r) {
int rightBound = l - 1;
int leftBound = r;
while (l < leftBound) {
if (arr[l] < arr[r]) {
swap(arr, ++rightBound, l++);
} else if (arr[l] > arr[r]) {
swap(arr, --leftBound, l);
} else {
l++;
}
}
swap(arr, leftBound, r);
//返回的是相等值的左,右边界
return new int[] { rightBound + 1, leftBound };
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
根据Master公式并且经过概率累加计算而得(需要数学推导证明)
时间复杂度分析O(N*logN)
空间复杂度分析O(logN)