快速排序
https://www.bilibili.com/video/BV1at411T75o
《算法：第4版》
快速排序的优点：
速度最快，原地排序
算法的时间复杂度是 NlgN
实现
数组版
public class Quick {
public static void sort(Comparable[] a) {
sort(a, 0, a.length - 1);
}
private static void sort(Comparable[] a, int lo, int hi) {
if (hi <= lo) {
return;
}
int j = partition(a, lo, hi); //切分
sort(a, lo, j - 1);
sort(a, j + 1, hi);
}
private static int partition(Comparable[] a, int lo, int hi) {
//将数组切分为a[lo……i-1]，a[i]，a[i+1……hi]
int i = lo, j = hi + 1; //左右扫描指针
Comparable v = a[lo]; //切分元素
while (true) {//扫描左右，检查扫描是否结束并交换元素
while (less(a[++i], v)) {
if (i == hi) {
break;
}
}
while (less(v, a[--j])) {
if (j == lo) {
break;
}
}
if (i >= j) {
break;
}
exch(a, i, j);
}//end while
exch(a, lo, j);
return j;
}//end partition
/**
* 自定义比较规则
*
* @param a
* @param b
* @return
*/
private static boolean less(Comparable a, Comparable b) {
boolean ret = false;
if (a instanceof Integer && b instanceof Integer) {
ret = (Integer) a < (Integer) b;
}
return ret;
}
private static void exch(Comparable[] a, int lo, int j) {
Comparable tmp = a[lo];
a[lo] = a[j];
a[j] = tmp;
}
public static void main(String[] args) {
Integer[] arr = {5,4,6,3,7,2,8,1,9,0};
Quick.sort(arr);
System.out.print(arr[0]);
for (int i = 1; i < arr.length; i++) {
System.out.printf(", %d", arr[i]);
}
System.out.println();
}
}
数组泛型版
public class Quick1<T> {
public static <T> void sort(Comparable<T>[] a) {
sort(a, 0, a.length - 1);
}
private static <T> void sort(Comparable<T>[] a, int lo, int hi) {
if (hi <= lo) {
return;
}
int j = partition(a, lo, hi); //切分
sort(a, lo, j - 1);
sort(a, j + 1, hi);
}
private static <T> int partition(Comparable<T>[] a, int lo, int hi) {
//将数组切分为a[lo……i-1]，a[i]，a[i+1……hi]
int i = lo, j = hi + 1; //左右扫描指针
Comparable v = a[lo]; //切分元素
while (true) {//扫描左右，检查扫描是否结束并交换元素
while (less(a[++i], v)) {
if (i == hi) {
break;
}
}
while (less(v, a[--j])) {
if (j == lo) {
break;
}
}
if (i >= j) {
break;
}
exch(a, i, j);
}//end while
exch(a, lo, j);
return j;
}//end partition
/**
* 自定义比较规则
*
* @param a
* @param b
* @return
*/
private static boolean less(Comparable a, Comparable b) {
return a.compareTo(b) == -1;
}
private static void exch(Comparable[] a, int lo, int j) {
Comparable tmp = a[lo];
a[lo] = a[j];
a[j] = tmp;
}
public static void main(String[] args) {
// Integer a = 1;
// Integer b = 2;
// boolean ret = less(a, b);
// System.out.println(ret);
Integer[] arr = {5,4,6,3,7,2,8,1,9,0};
Quick.sort(arr);
System.out.print(arr[0]);
for (int i = 1; i < arr.length; i++) {
System.out.printf(", %d", arr[i]);
}
System.out.println();
}
}
列表泛型版
package quicksort;
import java.util.Arrays;
import java.util.List;
public class QuickSort<T extends Comparable> {
private static <T extends Comparable> boolean less(T a, T b) {
return a.compareTo(b) == -1;
}
private static <T> void exch(List<T> a, int lo, int j) {
T tmp = a.get(lo);
a.set(lo, a.get(j));
a.set(j, tmp);
}
private static <T extends Comparable> int partition(List<T> a, int lo, int hi) {
//将数组切分为a[lo……i-1]，a[i]，a[i+1……hi]
int i = lo, j = hi + 1; //左右扫描指针
T v = a.get(lo); //切分元素
while (true) {//扫描左右，检查扫描是否结束并交换元素
while (true) {
++i;
if (!less(a.get(i), v)) {
break;
}
if (i == hi) {
break;
}
}
while (true) {
--j;
if (!less(v, a.get(j))) {
break;
}
if (j == lo) {
break;
}
}
if (i >= j) {
break;
}
exch(a, i, j);
}//end while
exch(a, lo, j);
return j;
}//end partition
public static <T extends Comparable> void sort(List<T> list) {
sort(list, 0, list.size() - 1);
}
private static <T extends Comparable> void sort(List<T> a, int lo, int hi) {
if (hi <= lo) {
return;
}
int j = partition(a, lo, hi); //切分
sort(a, lo, j - 1);
sort(a, j + 1, hi);
}
public static void main(String[] args) {
List<Integer> list = Arrays.asList(5,4,6,3,7,2,8,1,9,0);
QuickSort.sort(list);
System.out.print(list.get(0));
for (int i = 1; i < list.size(); i++) {
System.out.printf(", %d", list.get(i));
}
System.out.println();
}
}
效率增强版列表
对于小数组，快速排序比插入排序慢；
因为递归，快速排序的sort()方法在小数组中也会调用自己。
因此，在排序小数组时应该切换到插入排序。一般来说它们能将性能提升20%~30%。