快速排序和冒泡排序類似担巩，都是基于交換的思想薇宠，快速排序?qū)γ芭菖判蜻M(jìn)行了優(yōu)化购对，從而更加快速高效（從名字就可以看出應(yīng)該很牛批...）
算法基本思想：
- 首先選取一個(gè)基準(zhǔn)值徐钠，然后根據(jù)這個(gè)基準(zhǔn)將數(shù)組分為了左右兩部分
- 將這左右兩個(gè)部分中的數(shù)據(jù)，和基準(zhǔn)值做比較力图，大于基準(zhǔn)值的放在右邊步绸，小于基準(zhǔn)值的放在左邊
- 此時(shí)對于基準(zhǔn)值而言，已經(jīng) “排序 ” 完成吃媒，即“比我小的全在我左邊瓤介，比我大的全在我右邊”
- 然后再對左右兩部循環(huán)進(jìn)行同樣的操作（遞歸），最后整個(gè)數(shù)組的排序就完成了赘那。
示意圖
代碼實(shí)現(xiàn)：
import java.util.Arrays;
/**
* Created by noonbiteun
* Date: 2017/7/31
*/
public class QuickSort {
public static void sort(int[] arr, int left, int right) {
int base = arr[(left + right) / 2];//基準(zhǔn)數(shù)
int lt = left;//左端索引
int rt = right;//右端索引
int tmp;//數(shù)據(jù)暫存刑桑，交換時(shí)使用
while (lt < rt) {
while (arr[lt] < base) {
//左索引往后移，直到找到不小于base的數(shù)才停下來
lt++;
}
while (arr[rt] > base) {
//右索引往前移募舟，直到找到比不大于base的數(shù)才停下來
rt--;
}
if (lt <= rt) {
//交換此時(shí)兩個(gè)索引所指的數(shù)
tmp = arr[lt];
arr[lt] = arr[rt];
arr[rt] = tmp;
//索引更新
lt++;
rt--;
}
}
if (lt == rt) {
lt++;
rt--;
}
if (left < rt) {
//遞歸祠斧，排左索引前面的數(shù)
sort(arr, left, --lt);
}
if (right > lt) {
//遞歸，排右索引后面的數(shù)
sort(arr, ++rt, right);
}
}
public static void main(String[] args) {
int[] arr = new int[15];
//初始化數(shù)組
for (int i = 0; i < 15; i++) {
arr[i] = (int) (Math.random() * (100 + 1));
}
System.out.println("排序前數(shù)據(jù)： "+ Arrays.toString(arr));
QuickSort.sort(arr, 0, arr.length - 1);
System.out.println("排序后數(shù)據(jù)： "+ Arrays.toString(arr));
}
}
輸出結(jié)果：
運(yùn)行結(jié)果
