Java有哪些排序算法

這篇文章主要介紹“Java有哪些排序算法”，在日常操作中，相信很多人在Java有哪些排序算法問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”Java有哪些排序算法”的疑惑有所幫助！接下來，請跟著小編一起來學(xué)習(xí)吧！

10年積累的網(wǎng)站設(shè)計制作、成都做網(wǎng)站經(jīng)驗，可以快速應(yīng)對客戶對網(wǎng)站的新想法和需求。提供各種問題對應(yīng)的解決方案。讓選擇我們的客戶得到更好、更有力的網(wǎng)絡(luò)服務(wù)。我雖然不認(rèn)識你，你也不認(rèn)識我。但先網(wǎng)站制作后付款的網(wǎng)站建設(shè)流程，更有洛浦免費網(wǎng)站建設(shè)讓你可以放心的選擇與我們合作。

冒泡排序介紹

冒泡排序(Bubble Sort)，又被稱為氣泡排序或泡沫排序。

它是一種較簡單的排序算法。它會遍歷若干次要排序的數(shù)列，每次遍歷時，它都會從前往后依次的比較相鄰兩個數(shù)的大??；如果前者比后者大，則交換它們的位置。這樣，一次遍歷之后，最大的元素就在數(shù)列的末尾！ 采用相同的方法再次遍歷時，第二大的元素就被排列在最大元素之前。重復(fù)此操作，直到整個數(shù)列都有序為止！

冒泡排序圖文說明

/*  *   a -- 待排序的數(shù)組  *   n -- 數(shù)組的長度  */  public static void bubbleSort(int[] a, int n) {    int i,j;     for (i=n-1; i>0; i--) {      // 將a[0...i]中最大的數(shù)據(jù)放在末尾      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)使用分治法策略。

它的基本思想是：選擇一個基準(zhǔn)數(shù)，通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分；其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小。然后，再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個排序過程可以遞歸進(jìn)行，以此達(dá)到整個數(shù)據(jù)變成有序序列。

快速排序流程：

1. 從數(shù)列中挑出一個基準(zhǔn)值。  將所有比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有比基準(zhǔn)值大的擺在基準(zhǔn)的后面(相同的數(shù)可以到任一邊)；在這個分區(qū)退出之后，該基準(zhǔn)就處于數(shù)列的中間位置。  遞歸地把"基準(zhǔn)值前面的子數(shù)列"和"基準(zhǔn)值后面的子數(shù)列"進(jìn)行排序。  圖文介紹

代碼實現(xiàn)：

/**  *  * 參數(shù)說明：  *   a -- 待排序的數(shù)組  *   l -- 數(shù)組的左邊界(例如，從起始位置開始排序，則l=0)  *   r -- 數(shù)組的右邊界(例如，排序截至到數(shù)組末尾，則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的數(shù)        if(i < j)          a[i++] = a[j];        while(i < j && a[i] < x)          i++; // 從左向右找第一個大于x的數(shù)        if(i < j)          a[j--] = a[i];      }      a[i] = x;      quickSort(a, l, i-1); /* 遞歸調(diào)用 */      quickSort(a, i+1, r); /* 遞歸調(diào)用 */    }     }

運行：

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個元素，排序過程中每次從無序表中取出第一個元素，將它插入到有序表中的適當(dāng)位置，使之成為新的有序表，重復(fù)n-1次可完成排序過程。

直接插入排序圖文說明

代碼實現(xiàn)：

