冒泡排序(Bubble Sort)，又被稱為氣泡排序或泡沫排序。
它是一種較簡單的排序算法。它會遍歷若干次要排序的數列，每次遍歷時，它都會從前往后依次的比較相鄰兩個數的大小；如果前者比后者大，則交換它們的位置。這樣，一次遍歷之后，最大的元素就在數列的末尾！采用相同的方法再次遍歷時，第二大的元素就被排列在最大元素之前。重復此操作，直到整個數列都有序為止！
冒泡排序圖文說明
/*
* a -- 待排序的數組
* n -- 數組的長度
*/
public static void bubbleSort(int[] a, int n) {
int i,j;
for (i=n-1; i>0; i--) {
// 將a[0...i]中最大的數據放在末尾
for (j=0; j<i; j++) {
if (a[j] > a[j+1]) {
// 交換a[j]和a[j+1]
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
}
}
}
}
運行：
int[] a = {20,40,30,10,60,50,70};
String aa = "冒泡排序";
bubbleSort(a,a.length);
System.out.print(aa);
for (int d : a) {
System.out.print(d+",");
}
快速排序介紹
快速排序(Quick Sort)使用分治法策略。
它的基本思想是：選擇一個基準數，通過一趟排序將要排序的數據分割成獨立的兩部分；其中一部分的所有數據都比另外一部分的所有數據都要小。然后，再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。
快速排序流程：
- 從數列中挑出一個基準值。
- 將所有比基準值小的擺放在基準前面，所有比基準值大的擺在基準的后面(相同的數可以到任一邊)；在這個分區退出之后，該基準就處于數列的中間位置。
- 遞歸地把"基準值前面的子數列"和"基準值后面的子數列"進行排序。
- 圖文介紹
代碼實現：
/**
*
* 參數說明：
* a -- 待排序的數組
* l -- 數組的左邊界(例如，從起始位置開始排序，則l=0)
* r -- 數組的右邊界(例如，排序截至到數組末尾，則r=a.length-1)
*/
public static void quickSort(int[] a, int l, int r) {
if (l < r) {
int i,j,x;
i = l;
j = r;
x = a[i];
while (i < j) {
while(i < j && a[j] > x)
j--; // 從右向左找第一個小于x的數
if(i < j)
a[i++] = a[j];
while(i < j && a[i] < x)
i++; // 從左向右找第一個大于x的數
if(i < j)
a[j--] = a[i];
}
a[i] = x;
quickSort(a, l, i-1); /* 遞歸調用 */
quickSort(a, i+1, r); /* 遞歸調用 */
}
}
運行：
String aa = "快速排序";
quickSort(a,0,a.length-1);
System.out.print(aa);
for (int d : a) {
System.out.print(d+",");
}
直接插入排序介紹
直接插入排序(Straight Insertion Sort)的基本思想是：把n個待排序的元素看成為一個有序表和一個無序表。開始時有序表中只包含1個元素，無序表中包含有n-1個元素，排序過程中每次從無序表中取出第一個元素，將它插入到有序表中的適當位置，使之成為新的有序表，重復n-1次可完成排序過程。
直接插入排序圖文說明
代碼實現：
/**
* @param
* a -- 待排序的數組
* n -- 數組的長度
*/
public static void insertSort(int[] a, int n) {
int i, j, k;
for (i = 1; i < n; i++) {
//為a[i]在前面的a[0...i-1]有序區間中找一個合適的位置
for (j = i - 1; j >= 0; j--)
if (a[j] < a[i])
break;
//如找到了一個合適的位置
if (j != i - 1) {
//將比a[i]大的數據向后移
int temp = a[i];
for (k = i - 1; k > j; k--)
a[k + 1] = a[k];
//將a[i]放到正確位置上
a[k + 1] = temp;
}
}
}
運行和冒泡一樣。。。。。
希爾排序：
希爾(Shell)排序又稱為縮小增量排序，它是一種插入排序。它是直接插入排序算法的一種威力加強版。該方法因DL．Shell于1959年提出而得名。
希爾排序的基本思想是：
把記錄按步長 gap 分組，對每組記錄采用直接插入排序方法進行排序。
隨著步長逐漸減小，所分成的組包含的記錄越來越多，當步長的值減小到 1 時，整個數據合成為一組，構成一組有序記錄，則完成排序。
我們來通過演示圖，更深入的理解一下這個過程。
在上面這幅圖中：
初始時，有一個大小為 10 的無序序列。
在第一趟排序中，我們不妨設 gap1 = N / 2 = 5，即相隔距離為 5 的元素組成一組，可以分為 5 組。接下來，按照直接插入排序的方法對每個組進行排序。
在第二趟排序中，我們把上次的 gap 縮小一半，即 gap2 = gap1 / 2 = 2 (取整數)。這樣每相隔距離為 2 的元素組成一組，可以分為 2 組。按照直接插入排序的方法對每個組進行排序。
在第三趟排序中，再次把 gap 縮小一半，即gap3 = gap2 / 2 = 1。這樣相隔距離為 1 的元素組成一組，即只有一組。按照直接插入排序的方法對每個組進行排序。此時，排序已經結束。
需要注意一下的是，圖中有兩個相等數值的元素 5 和 5 。我們可以清楚的看到，在排序過程中，兩個元素位置交換了。
所以，希爾排序是不穩定的算法。
代碼實現：
/**
* 希爾排序
* @param list
*/
public static void shellSort(int[] a) {
int gap = a.length / 2;
while (1 <= gap) {
// 把距離為 gap 的元素編為一個組，掃描所有組
for (int i = gap; i < a.length; i++) {
int j = 0;
int temp = a[i];
// 對距離為 gap 的元素組進行排序
for (j = i - gap; j >= 0 && temp < a[j]; j = j - gap) {
a[j + gap] = a[j];
}
a[j + gap] = temp;
}
System.out.format("gap = %d:t", gap);
printAll(a);
gap = gap / 2; // 減小增量
}
}
// 打印完整序列
public static void printAll(int[] a) {
for (int value : a) {
System.out.print(value + "t");
}
System.out.println();
}
運行參考冒泡、、、、、
拓撲排序介紹
拓撲排序(Topological Order)是指，將一個有向無環圖(Directed Acyclic Graph簡稱DAG)進行排序進而得到一個有序的線性序列。
這樣說，可能理解起來比較抽象。下面通過簡單的例子進行說明！
例如，一個項目包括A、B、C、D四個子部分來完成，并且A依賴于B和D，C依賴于D。現在要制定一個計劃，寫出A、B、C、D的執行順序。這時，就可以利用到拓撲排序，它就是用來確定事物發生的順序的。
在拓撲排序中，如果存在一條從頂點A到頂點B的路徑，那么在排序結果中B出現在A的后面。
拓撲排序的算法圖解
拓撲排序算法的基本步驟：
1. 構造一個隊列Q(queue) 和 拓撲排序的結果隊列T(topological)；
2. 把所有沒有依賴頂點的節點放入Q；
3. 當Q還有頂點的時候，執行下面步驟：
3.1 從Q中取出一個頂點n(將n從Q中刪掉)，并放入T(將n加入到結果集中)；
3.2 對n每一個鄰接點m(n是起點，m是終點)；
3.2.1 去掉邊<n,m>;
3.2.2 如果m沒有依賴頂點，則把m放入Q;
注：頂點A沒有依賴頂點，是指不存在以A為終點的邊。
以上圖為例，來對拓撲排序進行演示。
第1步：將B和C加入到排序結果中。
頂點B和頂點C都是沒有依賴頂點，因此將C和C加入到結果集T中。假設ABCDEFG按順序存儲，因此先訪問B，再訪問C。訪問B之后，去掉邊<B,A>和<B,D>，并將A和D加入到隊列Q中。同樣的，去掉邊<C,F>和<C,G>，并將F和G加入到Q中。
將B加入到排序結果中，然后去掉邊<B,A>和<B,D>；此時，由于A和D沒有依賴頂點，因此并將A和D加入到隊列Q中。
將C加入到排序結果中，然后去掉邊<C,F>和<C,G>；此時，由于F有依賴頂點D，G有依賴頂點A，因此不對F和G進行處理。
第2步：將A,D依次加入到排序結果中。
第1步訪問之后，A,D都是沒有依賴頂點的，根據存儲順序，先訪問A，然后訪問D。訪問之后，刪除頂點A和頂點D的出邊。
第3步：將E,F,G依次加入到排序結果中。
因此訪問順序是：B -> C -> A -> D -> E -> F -> G
拓撲排序的代碼說明
拓撲排序是對有向無向圖的排序。下面以鄰接表實現的有向圖來對拓撲排序進行說明。
1. 基本定義
public class ListDG {
// 鄰接表中表對應的鏈表的頂點
private class ENode {
int ivex;
// 該邊所指向的頂點的位置
ENode nextEdge;
// 指向下一條弧的指針
}
// 鄰接表中表的頂點
private class VNode {
char data;
// 頂點信息
ENode firstEdge;
// 指向第一條依附該頂點的弧
};
private VNode[] mVexs;
// 頂點數組
...
}
- ListDG是鄰接表對應的結構體。mVexs則是保存頂點信息的一維數組。
- VNode是鄰接表頂點對應的結構體。data是頂點所包含的數據，而firstEdge是該頂點所包含鏈表的表頭指針。
- ENode是鄰接表頂點所包含的鏈表的節點對應的結構體。ivex是該節點所對應的頂點在vexs中的索引，而nextEdge是指向下一個節點的。
2. 拓撲排序
/*
* 拓撲排序
*
* 返回值：
* -1 -- 失敗(由于內存不足等原因導致)
* 0 -- 成功排序，并輸入結果
* 1 -- 失敗(該有向圖是有環的)
*/
public int topologicalSort() {
int index = 0;
int num = mVexs.size();
int[] ins;
// 入度數組
char[] tops;
// 拓撲排序結果數組，記錄每個節點的排序后的序號。
Queue<Integer> queue;
// 輔組隊列
ins = new int[num];
tops = new char[num];
queue = new LinkedList<Integer>();
// 統計每個頂點的入度數
for(int i = 0; i < num; i++) {
ENode node = mVexs.get(i).firstEdge;
while (node != null) {
ins[node.ivex]++;
node = node.nextEdge;
}
}
// 將所有入度為0的頂點入隊列
for(int i = 0; i < num; i ++)
if(ins[i] == 0)
queue.offer(i);
// 入隊列
while (!queue.isEmpty()) {
// 隊列非空
int j = queue.poll().intValue();
// 出隊列。j是頂點的序號
tops[index++] = mVexs.get(j).data;
// 將該頂點添加到tops中，tops是排序結果
ENode node = mVexs.get(j).firstEdge;
// 獲取以該頂點為起點的出邊隊列
// 將與"node"關聯的節點的入度減1；
// 若減1之后，該節點的入度為0；則將該節點添加到隊列中。
while(node != null) {
// 將節點(序號為node.ivex)的入度減1。
ins[node.ivex]--;
// 若節點的入度為0，則將其"入隊列"
if( ins[node.ivex] == 0)
queue.offer(node.ivex);
// 入隊列
node = node.nextEdge;
}
}
if(index != num) {
System.out.printf("Graph has a cyclen");
return 1;
}
// 打印拓撲排序結果
System.out.printf("== TopSort: ");
for(int i = 0; i < num; i ++)
System.out.printf("%c ", tops[i]);
System.out.printf("n");
return 0;
}
說明：
queue的作用就是用來存儲沒有依賴頂點的頂點。它與前面所說的Q相對應。
tops的作用就是用來存儲排序結果。它與前面所說的T相對應。
歸并排序
基本思想
歸并排序（MERGE-SORT）是利用歸并的思想實現的排序方法，該算法采用經典的分治（divide-and-conquer）策略（分治法將問題分(divide)成一些小的問題然后遞歸求解，而治(conquer)的階段則將分的階段得到的各答案"修補"在一起，即分而治之)。
分而治之
可以看到這種結構很像一棵完全二叉樹，本文的歸并排序我們采用遞歸去實現（也可采用迭代的方式去實現）。分階段可以理解為就是遞歸拆分子序列的過程，遞歸深度為log2n。
合并相鄰有序子序列
再來看看治階段，我們需要將兩個已經有序的子序列合并成一個有序序列，比如上圖中的最后一次合并，要將[4,5,7,8]和[1,2,3,6]兩個已經有序的子序列，合并為最終序列[1,2,3,4,5,6,7,8]，來看下實現步驟。
代碼實現
package sortdemo;
import JAVA.util.Arrays;
/**
* Created by chengxiao on 2016/12/8.
*/
public class MergeSort {
public static void main(String []args){
int []arr = {9,8,7,6,5,4,3,2,1};
sort(arr);
System.out.println(Arrays.toString(arr));
}
public static void sort(int []arr){
int []temp = new int[arr.length];
//在排序前，先建好一個長度等于原數組長度的臨時數組，
//避免遞歸中頻繁開辟空間
sort(arr,0,arr.length-1,temp);
}
private static void sort(int[] arr,int left,int right,int []temp){
if(left<right){
int mid = (left+right)/2;
sort(arr,left,mid,temp);
//左邊歸并排序，使得左子序列有序
sort(arr,mid+1,right,temp);
//右邊歸并排序，使得右子序列有序
merge(arr,left,mid,right,temp);
//將兩個有序子數組合并操作
}
}
private static void merge(int[] arr,int left,int mid,int right,int[] temp){
int i = left;//左序列指針
int j = mid+1;//右序列指針
int t = 0;//臨時數組指針
while (i<=mid && j<=right){
if(arr[i]<=arr[j]){
temp[t++] = arr[i++];
}else {
temp[t++] = arr[j++];
}
}
while(i<=mid){//將左邊剩余元素填充進temp中
temp[t++] = arr[i++];
}
while(j<=right){//將右序列剩余元素填充進temp中
temp[t++] = arr[j++];
}
t = 0;
//將temp中的元素全部拷貝到原數組中
while(left <= right){
arr[left++] = temp[t++];
}
}
}
最后
歸并排序是穩定排序，它也是一種十分高效的排序，能利用完全二叉樹特性的排序一般性能都不會太差。java中Arrays.sort()采用了一種名為TimSort的排序算法，就是歸并排序的優化版本。從上文的圖中可看出，每次合并操作的平均時間復雜度為O(n)，而完全二叉樹的深度為|log2n|。總的平均時間復雜度為O(nlogn)。而且，歸并排序的最好，最壞，平均時間復雜度均為O(nlogn)。
