快速排序代碼有幾個(gè)坑需要注意：
1豁鲤，partition的過程比較復(fù)雜，很容易出錯(cuò)，某些行數(shù)很短的代碼很簡(jiǎn)潔但是不容易看懂典挑，不如采用簡(jiǎn)單直觀的方法：用第一個(gè)元素作為軸、partition結(jié)束之后再把軸swap到中間
2啦吧，選軸如果固定選第一個(gè)您觉，可能進(jìn)入worst case，復(fù)雜度退化為N2授滓，使用隨機(jī)選軸來解決這個(gè)問題
3琳水，如果有大量重復(fù)元素，快速排序同樣會(huì)陷入N2般堆，此時(shí)需要使用三向快速排序：將數(shù)組分為小于在孝、等于、大于軸的三部分郁妈，我們可以通過兩步partition來完成：首先分為小于等于浑玛、大于的兩部分，然后再進(jìn)行一次partition噩咪，拆分成三部分顾彰。
package com.mocyx.algs.sort;
import java.util.Random;
import java.util.Scanner;
/**
* @author Administrator
*/
public class FastSort {
static int[] arrs;
static void swap(int a, int b) {
int v = arrs[a];
arrs[a] = arrs[b];
arrs[b] = v;
}
static Random random = new Random(System.currentTimeMillis());
static void choosePovit(int s, int e) {
int m = s + random.nextInt(e - s);
swap(s, m);
}
/**
* @param s
* @param e
* @param leftEqual true表示把相等的放在左邊，false表示把相等的放在右邊
* @return
*/
static int partition(int s, int e, boolean leftEqual) {
int i = s + 1;
int j = e;
int pivotValue = arrs[s];
while (true) {
if (leftEqual) {
while (i <= e && arrs[i] <= pivotValue) {
i += 1;
}
while (j >= s + 1 && arrs[j] > pivotValue) {
j -= 1;
}
} else {
while (i <= e && arrs[i] < pivotValue) {
i += 1;
}
while (j >= s + 1 && arrs[j] >= pivotValue) {
j -= 1;
}
}
if (i <= e && j >= s + 1 && i <= j) {
swap(i, j);
i += 1;
j -= 1;
}else {
break;
}
}
swap(s, i - 1);
return i - 1;
}
static void sort(int s, int e, int depth) {
if (s >= e) {
return;
}
//隨機(jī)選擇軸胃碾，避免進(jìn)入worst case
choosePovit(s, e);
//第一次partition涨享，小于等于軸的置換到軸右邊
int mr = partition(s, e, true);
//第二次partition，把等于軸的置換到右側(cè)
swap(s, mr);
int ml = partition(s, mr, false);
//現(xiàn)在數(shù)組分為三塊：小于軸 等于軸 大于軸的
sort(s, ml - 1, depth + 1);
sort(mr + 1, e, depth + 1);
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int c = scanner.nextInt();
arrs = new int[c];
for (int i = 0; i < c; i++) {
arrs[i] = scanner.nextInt();
}
sort(0, arrs.length - 1, 1);
StringBuilder stringBuilder = new StringBuilder();
for (int i = 0; i < arrs.length; i++) {
stringBuilder.append(String.format("%d ", arrs[i]));
}
System.out.print(stringBuilder.toString());
}
}
