這段時間閑了下來，就抽了點(diǎn)時間總結(jié)了下java中常用的七大排序算法，希望以后可以回顧！

1.插入排序算法

插入排序的基本思想是在遍歷數(shù)組的過程中，假設(shè)在序號 i 之前的元素即 [0..i-1] 都已經(jīng)排好序，本趟需要找到 i 對應(yīng)的元素 x 的正確位置 k ，并且在尋找這個位置 k 的過程中逐個將比較過的元素往后移一位，為元素 x “騰位置”，***將 k 對應(yīng)的元素值賦為 x ，一般情況下，插入排序的時間復(fù)雜度和空間復(fù)雜度分別為 O(n2 ) 和 O(1)。

/** 
* @param int[] 未排序數(shù)組 
* @return int[] 排完序數(shù)組 
*/ 
 
public int[] sortInsert(int[] array){ 
for(int i=1;i<array.length;i++){ 
int temp = array[i]; 
int j; 
for(j=i-1;j >= 0 && temp< array[j]; j--){ 
array[j + 1] = array[j]; 
} 
array[j + 1] = temp; 
} 
return array; 
} 

2.選擇排序算法

選擇排序的基本思想是遍歷數(shù)組的過程中，以 i 代表當(dāng)前需要排序的序號，則需要在剩余的 [i…n-1] 中找出其中的最小值，然后將找到的最小值與 i 指向的值進(jìn)行交換。因為每一趟確定元素的過程中都會有一個選擇***值的子流程，所以人們形象地稱之為選擇排序。選擇排序的時間復(fù)雜度和空間復(fù)雜度分別為 O(n2 ) 和 O(1) 。

/** 
* @param int[] 未排序數(shù)組 
* @return int[] 排完序數(shù)組 
*/ 
 
public int[] sortSelect(int[] arr){ 
for (int i = 0; i < arr.length; i++) { 
int miniPost = i; 
for (int m = i + 1; m < arr.length; m++) { 
if (arr[m] < arr[miniPost]) { 
miniPost = m; 
} 
} 
 
if (arr[i] > arr[miniPost]) { 
int temp; 
temp = arr[i]; 
arr[i] = arr[miniPost]; 
arr[miniPost] = temp; 
} 
} 
return arr; 
} 

3.冒泡排序算法

冒泡排序是將比較大的數(shù)字沉在最下面，較小的浮在上面

/** 
* @param int[] 未排序數(shù)組 
* @return int[] 排完序數(shù)組 
*/ 
 
public int[] sortBubble(int[] array){ 
int temp; 
// ***層循環(huán):表明比較的次數(shù), 比如 length 個元素,比較次數(shù)為 length-1 次（肯定不需和自己比） 
for(int i=0;i<array.length-1;i++){ 
for (int j = array.length - 1; j > i; j--) { 
if (array[j] < array[j - 1]) { 
temp = array[j]; 
array[j] = array[j - 1]; 
array[j - 1] = temp; 
} 
} 
} 
return array; 
} 

4.快速排序算法

