排序算法整合(冒泡,快速,希爾,拓撲,歸併)

冒泡排序(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 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)使用分治法策略。

它的基本思想是:選擇一個基準數,通過一趟排序將要排序的數據分割成獨立的兩部分;其中一部分的所有數據都比另外一部分的所有數據都要小。然後,再按此方法對這兩部分數據分別進行快速排序,整個排序過程可以遞歸進行,以此達到整個數據變成有序序列。

快速排序流程:

  1. 從數列中挑出一個基準值。
  2. 將所有比基準值小的擺放在基準前面,所有比基準值大的擺在基準的後面(相同的數可以到任一邊);在這個分區退出之後,該基準就處於數列的中間位置。
  3. 遞歸地把"基準值前面的子數列"和"基準值後面的子數列"進行排序。
  4. 圖文介紹
排序算法整合(冒泡,快速,希爾,拓撲,歸併)


代碼實現:

 /**
 *
 * 參數說明:
 * 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 去掉邊;

3.2.2 如果m沒有依賴頂點,則把m放入Q;

注:頂點A沒有依賴頂點,是指不存在以A為終點的邊。

排序算法整合(冒泡,快速,希爾,拓撲,歸併)


以上圖為例,來對拓撲排序進行演示。

排序算法整合(冒泡,快速,希爾,拓撲,歸併)


第1步:將B和C加入到排序結果中。

頂點B和頂點C都是沒有依賴頂點,因此將C和C加入到結果集T中。假設ABCDEFG按順序存儲,因此先訪問B,再訪問C。訪問B之後,去掉邊

,並將A和D加入到隊列Q中。同樣的,去掉邊和,並將F和G加入到Q中。

將B加入到排序結果中,然後去掉邊;此時,由於A和D沒有依賴頂點,因此並將A和D加入到隊列Q中。

將C加入到排序結果中,然後去掉邊和;此時,由於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; 
 // 頂點數組
 ...
}


  1. ListDG是鄰接表對應的結構體。mVexs則是保存頂點信息的一維數組。
  2. VNode是鄰接表頂點對應的結構體。data是頂點所包含的數據,而firstEdge是該頂點所包含鏈表的表頭指針。
  3. ENode是鄰接表頂點所包含的鏈表的節點對應的結構體。ivex是該節點所對應的頂點在vexs中的索引,而nextEdge是指向下一個節點的。


2. 拓撲排序

/*
* 拓撲排序
*
* 返回值:
* -1 -- 失敗(由於內存不足等原因導致)
* 0 -- 成功排序,並輸入結果
* 1 -- 失敗(該有向圖是有環的)
*/
public int topologicalSort() {
 int index = 0;
 int num = mVexs.size();
 int[] ins; 
 // 入度數組
 char[] tops; 
 // 拓撲排序結果數組,記錄每個節點的排序後的序號。
 Queue queue; 
 // 輔組隊列
 ins = new int[num];
 tops = new char[num];
 queue = new LinkedList();
 // 統計每個頂點的入度數
 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 cycle\n"); 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


最後

歸併排序是穩定排序,它也是一種十分高效的排序,能利用完全二叉樹特性的排序一般性能都不會太差。java中Arrays.sort()採用了一種名為TimSort的排序算法,就是歸併排序的優化版本。從上文的圖中可看出,每次合併操作的平均時間複雜度為O(n),而完全二叉樹的深度為|log2n|。總的平均時間複雜度為O(nlogn)。而且,歸併排序的最好,最壞,平均時間複雜度均為O(nlogn)。

現在私信關注小編可以獲得免費的JAVA入門到高級的學習資料以及視頻!


分享到:


相關文章: