1. 冒泡排序
描述
冒泡排序（Bubble Sort）设塔，是一種計(jì)算機(jī)科學(xué)領(lǐng)域的較簡(jiǎn)單的排序算法。
它重復(fù)地走訪過要排序的元素列缩幸，依次比較兩個(gè)相鄰的元素壹置，如果他們的順序（如從大到小、首字母從A到Z）錯(cuò)誤就把他們交換過來表谊。走訪元素的工作是重復(fù)地進(jìn)行直到?jīng)]有相鄰元素需要交換钞护，也就是說該元素已經(jīng)排序完成。
這個(gè)算法的名字由來是因?yàn)樵酱蟮脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端（升序或降序排列）爆办，就如同碳酸飲料中二氧化碳的氣泡最終會(huì)上浮到頂端一樣难咕，故名“冒泡排序”。
代碼
/**
* 冒泡排序
*
* @param array
* @return
*/
public static int[] bubbleSort(int[] array) {
if (array.length == 0) {
return array;
}
for (int i=1; i < array.length; i++) {// 執(zhí)行多少次數(shù)組的走訪
for (int j=0; j< array.length-i; j++) {// array.length-i: 每次走訪最后一個(gè)元素的索引距辆，j不能取這個(gè)值
if (array[j] > array[j+1]) {
int temp = array[j+1];
array[j+1] = array[j];
array[j] = temp;
}
}
}
return array;
}
2. 選擇排序
描述
選擇排序（Selection sort）是一種簡(jiǎn)單直觀的排序算法余佃。它的工作原理是每一次從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個(gè)元素跨算，存放在序列的起始位置爆土，然后，再從剩余未排序元素中繼續(xù)尋找最兄畈稀（大）元素步势，然后放到已排序序列的末尾氧猬。以此類推，直到全部待排序的數(shù)據(jù)元素排完坏瘩。 選擇排序是不穩(wěn)定的排序方法盅抚。
代碼
/**
* 選擇排序
*
* @param array
* @return
*/
public static int[] selectionSort(int[] array) {
if (array.length == 0) {
return array;
}
for (int i=0; i<array.length-1; i++) {// 確定待選擇序列的起始位置
int minIndex = i; // 默認(rèn)最小的數(shù)為待選擇序列的起始元素
// 從待選擇序列中找出最小元素的索引
for (int j = i+1; j<array.length; j++) {
if (array[j] < array[minIndex]) {
minIndex = j;
}
}
// 將最小的元素與待選擇序列的起始元素進(jìn)行交換
int temp = array[i];
array[i] = array[minIndex];
array[minIndex] = temp;
}
return array;
}
3.插入排序
描述
有一個(gè)已經(jīng)有序的數(shù)據(jù)序列，要求在這個(gè)已經(jīng)排好的數(shù)據(jù)序列中插入一個(gè)數(shù)倔矾，但要求插入后此數(shù)據(jù)序列仍然有序妄均，這個(gè)時(shí)候就要用到一種新的排序方法——插入排序法,插入排序的基本操作就是將一個(gè)數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中，從而得到一個(gè)新的哪自、個(gè)數(shù)加一的有序數(shù)據(jù)丰包，算法適用于少量數(shù)據(jù)的排序，時(shí)間復(fù)雜度為O(n^2)提陶。是穩(wěn)定的排序方法烫沙。插入算法把要排序的數(shù)組分成兩部分：第一部分包含了這個(gè)數(shù)組的所有元素，但將最后一個(gè)元素除外（讓數(shù)組多一個(gè)空間才有插入的位置）隙笆，而第二部分就只包含這一個(gè)元素（即待插入元素）锌蓄。在第一部分排序完成后，再將這個(gè)最后元素插入到已排好序的第一部分中撑柔。
插入排序的基本思想是：每步將一個(gè)待排序的記錄瘸爽，按其關(guān)鍵碼值的大小插入前面已經(jīng)排序的文件中適當(dāng)位置上，直到全部插入完為止铅忿。
代碼
/**
* 插入排序
*
* @param array
* @return
*/
public static int[] insertionSort(int[] array) {
if (array.length == 0) {
return array;
}
for (int i=1; i<array.length; i++) {// 默認(rèn)初始已排序的序列為僅包含索引為0的元素的序列
int j = i;
while (j >0 && array[j] < array[j-1]) {
int temp = array[j-1];
array[j-1] = array[j];
array[j] = temp;
j--;// 交換之后繼續(xù)和前一個(gè)數(shù)進(jìn)行對(duì)比
}
}
return array;
}
4. 希爾排序
描述
希爾排序(Shell's Sort)是插入排序的一種又稱“縮小增量排序”（Diminishing Increment Sort）剪决，是直接插入排序算法的一種更高效的改進(jìn)版本。希爾排序是非穩(wěn)定排序算法檀训。該方法因D.L.Shell于1959年提出而得名柑潦。
希爾排序是把記錄按下標(biāo)的一定增量分組，對(duì)每組使用直接插入排序算法排序峻凫；隨著增量逐漸減少渗鬼，每組包含的關(guān)鍵詞越來越多，當(dāng)增量減至1時(shí)荧琼，整個(gè)文件恰被分成一組譬胎，算法便終止。
代碼
/**
* 希爾排序
*
* @param array
* @return
*/
public static int[] shellSort(int[] array) {
if (array.length == 0) {
return array;
}
int gap = array.length / 2;
while (gap > 0) {
for (int i = gap; i < array.length; i++) {
int j = i;
while (j-gap>=0 && array[j] < array[j-gap]) {
int temp = array[j-gap];
array[j-gap] = array[j];
array[j] = temp;
j -= gap;
}
}
gap /= 2;
}
return array;
}
5. 快速排序
描述
快速排序（Quicksort）是對(duì)冒泡排序的一種改進(jìn)命锄。
快速排序由C. A. R. Hoare在1962年提出堰乔。它的基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小脐恩，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序镐侯，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列驶冒。
代碼
/**
* 快速排序
*
* @param array
* @param start
* @param end
* @return
*/
public static int[] quickSort(int[] array, int start, int end) {
if (start >= end) {
return array;
}
int low = start;
int high = end;
int middleValue = array[low];
while (low < high) {
// high左移
while (low < high && array[high] >= middleValue) {
high--;
}
array[low] = array[high];
// low右移
while (low < high && array[low] < middleValue) {
low++;
}
array[high] = array[low];
}
// 從循環(huán)退出: low == high
array[low] = middleValue;
// 對(duì)low左邊的列表進(jìn)行快速排序
quickSort(array, start, low - 1);
// 對(duì)low右邊的列表進(jìn)行快速排序
quickSort(array, low + 1, end);
return array;
}
6. 歸并排序
描述
歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用苟翻。將已有序的子序列合并搭伤，得到完全有序的序列；即先使每個(gè)子序列有序袜瞬，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表身堡，稱為二路歸并邓尤。
代碼
/**
* 歸并排序
*
* @param array
* @return
*/
public static int[] mergeSort(int[] array) {
if (array.length < 2)
return array;
int mid = array.length / 2;
int[] left = Arrays.copyOfRange(array, 0, mid);
int[] right = Arrays.copyOfRange(array, mid, array.length);
return merge(mergeSort(left), mergeSort(right));
}
/**
* 歸并: 將兩段排序好的數(shù)組結(jié)合成一個(gè)排序數(shù)組
*
* @param left
* @param right
* @return
*/
private static int[] merge(int[] left, int[] right) {
int[] result = new int[left.length + right.length];
for (int index =0, i=0, j=0; index < result.length; index++) {
if (i >= left.length)
result[index] = right[j++];
else if (j >= right.length)
result[index] = left[i++];
else if (left[i] > right[j])
result[index] = right[j++];
else
result[index] = left[i++];
}
return result;
}