通過一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的兩部分,其中一部分記錄的關(guān)鍵字均比另一部分的關(guān)鍵字小,則可以分別對這兩部分記錄繼續(xù)進(jìn)行排序,已達(dá)到整個序列有序的目的，本質(zhì)就是,找一個基位(樞軸,分水嶺,作用是左邊的都比它小,右邊的都比它大.可隨機(jī),取名base，首先從序列最右邊開始找比base小的,如果小,換位置,從而base移到剛才右邊(比較時比base小)的位置(記為臨時的high位),這樣base右邊的都比base大。然后,從序列的最左邊開始找比base大的，如果大,換位置,從而base移動到剛才左邊(比較時比base大)的位置(記為臨時的low位),這樣base左邊的都比base小，循環(huán)以上兩步,直到 low == heigh, 這使才真正的找到了樞軸,分水嶺. 返回這個位置,分水嶺左邊和右邊的序列,分別再來遞歸。

/** 
* @param int[] 未排序數(shù)組 
* @return int[] 排完序數(shù)組 
*/ 
 
public int[] sortQuick(int[] array){ 
return quickSort(array, 0, array.length-1); 
} 
 
private int[] quickSort(int[] arr, int low, int heigh) { 
if (low < heigh) { 
int division = partition(arr, low, heigh); 
quickSort(arr, low, division - 1); 
quickSort(arr, division + 1, heigh); 
} 
return arr; 
} 
 
// 分水嶺,基位,左邊的都比這個位置小,右邊的都大 
private int partition(int[] arr, int low, int heigh) { 
int base = arr[low]; //用子表的***個記錄做樞軸(分水嶺)記錄 
while (low < heigh) { //從表的兩端交替向中間掃描 
while (low < heigh && arr[heigh] >= base) { 
heigh--; 
} 
// base 賦值給 當(dāng)前 heigh 位,base 挪到(互換)到了這里,heigh位右邊的都比base大 
swap(arr, heigh, low); 
while (low < heigh && arr[low] <= base) { 
low++; 
} 
// 遇到左邊比base值大的了,換位置 
swap(arr, heigh, low); 
} 
// now low = heigh; 
return low; 
} 
 
private void swap(int[] arr, int a, int b) { 
int temp; 
temp = arr[a]; 
arr[a] = arr[b]; 
arr[b] = temp; 
} 

5.合并排序算法

歸并排序采用的是遞歸來實現(xiàn)，屬于“分而治之”，將目標(biāo)數(shù)組從中間一分為二，之后分別對這兩個數(shù)組進(jìn)行排序，排序完畢之后再將排好序的兩個數(shù)組“歸并”到一起，歸并排序最重要的也就是這個“歸并”的過程，歸并的過程中需要額外的跟需要?dú)w并的兩個數(shù)組長度一致的空間

/** 
* @param int[] 未排序數(shù)組 
* @return int[] 排完序數(shù)組 
*/ 
private int[] sort(int[] nums, int low, int high) { 
int mid = (low + high) / 2; 
if (low < high) { 
// 左邊 
sort(nums, low, mid); 
// 右邊 
sort(nums, mid + 1, high); 
// 左右歸并 
merge(nums, low, mid, high); 
} 
return nums; 
} 
 
private void merge(int[] nums, int low, int mid, int high) { 
int[] temp = new int[high - low + 1]; 
int i = low;// 左指針 
int j = mid + 1;// 右指針 
int k = 0; 
// 把較小的數(shù)先移到新數(shù)組中 
while (i <= mid && j <= high) { 
if (nums[i] < nums[j]) { 
temp[k++] = nums[i++]; 
} else { 
temp[k++] = nums[j++]; 
} 
} 
// 把左邊剩余的數(shù)移入數(shù)組 
while (i <= mid) { 
temp[k++] = nums[i++]; 
} 
// 把右邊邊剩余的數(shù)移入數(shù)組 
while (j <= high) { 
temp[k++] = nums[j++]; 
} 
// 把新數(shù)組中的數(shù)覆蓋nums數(shù)組 
for (int k2 = 0; k2 < temp.length; k2++) { 
nums[k2 + low] = temp[k2]; 
} 
} 
 
public int[] sortMerge(int[] array) { 
return sort(array, 0, array.length - 1); 
} 

6.希爾排序算法

希爾排序的誕生是由于插入排序在處理大規(guī)模數(shù)組的時候會遇到需要移動太多元素的問題。希爾排序的思想是將一個大的數(shù)組“分而治之”，劃分為若干個小的數(shù)組，以 gap 來劃分，比如數(shù)組 [1, 2, 3, 4, 5, 6, 7, 8] ，如果以 gap = 2 來劃分，可以分為 [1, 3, 5, 7] 和 [2, 4, 6, 8] 兩個數(shù)組（對應(yīng)的，如 gap = 3 ， 則劃分的數(shù)組為： [1, 4, 7] 、 [2, 5, 8] 、 [3, 6] ）然后分別對劃分出來的數(shù)組進(jìn)行插入排序，待各個子數(shù)組排序完畢之后再減小 gap 值重復(fù)進(jìn)行之前的步驟，直至 gap = 1 ，即對整個數(shù)組進(jìn)行插入排序，此時的數(shù)組已經(jīng)基本上快排好序了，所以需要移動的元素會很小很小，解決了插入排序在處理大規(guī)模數(shù)組時較多移動次數(shù)的問題，

