排序
選擇排序
- 主要思想 在未排序序列中找出最小的元素循衰，添加到有序序列中褐澎。
選擇排序圖解
- 思路：
- 將整個序列分為無序區(qū)和有序區(qū)工三，初始時候有序區(qū)為空，無序區(qū)含有待排序的所有記錄奸鬓。
- 在無序區(qū)中選取最小的元素全蝶，將它與無序區(qū)的第一個元素交換抑淫，使得有序區(qū)擴展了一位，同時無序區(qū)減少了一位砌烁。
- 重復(fù) 2 函喉，直到無序區(qū)只剩下一個記錄為之荣月。此時所有的記錄已經(jīng)從小到大排序完畢哺窄。
- 代碼實現(xiàn)
public static void sort(int[] array){
int len = array.length;
for (int i = 0; i < len; i++){
//對n個元素進行n-1次簡單排序
int index = i;
for(int j = i + 1; j < len; j++){
//在這層循環(huán)里面找出最小的元素
if(array[j] < array[index]){
index = j;
}
}
if(index != i){
int tem = array[i];
array[i] = array[index];
array[index] = tem;
}
}
}
冒泡排序（穩(wěn)定）
冒泡排序，又稱起泡排序萌业。是交換排序中最簡單的排序方法坷襟。
-
主要思想： 兩兩比較相鄰的元素，如果反序則交換生年，直到?jīng)]有反序婴程。（反序就是違反序列規(guī)律，比如你要從小到大排序抱婉，但是兩個元素 [5,2] 這樣就反序了）
起泡排序圖解.jpg 思路：
- 將整個序列分為無序區(qū)和有序區(qū)档叔，初始時候有序區(qū)為空，無序區(qū)含有待排序的所有記錄蒸绩。
- 對無序區(qū)從前到后依次相鄰的元素兩兩比較，反序則交換侵贵，從而使較小的元素往前移届搁，較大的元素往后移,，一趟下來無序區(qū)中最大的元素就會在無序區(qū)的最后了，我們把這個元素移除無序區(qū)放到有序區(qū)中卡睦。（像水中的起泡宴胧，體積大的先浮上來）
- 重復(fù) 2 ，直到無序區(qū)只剩下一個記錄為之表锻。此時所有的記錄已經(jīng)從小到大排序完畢恕齐。
-
再舉個例子吧
初始元素序列 [50 , 13 , 55 , 97 , 27, 38, 49, 65] 方括號代表無序區(qū)第一趟排序結(jié)果 [13 , 50 , 55 , 27 , 38 , 49 , 65 ], 97 先是 50 和 13 比較，50>13瞬逊，反序了显歧，交換位置。
然后 50 和 55 比較确镊，50<55士骤，正常，下一個蕾域。
然后是 55 和 97 比較拷肌，55<97，正常旨巷，下一個巨缘。
然后是 97 和 27 比較，97>27采呐，反序若锁，交換位置。
···
如此類推斧吐，就把最大的元素97給放到最后了又固，此時97被排除出無序區(qū)，放進了有序區(qū)会通。大家可以把剩下幾趟的排序結(jié)果自己排一下練手看看是否理解口予。
-
代碼實現(xiàn)
public void sort(int[] array){ //第一層循環(huán)從數(shù)組最后往前遍歷 for(int i = array.length - 1; i > 0; i--){ //這里循環(huán)上界是i-1娄周，體現(xiàn)出每趟排序選出的最大值從無序區(qū)中轉(zhuǎn)移到有序區(qū)中 for(int j = 0; j < i; j++){ if(array[j] > array[j+1]){ int tem = array[j]; array[j] = array[j+1]; array[j+1] = tem; } } } }
快速排序（不穩(wěn)定）
快速是對冒泡排序的一種改進涕侈。在冒泡排序中，記錄的比較和移動是兩兩相鄰的元素煤辨，把較大的元素一步一步推到后面裳涛，因此總的比較次數(shù)和移動次數(shù)較多。而快速排序是從兩端向中間進行的众辨。較大的元素一下子就能從前面移動到后面端三，這樣比較的次數(shù)和移動的次數(shù)就減少了。
-
主要思想：運用分治算法鹃彻，找一個分割值key郊闯，然后將無序區(qū)元素分為小于 key 和大于 key的元素集，直到所有的分區(qū)只包含一個元素。
快速排序圖解.jpg?
-
思路：
- 選擇分割值：最簡單的方法是選擇第一個元素作為分割值团赁。
- 定義i育拨、j 分別指向集合的最左和最右。
- 從右側(cè)掃描小于key的欢摄，r[ i ] 和 r[ j ] 進行交換熬丧，并執(zhí)行i++。
- 然后從左側(cè) i 開始掃描怀挠，找到大于key 的析蝴，r[ i ] 和 r[ j ] 進行交換，并執(zhí)行 j-- 绿淋。
- 重復(fù)以上步驟闷畸，直到 i = j ;此時一次劃分完畢，無序元素集合將分為小于key和大于key的兩個無序區(qū)躬它。
- 退出循環(huán)腾啥，說明 i 和 j 指向 key 所在的位置，返回該位置
-
代碼實現(xiàn)：
//一次迭代 public int partition(int[] r, int start, int end){ int i = start; int j = end; while(i < j){ //右側(cè)掃描 while(i < j && r[i] <= r[j]){ j--;//一直到r[i] > r[j] ,代表找到了小于key的值冯吓，可以進行交換了 } if(i < j){ swap(r, i, j);//交換數(shù)組兩個元素倘待，此方法省略 i++; } //然后是從左側(cè)掃描 while(i < j && r[i] <= r[j]){ i++; } if(i < j){ swap(r, i, j); j--; } } return i; } //遞歸實現(xiàn) public void queickSort(int[] r, int start, int end){ if(end - start > 1){//此時一個區(qū)間長度大于1，遞歸才繼續(xù)執(zhí)行组贺，否則結(jié)束 int mid = 0; mid = partition(r, start, end); queickSort(r, start, mid);//對左側(cè)無序區(qū)進行快速排序凸舵，分治處理 queickSort(r, mid+1, end);//對右側(cè)無序區(qū)進行快速排序，分治處理 } }
歸并排序 （穩(wěn)定）
歸并排序的中心思想還是分治失尖“⊙伲“歸并”的含義就是將兩個或者兩個以上的有序序列歸并成一個有序序列的過程。二路歸并排序掀潮，是歸并排序中最簡單的排序方法菇夸。
歸并排序.jpg
歸并排序有個主要問題：如何將兩個相鄰的有序序列合并成一個有序序列？
因為兩個有序序列仪吧，在歸并過程中庄新，可能會破壞掉原來的序列。像上圖中薯鼠，[20, 60]择诈，[10, 50] 在合并中就會破壞原來的序列了。為此出皇，我們設(shè)置i, j, k 三個參數(shù)羞芍，分別指向兩個待歸并的序列，以及最終序列的當(dāng)前位置郊艘。也就是 [ i→20 , j→10] ,k指向歸并結(jié)果存放的位置荷科，一開始是k→20 起始位置唯咬。
下面是一次歸并的代碼
/**
* r[start]→r[mid] , r[mid+1]→r[end]
* 下列start、mid畏浆、end 三個參數(shù)分別對應(yīng)有序序列的位置如上
*/
void merge (int[] r, int[] merge, int start, int mid, int end){
int i = start;
int j = mid + 1;
int k = start;
while(i <= mid && j <= end){
merge[k++] = r[i] >= r[j] ? r[j++] : r[i++];//將小的元素放入merge里面
}
if(i <= mid){//第一個子序列沒處理完
while(i <= mid){
merge[k++] = r[i++];
}
} else {
while(j <= end){//第二個序列沒處理完
merge[k++] = r[j++];
}
}
for (int index = start; index <= end; index++)
r[index] = merge[index];
}
另外要注意的是眉撵，使用遞歸的方式缀遍，是先把原來的數(shù)組拆分成一個一個的元素隔缀，這時候 start>=end 闻镶，然后才會開始進行兩兩歸并排序。
//遞歸實現(xiàn)
void mergeSort(int[] r, int[] merge, int start, int end){
if(start >= end) return;
int mid = (start + end)/2;
mergeSort(r, merge, start, mid);
mergeSort(r, merge, mid+1, end);
merge(r, merge, start, mid, end);
}
?
