基础排序之快速排序
2019-12-23 本文已影响0人
JunL_Dev
Start
前言
快速排序由 C. A. R. Hoare 在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。《百度百科》
1. 第一趟快速排序
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小。
百度百科的话并没有说到重点，更简单的理解是这样的：在数组中找一个支点(任意)，经过一趟排序后，支点左边的数都要比支点小，支点右边的数都要比支点大！
现在我们有一个数组：int arr[]={1,4,5,67,2,7,8,6,9,44};
经过一趟排序之后，如果我选择数组中间的数作为支点：7(任意的)，那么第一趟排序后的结果是这样的：{1,4,5,6,2,7,8,67,9,44}
那么就实现了支点左边的数比支点小，支点右边的数比支点大。
2. 递归分析与代码实现
现在我们的数组是这样的：{1,4,5,6,2,7,8,67,9,44}，既然我们比7小的在左边，比7大的在右边，那么我们只要将”左边“的排好顺序，又将”右边“的排好序，那整个数组是不是就有序了？想一想，是不是？
又回顾一下递归：”左边“的排好顺序，”右边“的排好序，跟我们第一趟排序的做法是不是一致的？
只不过是参数不一样：第一趟排序是任选了一个支点，比支点小的在左边，比支点大的在右边。那么，我们想要”左边“的排好顺序，只要在”左边“部分找一个支点，比支点小的在左边，比支点大的在右边。
…………..
在数组中使用递归依照我的惯性，往往定义两个变量：L 和 R，L 指向第一个数组元素，R 指向在最后一个数组元素。
递归出口也很容易找到：如果数组只有一个元素时，那么就不用排序了。
所以，我们可以写出这样的代码：
public class QuickSort {
public static void main(String[] args) {
int[] ints = SortManager.sortArr;
quickSort(ints, 0, ints.length - 1);
for (int i = 0; i < ints.length; i++) {
System.out.println("输出结果：" + ints[i]);
}
}
public static void quickSort(int[] arr, int L, int R) {
int i = L, j = R;
//支点
int pivot = arr[(L + R) / 2];
//左右两端进行扫描，只要两端还没有交替，就一直扫描
while (i <= j) {
//寻找直到比支点大的数
while (pivot > arr[i])
i++;
//寻找直到比支点大的数
while (pivot < arr[j])
j--;
//此时已经分别找到了比支点小的数(右边)、比支点大的数(左边)，它们进行交换
if (i <= j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
//上面一个while保证了第一趟排序支点的左边比支点小，支点的右边比支点大了。
//“左边”再做排序，直到左边剩下一个数(递归出口)
if (L < j) {
quickSort(arr, L, j);
}
//“右边”再做排序，直到右边剩下一个数(递归出口)
if (i < R) {
quickSort(arr, i, R);
}
}
}
3. 快速排序优化
3.1 普通快速排序
找一个基准值 base，然后一趟排序后让 base 左边的数都小于 base，base 右边的数都大于等于 base。再分为两个子数组的排序。如此递归下去。
public class QuickSort {
public static <T extends Comparable<? super T>> void sort(T[] arr) {
sort(arr, 0, arr.length - 1);
}
public static <T extends Comparable<? super T>> void sort(T[] arr, int left, int right) {
if (left >= right) return;
int p = partition(arr, left, right);
sort(arr, left, p - 1);
sort(arr, p + 1, right);
}
private static <T extends Comparable<? super T>> int partition(T[] arr, int left, int right) {
T base = arr[left];
int j = left;
for (int i = left + 1; i <= right; i++) {
if (base.compareTo(arr[i]) > 0) {
j++;
swap(arr, j, i);
}
}
swap(arr, left, j);
return j;//返回一趟排序后基准值的下角标
}
public static void swap(Object[] arr, int i, int j) {
if (i != j) {
Object temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
private static void printArr(Object[] arr) {
for (Object o : arr) {
System.out.print(o);
System.out.print("\t");
}
System.out.println();
}
public static void main(String args[]) {
Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};
printArr(arr);//3 5 1 7 2 9 8 0 4 6
sort(arr);
printArr(arr);//0 1 2 3 4 5 6 7 8 9
}
}
3.2 两路快排
在最开始的普通快速排序说过，让基准值 base 左边的都比 base 小，而 base 右边的都大于等于 base。等于 base 的这些会聚集到右侧(或者稍微改改大小关系就会聚集到左侧)。总之就会聚集到一边。这样在数组中重复数字很多的时候，就又会导致两边子递归规模差距悬殊的情况。这时想把等于 base 的那些数分派到 base 两边，而不是让他们聚集到一起。
public class QuickSort {
public static <T extends Comparable<? super T>> void sort(T[] arr) {
sort(arr, 0, arr.length - 1);
}
/**
* @param arr 待排序的数组
* @param left 左闭
* @param right 右闭
* @param k 当快排递归到子问题的规模 <= k 时，采用插入排序优化
* @param <T> 泛型，待排序可比较类型
*/
public static <T extends Comparable<? super T>> void sort(T[] arr, int left, int right) {
if (left >= right) return;
int p = partition(arr, left, right);
sort(arr, left, p - 1);
sort(arr, p + 1, right);
}
private static <T extends Comparable<? super T>> int partition(T[] arr, int left, int right) {
//排序前，先让基准值和随机的一个数进行交换。这样，基准值就有随机性。
//就不至于在数组相对有序时，导致左右两边的递归规模不一致，产生最坏时间复杂度
swap(arr, left, (int) (Math.random() * (right - left + 1) + left));
T base = arr[left];//基准值，每次都把这个基准值抛出去，看成[left+1.....right]左闭右闭区间的排序
int i = left + 1; //对于上一行提到的[left+1.....right]区间，i表示 [left+1......i)左闭右开区间的值都小于等于base。
int j = right;//对于上二行提到的[left+1.....right]区间，j表示 (j......right]左开右闭区间的值都大于等于base。
while (true) {
//从左到右扫描，扫描出第一个比base大的元素，然后i停在那里。
while (i <= right && arr[i].compareTo(base) < 0) i++;
//从右到左扫描，扫描出第一个比base小的元素，然后j停在那里。
while (j >= left && arr[j].compareTo(base) > 0) j--;
if (i > j) {//虽说是i>j，但其实都是以j=i-1为条件结束的
break;
}
swap(arr, i++, j--);
}
swap(arr, left, j);
return j;//返回一躺排序后，基准值的下角标
}
public static void swap(Object[] arr, int i, int j) {
if (i != j) {
Object temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
private static void printArr(Object[] arr) {
for (Object o : arr) {
System.out.print(o);
System.out.print("\t");
}
System.out.println();
}
public static void main(String args[]) {
Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};
printArr(arr);//3 5 1 7 2 9 8 0 4 6
sort(arr);
printArr(arr);//0 1 2 3 4 5 6 7 8 9
}
}
3.3 两路快排 不用 swap, 用直接赋值
public class QuickSort {
public static <T extends Comparable<? super T>> void sort(T[] arr) {
sort(arr, 0, arr.length - 1);
}
/**
* @param arr 待排序的数组
* @param left 左闭
* @param right 右闭
* @param <T> 泛型，待排序可比较类型
*/
public static <T extends Comparable<? super T>> void sort(T[] arr, int left, int right) {
if (left >= right) return;
int p = partition(arr, left, right);
sort(arr, left, p - 1);
sort(arr, p + 1, right);
}
private static <T extends Comparable<? super T>> int partition(T[] arr, int left, int right) {
//排序前，先让基准值和随机的一个数进行交换。这样，基准值就有随机性。
//就不至于在数组相对有序时，导致左右两边的递归规模不一致，产生最坏时间复杂度
swap(arr, left, (int) (Math.random() * (right - left + 1) + left));
T base = arr[left];//基准值，每次都把这个基准值抛出去，看成[left+1.....right]左闭右闭区间的排序
int i = left; //对于上一行提到的[left+1.....right]区间，i表示 [left+1......i)左闭右开区间的值都小于等于base。
int j = right;//对于上二行提到的[left+1.....right]区间，j表示 (j......right]左开右闭区间的值都大于等于base。
while (i < j) {
//从右到左扫描，扫描出第一个比base小的元素，然后j停在那里。
while (j > i && arr[j].compareTo(base) > 0) j--;
arr[i] = arr[j];
//从左到右扫描，扫描出第一个比base大的元素，然后i停在那里。
while (i < j && arr[i].compareTo(base) < 0) i++;
arr[j] = arr[i];
}
arr[j] = base;
return j;//返回一躺排序后，基准值的下角标
}
public static void swap(Object[] arr, int i, int j) {
if (i != j) {
Object temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
private static void printArr(Object[] arr) {
for (Object o : arr) {
System.out.print(o);
System.out.print("\t");
}
System.out.println();
}
public static void main(String args[]) {
Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};
printArr(arr);//3 5 1 7 2 9 8 0 4 6
sort(arr);
printArr(arr);//0 1 2 3 4 5 6 7 8 9
}
}
参考文章：
https://www.cnblogs.com/noKing/archive/2017/11/29/7922397.html
申明：开始的图片来源网络，侵删