/**  * @param   *   a -- 待排序的數(shù)組  *   n -- 數(shù)組的長度  */  public static void insertSort(int[] a, int n) {    int i, j, k;     for (i = 1; i < n; i++) {       //為a[i]在前面的a[0...i-1]有序區(qū)間中找一個合適的位置      for (j = i - 1; j >= 0; j--)        if (a[j] < a[i])          break;       //如找到了一個合適的位置      if (j != i - 1) {        //將比a[i]大的數(shù)據(jù)向后移        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 分組，對每組記錄采用直接插入排序方法進(jìn)行排序。

隨著步長逐漸減小，所分成的組包含的記錄越來越多，當(dāng)步長的值減小到 1 時，整個數(shù)據(jù)合成為一組，構(gòu)成一組有序記錄，則完成排序。

我們來通過演示圖，更深入的理解一下這個過程。

在上面這幅圖中：

初始時，有一個大小為 10 的無序序列。

在第一趟排序中，我們不妨設(shè) gap1 = N / 2 = 5，即相隔距離為 5 的元素組成一組，可以分為 5 組。接下來，按照直接插入排序的方法對每個組進(jìn)行排序。

在第二趟排序中，我們把上次的 gap 縮小一半，即 gap2 = gap1 / 2 = 2 (取整數(shù))。這樣每相隔距離為 2 的元素組成一組，可以分為 2 組。按照直接插入排序的方法對每個組進(jìn)行排序。

在第三趟排序中，再次把 gap 縮小一半，即gap3 = gap2 / 2 = 1。 這樣相隔距離為 1 的元素組成一組，即只有一組。按照直接插入排序的方法對每個組進(jìn)行排序。此時，排序已經(jīng)結(jié)束。

需要注意一下的是，圖中有兩個相等數(shù)值的元素 5 和 5 。我們可以清楚的看到，在排序過程中，兩個元素位置交換了。

所以，希爾排序是不穩(wěn)定的算法。

代碼實現(xiàn)：

/**   * 希爾排序   * @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 的元素組進(jìn)行排序        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();  }

運行參考冒泡、、、、、

拓?fù)渑判蚪榻B

拓?fù)渑判?Topological Order)是指，將一個有向無環(huán)圖(Directed Acyclic Graph簡稱DAG)進(jìn)行排序進(jìn)而得到一個有序的線性序列。

這樣說，可能理解起來比較抽象。下面通過簡單的例子進(jìn)行說明！

例如，一個項目包括A、B、C、D四個子部分來完成，并且A依賴于B和D，C依賴于D?，F(xiàn)在要制定一個計劃，寫出A、B、C、D的執(zhí)行順序。這時，就可以利用到拓?fù)渑判颍褪怯脕泶_定事物發(fā)生的順序的。

在拓?fù)渑判蛑校绻嬖谝粭l從頂點A到頂點B的路徑，那么在排序結(jié)果中B出現(xiàn)在A的后面。

拓?fù)渑判虻乃惴▓D解

拓?fù)渑判蛩惴ǖ幕静襟E：

1. 構(gòu)造一個隊列Q(queue) 和 拓?fù)渑判虻慕Y(jié)果隊列T(topological)；

2. 把所有沒有依賴頂點的節(jié)點放入Q；

3. 當(dāng)Q還有頂點的時候，執(zhí)行下面步驟：

3.1 從Q中取出一個頂點n(將n從Q中刪掉)，并放入T(將n加入到結(jié)果集中)；

3.2 對n每一個鄰接點m(n是起點，m是終點)；

3.2.1 去掉邊<n,m>;

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

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

以上圖為例，來對拓?fù)渑判蜻M(jìn)行演示。

第1步：將B和C加入到排序結(jié)果中。

頂點B和頂點C都是沒有依賴頂點，因此將C和C加入到結(jié)果集T中。假設(shè)ABCDEFG按順序存儲，因此先訪問B，再訪問C。訪問B之后，去掉邊<B,A>和<B,D>，并將A和D加入到隊列Q中。同樣的，去掉邊<C,F>和<C,G>，并將F和G加入到Q中。

將B加入到排序結(jié)果中，然后去掉邊<B,A>和<B,D>；此時，由于A和D沒有依賴頂點，因此并將A和D加入到隊列Q中。

將C加入到排序結(jié)果中，然后去掉邊<C,F>和<C,G>；此時，由于F有依賴頂點D，G有依賴頂點A，因此不對F和G進(jìn)行處理。

第2步：將A,D依次加入到排序結(jié)果中。

第1步訪問之后，A,D都是沒有依賴頂點的，根據(jù)存儲順序，先訪問A，然后訪問D。訪問之后，刪除頂點A和頂點D的出邊。

第3步：將E,F,G依次加入到排序結(jié)果中。

因此訪問順序是：B -> C -> A -> D -> E -> F -> G

拓?fù)渑判虻拇a說明

拓?fù)渑判蚴菍τ邢驘o向圖的排序。下面以鄰接表實現(xiàn)的有向圖來對拓?fù)渑判蜻M(jìn)行說明。

1. 基本定義

public class ListDG {  // 鄰接表中表對應(yīng)的鏈表的頂點  private class ENode {    int ivex;        // 該邊所指向的頂點的位置    ENode nextEdge;     // 指向下一條弧的指針  }   // 鄰接表中表的頂點  private class VNode {    char data;         // 頂點信息    ENode firstEdge;      // 指向第一條依附該頂點的弧  };   private VNode[] mVexs;   // 頂點數(shù)組   ...}

1. ListDG是鄰接表對應(yīng)的結(jié)構(gòu)體。 mVexs則是保存頂點信息的一維數(shù)組。  VNode是鄰接表頂點對應(yīng)的結(jié)構(gòu)體。 data是頂點所包含的數(shù)據(jù)，而firstEdge是該頂點所包含鏈表的表頭指針。  ENode是鄰接表頂點所包含的鏈表的節(jié)點對應(yīng)的結(jié)構(gòu)體。 ivex是該節(jié)點所對應(yīng)的頂點在vexs中的索引，而nextEdge是指向下一個節(jié)點的。

2. 拓?fù)渑判?/p>

/** 拓?fù)渑判?* 返回值：*   -1 -- 失敗(由于內(nèi)存不足等原因?qū)е?*   0 -- 成功排序，并輸入結(jié)果*   1 -- 失敗(該有向圖是有環(huán)的)*/public int topologicalSort() {  int index = 0;  int num = mVexs.size();  int[] ins;          // 入度數(shù)組  char[] tops;         // 拓?fù)渑判蚪Y(jié)果數(shù)組，記錄每個節(jié)點的排序后的序號。  Queue<Integer> queue;    // 輔組隊列   ins  = new int[num];  tops = new char[num];  queue = new LinkedList<Integer>();   // 統(tǒng)計每個頂點的入度數(shù)  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是排序結(jié)果    ENode node = mVexs.get(j).firstEdge;    // 獲取以該頂點為起點的出邊隊列     // 將與"node"關(guān)聯(lián)的節(jié)點的入度減1；    // 若減1之后，該節(jié)點的入度為0；則將該節(jié)點添加到隊列中。    while(node != null) {      // 將節(jié)點(序號為node.ivex)的入度減1。      ins[node.ivex]--;      // 若節(jié)點的入度為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;  }   // 打印拓?fù)渑判蚪Y(jié)果  System.out.printf("== TopSort: ");  for(int i = 0; i < num; i ++)    System.out.printf("%c ", tops[i]);  System.out.printf("\n");   return 0;}

說明：

1. queue的作用就是用來存儲沒有依賴頂點的頂點。它與前面所說的Q相對應(yīng)。  tops的作用就是用來存儲排序結(jié)果。它與前面所說的T相對應(yīng)。

歸并排序

基本思想

歸并排序（MERGE-SORT）是利用歸并的思想實現(xiàn)的排序方法，該算法采用經(jīng)典的分治（pide-and-conquer）策略（分治法將問題分(pide)成一些小的問題然后遞歸求解，而治(conquer)的階段則將分的階段得到的各答案"修補"在一起，即分而治之)。

分而治之

可以看到這種結(jié)構(gòu)很像一棵完全二叉樹，本文的歸并排序我們采用遞歸去實現(xiàn)（也可采用迭代的方式去實現(xiàn)）。分階段可以理解為就是遞歸拆分子序列的過程，遞歸深度為log2n。

合并相鄰有序子序列

再來看看治階段，我們需要將兩個已經(jīng)有序的子序列合并成一個有序序列，比如上圖中的最后一次合并，要將[4,5,7,8]和[1,2,3,6]兩個已經(jīng)有序的子序列，合并為最終序列[1,2,3,4,5,6,7,8]，來看下實現(xiàn)步驟。

代碼實現(xiàn)

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];   //在排序前，先建好一個長度等于原數(shù)組長度的臨時數(shù)組，   //避免遞歸中頻繁開辟空間   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);     //將兩個有序子數(shù)組合并操作   } } private static void merge(int[] arr,int left,int mid,int right,int[] temp){   int i = left;//左序列指針   int j = mid+1;//右序列指針   int t = 0;//臨時數(shù)組指針   while (i<=mid && j<=right){     if(arr[i]<=arr[j]){       temp[t++] = arr[i++];     }else {       temp[t++] = arr[j++];     }   }   while(i<=mid){//將左邊剩余元素填充進(jìn)temp中     temp[t++] = arr[i++];   }   while(j<=right){//將右序列剩余元素填充進(jìn)temp中     temp[t++] = arr[j++];   }   t = 0;   //將temp中的元素全部拷貝到原數(shù)組中   while(left <= right){     arr[left++] = temp[t++];   } }}

到此，關(guān)于“Java有哪些排序算法”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識，請繼續(xù)關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編會繼續(xù)努力為大家?guī)砀鄬嵱玫奈恼拢?/p>

分享名稱：Java有哪些排序算法
網(wǎng)站網(wǎng)址：http://muchs.cn/article6/jcpjog.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站建設(shè)、、網(wǎng)頁設(shè)計公司、網(wǎng)站設(shè)計、品牌網(wǎng)站建設(shè)、做網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)