快速排序基本思想
輸入代排數(shù)組——>選取基準(zhǔn)元——>執(zhí)行劃分操作——>遞歸對兩個(gè)數(shù)組進(jìn)行快速排序
1怎囚、比如這里輸入序列{72，6摔踱，57岭参，88，60包晰，42湿镀，83，73伐憾，48}
2勉痴、下面選取基準(zhǔn)元，這里選取72
選取基準(zhǔn)元后树肃，會用另一個(gè)空間存放基準(zhǔn)元的數(shù)據(jù)蒸矛，用兩個(gè)指針分別指向數(shù)組最前端與最后端，從最后端開始比較，如果比基準(zhǔn)元72小雏掠，則放在基準(zhǔn)元前面斩祭，也就是將數(shù)據(jù)放在前端指針指的數(shù)據(jù)，這里是48<72所以要放在第一個(gè)位置乡话。
3摧玫、執(zhí)行劃分操作
再移動前端指針，依次進(jìn)行數(shù)據(jù)的改變绑青，當(dāng)前后指針指向同一個(gè)數(shù)據(jù)時(shí)诬像，就是劃分結(jié)束，將基準(zhǔn)元的數(shù)據(jù)放在指針的位置闸婴。
4坏挠、遞歸對兩個(gè)數(shù)組進(jìn)行快速排序
現(xiàn)在依據(jù)第一次的基準(zhǔn)元，將數(shù)組分為左右兩個(gè)部分邪乍，分別對兩個(gè)數(shù)組進(jìn)行快速排序降狠，基準(zhǔn)元選擇第一個(gè)數(shù)字，也就是48庇楞、83作為基準(zhǔn)元喊熟。
執(zhí)行劃分后得到上圖，依次類推執(zhí)行快速排序姐刁。
經(jīng)過三次劃分后芥牌，得到了有序的序列。
快速排序優(yōu)化方法
選擇基準(zhǔn)的方式——固定位置
思想：取待排序列的第一個(gè)或最后一個(gè)作為基準(zhǔn)
就是我們剛才舉列子的方式聂使，這種方式在最好的情況下壁拉，時(shí)間復(fù)雜度是O(nlgn)，不過在最壞情況下柏靶，也就是這個(gè)序列本身是有序的時(shí)候弃理，這個(gè)排序就會變成冒泡排序，時(shí)間復(fù)雜度為O(n2)
選擇基準(zhǔn)的方式——隨機(jī)選擇基準(zhǔn)
思想：取待排序列中的任意一個(gè)作為基準(zhǔn)
簡單分析：
基準(zhǔn)元的位置是隨機(jī)的屎蜓，則出現(xiàn)最壞情況的概率大大降低痘昌，最好情況依然是O(nlgn)
在整個(gè)數(shù)組數(shù)字全相等時(shí)，仍然是 最壞情況炬转，時(shí)間復(fù)雜度是O(n2)
選擇基準(zhǔn)的方式——“三數(shù)取中”選取基準(zhǔn)元
這樣可以盡可能讓劃分得到的兩個(gè)序列盡可能等長辆苔，會降低快速排序的時(shí)間復(fù)雜度。
快速排序+插入排序
原因：
對于很小和部分有序的數(shù)組扼劈，快排不如插排好
“聚key”方法
思想：在一次分割結(jié)束后驻啤，可以把與Key相等的元素聚在一起，繼續(xù)下次分割時(shí)荐吵，不用再對與key相等元素分割骑冗。
這里給出序列{1赊瞬，4，6贼涩，7巧涧，6，6遥倦，7谤绳，6，8谊迄，6}闷供，
用三數(shù)取中的方法會選擇出基準(zhǔn)元6烟央，最后劃分出左右兩個(gè)子序列统诺。
這個(gè)方法與其他方法的不同，就是在移動指針時(shí)疑俭，如果指針的值粮呢，和基準(zhǔn)元一樣，比如這里指向6钞艇，那就會將這個(gè)數(shù)移動到兩端（哪一邊的指針指向的啄寡，就移動到哪一段）。
再將兩端的key值哩照，移動到與基準(zhǔn)相等的地方挺物，最后劃分得到左右兩個(gè)子序列。
采用這種方法飘弧，能減少迭代次數(shù)识藤，提高效率。
快排及其優(yōu)化-總結(jié)
在優(yōu)化方面次伶，主要集中在選取基準(zhǔn)元和執(zhí)行劃分操作上痴昧。