希爾排序是插入排序的改進(jìn)版，在數(shù)據(jù)量大的時候?qū)π实奶嵘龓椭艽螅瑪?shù)據(jù)量小的時候建議直接使用插入排序就好了。

/** 
* @param int[] 未排序數(shù)組 
* @return int[] 排完序數(shù)組 
*/ 
 
public int[] sortShell(int[] array) { 
// 取增量 
int step = array.length / 2; 
while (step >= 1) { 
for (int i = step; i < array.length; i++) { 
int temp = array[i]; 
int j = 0; 
// 跟插入排序的區(qū)別就在這里 
for (j = i - step; j >= 0 && temp < array[j]; j -= step) { 
array[j + step] = array[j]; 
} 
array[j + step] = temp; 
} 
step /= 2; 
} 
return array; 
} 

7.堆排序算法

本質(zhì)就是先構(gòu)造一個大頂堆,parent比children大,root節(jié)點(diǎn)就是***的節(jié)點(diǎn) 把***的節(jié)點(diǎn)(root)與尾節(jié)點(diǎn)(***一個節(jié)點(diǎn),比較小)位置互換，剩下***的尾節(jié)點(diǎn),現(xiàn)在***,其余的,從***個元素開始到尾節(jié)點(diǎn)前一位,構(gòu)造大頂堆遞歸。

/** 
* @param int[] 未排序數(shù)組 
* @return int[] 排完序數(shù)組 
*/ 
public int[] sortHeap(int[] array) { 
buildHeap(array);// 構(gòu)建堆 
int n = array.length; 
int i = 0; 
for (i = n - 1; i >= 1; i--) { 
swap(array, 0, i); 
heapify(array, 0, i); 
} 
 
return array; 
} 
 
private void buildHeap(int[] array) { 
int n = array.length;// 數(shù)組中元素的個數(shù) 
for (int i = n / 2 - 1; i >= 0; i--) 
heapify(array, i, n); 
} 
 
private void heapify(int[] A, int idx, int max) { 
int left = 2 * idx + 1;// 左孩子的下標(biāo)（如果存在的話） 
int right = 2 * idx + 2;// 左孩子的下標(biāo)（如果存在的話） 
int largest = 0;// 尋找3個節(jié)點(diǎn)中***值節(jié)點(diǎn)的下標(biāo) 
if (left < max && A[left] > A[idx]) 
largest = left; 
else 
largest = idx; 
if (right < max && A[right] > A[largest]) 
largest = right; 
if (largest != idx) { 
swap(A, largest, idx); 
heapify(A, largest, max); 
} 
} 
} 
// 建堆函數(shù)，認(rèn)為【s，m】中只有 s 
// 對應(yīng)的關(guān)鍵字未滿足大頂堆定義，通過調(diào)整使【s，m】成為大頂堆===================================================== 
public static void heapAdjust(int[] array, int s, int m) { 
// 用0下標(biāo)元素作為暫存單元 
array[0] = array[s]; 
// 沿孩子較大的結(jié)點(diǎn)向下篩選 
for (int j = 2 * s; j <= m; j *= 2) { 
// 保證j為較大孩子結(jié)點(diǎn)的下標(biāo)，j < m 保證 j+1 <= m ，不越界 
if (j < m && array[j] < array[j + 1]) { 
j++; 
} 
if (!(array[0] < array[j])) { 
break; 
} 
// 若S位較小，應(yīng)將較大孩子上移 
array[s] = array[j]; 
// 較大孩子的值變成S位的較小值，可能引起頂堆的不平衡，故對其所在的堆進(jìn)行篩選 
s = j; 
} 
// 若S位較大，則值不變；否則，S位向下移動至2*s、4*s、。。。 
array[s] = array[0];