今天開始復(fù)習(xí)一下排序，其實這個最近都有再撿起來練艾君，畢竟太久遠(yuǎn)拿起來還挺不容易的采够。
簡單說一下——自己復(fù)習(xí)排序的時候理解是這樣的：基本的排序分為三類：交換排序、選擇排序冰垄、插入排序蹬癌。用一張圖表示一下：
不得不說，我畫的圖簡直太丑了......
將就看一下吧虹茶，大概是這樣的逝薪。前面的話有點多了，直接進(jìn)入今天的正題——交換排序蝴罪。
冒泡排序：BubbleSort
冒泡排序應(yīng)該是最簡單的了吧董济？額，至少我個人覺得應(yīng)該是最好理解的一種排序要门。
百度百科的原理：
1.比較相鄰的元素虏肾。如果第一個比第二個大，就交換他們兩個欢搜。
2.對每一對相鄰元素作同樣的工作封豪，從開始第一對到結(jié)尾的最后一對。在這一點炒瘟，最后的元素應(yīng)該會是最大的數(shù)撑毛。
3.針對所有的元素重復(fù)以上的步驟，除了最后一個唧领。
4.持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較雌续。
說起原理來感覺好難懂是吧斩个？？驯杜？
其實可以簡單去思考：為啥叫冒泡排序呢受啥？
不知道有沒有注意過水里的氣泡，大的氣泡會浮到上面去。冒泡排序也是：每一輪的排序,在這一輪中參與比較的元素中最大的數(shù)將會浮到最后滚局。
時間復(fù)雜度之類的分析居暖，我寫在了備注中~~~
So,直接上代碼：
請注意第二層for循環(huán)，循環(huán)次數(shù)會越來越小藤肢，簡單思考一下就會發(fā)現(xiàn)：畢竟每輪過后相對來說最大的數(shù)都會排到應(yīng)該在的地方去太闺，所以如果再多比較那幾次也沒啥意義~
/**
* Created by AceCream on 2017/3/19.
* 冒泡排序BubbleSort（屬于交換排序）
* 時間復(fù)雜度： 平均：O(n^2) 最佳：O(n) 最壞：O(n^2)
* 空間復(fù)雜度： O(1)
* 穩(wěn)定性： 穩(wěn)定
*/
public class BubbleSort {
public static void bubbleSort(int[] values){
for (int i=0;i<values.length;i++){
for (int j=i;j<values.length;j++){
if (values[i]>values[j]){
int temp = values[i];
values[i] = values[j];
values[j] = temp;
}
}
}
}
public static void main(String[] args) {
int value[] = {1,7,5,8,3};
bubbleSort(value);
for (int result : value) {
System.out.print(result+" ");
}
}
}
快速排序：Quicksort
為啥叫快速排序？因為他比別的排序快班胰Α省骂！當(dāng)然這是一般情況下，也就是平均情況下最住，快速排序的時間復(fù)雜度是O(nlogn)钞澳，這速度真的不要太快！
Ｕ歉俊Ｔ凇！但是Ｅ骸＠家鳌！
“快速排序是最快的排序”轧拄，這句話是正確的嗎揽祥？？檩电？
答案是：“不準(zhǔn)確拄丰！”
因為按照平均速度來說，它確實很快俐末，但是如果“樞紐元”為最大或者最小數(shù)字料按，那這個時候簡直就是災(zāi)難！對卓箫！災(zāi)難载矿！它就直接成為了——冒泡排序（Ps：冒泡：“靠！這個鍋烹卒，我不背闷盔！”）
具體這個“樞紐元”是啥讹语？還是從快速排序的原理說起來：
快排原理
原理：
- 確定一個基準(zhǔn)值
- 一次循環(huán)：從后往前比較消约，用基準(zhǔn)值和最后一個值比較，
- 如果比基準(zhǔn)值小的交換位置粉铐，如果沒有繼續(xù)比較下一個藐吮，
- 直到找到第一個比基準(zhǔn)值小的值才交換溺拱。
- 找到這個值之后逃贝，又從前往后開始比較，如果有比基準(zhǔn)值大的迫摔，交換位置沐扳，
- 如果沒有繼續(xù)比較下一個，直到找到第一個比基準(zhǔn)值大的值才交換句占。
- 直到從前往后的比較索引>從后往前比較的索引沪摄，結(jié)束第一次循環(huán)。
- 此時辖众，對于基準(zhǔn)值來說卓起，左右兩邊就是有序的了。
- 接著分別比較左右兩邊的序列凹炸，重復(fù)上述的循環(huán)戏阅。
行了，看了原理啤它，我相信基本上都懵逼了奕筐，我當(dāng)初也是被快排折磨是不行，找了大量的文檔变骡，沒看懂离赫。后來自己每一步都在紙上寫一遍，終于發(fā)現(xiàn)了其精髓所在塌碌！
簡單來說渊胸，快速排序其實是冒泡排序的加強(qiáng)版！從成熟體化身為完全體台妆！至于究極體翎猛，還得在其基礎(chǔ)上繼續(xù)優(yōu)化~~
我們第一次循環(huán)中，確定的這個“基準(zhǔn)值”接剩，就是上文所述的“樞紐元”切厘。
借用一下百科的圖片：
這個圖挺好，但是“初始”和“一次劃分”中間省略了很多步懊缺，我來補(bǔ)充一下：想象一下挖坑~
1.首先把第一個值疫稿，也就是49作為key值，取出來存坑里
2.從右邊開始向左邊鹃两，依次和key值比較遗座，一旦發(fā)現(xiàn)比它小的了也就是27，就把27挖出來俊扳，填在它曾經(jīng)的坑里(第一個位置)员萍。這時候變成了這個樣子：
27，38拣度，65，97，76抗果，13筋帖，27，49
3.那么這時候冤馏，出現(xiàn)了倆27日麸，這第二個27，人已經(jīng)走了逮光，但是它的坑還在代箭，很尷尬，咋辦涕刚？我們繼續(xù)走下一步嗡综，從左邊開始比較(注意！就不要從第一個開始了杜漠，已經(jīng)比較完了极景，就從38開始吧)，比較誰驾茴？還是依次與key(49)比較盼樟，直到發(fā)現(xiàn)比key大的數(shù)，也就是65锈至，這時候就把65晨缴，放到剛剛那個尷尬的坑里，把“坑里的值”更新掉~于是變成了這樣：
27峡捡，38击碗，65，97棋返，76延都，13，65睛竣，49
然后把最開始挖出來的那個49填坑里
27晰房，38，49射沟，97殊者，76，13验夯，65猖吴，49
但是這樣就結(jié)束第一此劃分了嗎？并沒有挥转，因為從start開始的left值和end開始的right值海蔽，還沒有碰到一起(left<right),所以繼續(xù)走共屈，重復(fù)剛才的動作，直到他們相遇党窜，這個時候：49左邊的數(shù)都小于49拗引，右邊的數(shù)都大于或等于49。也就完成了第一次劃分幌衣。
這之后我們看一下上面的圖矾削，以49為中心，分成了兩個部分豁护，這里就體現(xiàn)了“分治”的思想哼凯。將一個問題，分解成兩個小的部分楚里，分別做相同的操作断部。將兩個部分做同樣的操作，你想到了什么方式腻豌？對家坎！遞歸！快速排序吝梅，體現(xiàn)了算法的兩大思想：遞歸和分治虱疏。所以快速排序才這么重要。
這里多說一句苏携，前面說過如果這個"樞紐元"選的不好做瞪，那就很尷尬了，比如說右冻，這組數(shù)装蓬，我第一個值如果不是49而是13呢？那第一次劃分后纱扭，13放在了最左邊牍帚，我們再看第二個值，如果第二個值是27呢乳蛾？以此類推暗赶，如果我的這串?dāng)?shù)字剛開始就比較有序，那么快排反而成為了冒泡八嘁丁蹂随！時間復(fù)雜度變?yōu)榱薔(n^2)，所以說因惭，快速排序并不穩(wěn)定岳锁。
但是！我們不能因為這個就否定它蹦魔，畢竟在大量的測試中激率，快速排序的速度是要優(yōu)與堆排序和shell排序的咳燕。
是不是聽起來很暈。自己動手（請在紙上）寫一遍流程其實就懂得了~~
接下來柱搜，直接手敲代碼：
/**
* Created by AceCream on 2017/3/19.
* 快速排序QuickSort （屬于交換排序）
* 原理：
* 一次循環(huán)：從后往前比較迟郎，用基準(zhǔn)值和最后一個值比較，
* 如果比基準(zhǔn)值小的交換位置聪蘸，如果沒有繼續(xù)比較下一個，
* 直到找到第一個比基準(zhǔn)值小的值才交換表制。
* 找到這個值之后健爬，又從前往后開始比較，如果有比基準(zhǔn)值大的么介，交換位置娜遵，
* 如果沒有繼續(xù)比較下一個，直到找到第一個比基準(zhǔn)值大的值才交換壤短。
* 直到從前往后的比較索引>從后往前比較的索引设拟，結(jié)束第一次循環(huán)。
* 此時久脯，對于基準(zhǔn)值來說纳胧，左右兩邊就是有序的了。
* 接著分別比較左右兩邊的序列帘撰，重復(fù)上述的循環(huán)跑慕。
*
* 時間復(fù)雜度： 平均：O(nlog2n) 最佳：O(nlog2n) 最壞：O(n^2)
* 空間復(fù)雜度： O(1)
* 穩(wěn)定性： 不穩(wěn)定
*
*/
public class QuickSort {
private static void quickSort(int[] value, int start, int end) {
int left = start;
int right = end;
int key = value[start];
while (left<right){
while (left<right&&value[right]>=key){
right--;
}
if (left<right){
value[left] = value[right];
left++;
}
while (left<right&&value[left]<key){
left++;
}
if (left<right){
value[right] = value[left];
right--;
}
value[left] = key;
if (left>start) quickSort(value,start,left-1);
if (right<end) quickSort(value,right+1,end);
}
}
public static void main(String[] args) {
int[] value = {49,38,65,97,76,13,27,49};
int start = 0;
int end = value.length-1;
quickSort(value,start,end);
//打印出來
for (int result : value) {
System.out.print(result+" ");
}
}
}
