免费视频淫片aa毛片_日韩高清在线亚洲专区vr_日韩大片免费观看视频播放_亚洲欧美国产精品完整版

打開APP
userphoto
未登錄

開通VIP，暢享免費(fèi)電子書等14項(xiàng)超值服

開通VIP

首頁

好書

留言交流

下載APP

聯(lián)系客服
排序算法整合（冒泡，快速，希爾，拓?fù)?，歸并）

冒泡排序介紹

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

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

冒泡排序圖文說明

  1. /*
  2. * a -- 待排序的數(shù)組
  3. * n -- 數(shù)組的長度
  4. */
  5. public static void bubbleSort(int[] a, int n) {
  6. int i,j;
  8. for (i=n-1; i>0; i--) {
  9. // 將a[0...i]中最大的數(shù)據(jù)放在末尾
  10. for (j=0; j<i; j++) {
  12. if (a[j] > a[j+1]) {
  13. // 交換a[j]和a[j+1]
  14. int tmp = a[j];
  15. a[j] = a[j+1];
  16. a[j+1] = tmp;
  17. }
  18. }
  19. }
  21. }

運(yùn)行：

  1. int[] a = {20,40,30,10,60,50,70};
  2. String aa = '冒泡排序';
  3. bubbleSort(a,a.length);
  5. System.out.print(aa);
  6. for (int d : a) {
  7. System.out.print(d+',');
  8. }

快速排序介紹

快速排序(Quick Sort)使用分治法策略。

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

快速排序流程：

  1. 從數(shù)列中挑出一個(gè)基準(zhǔn)值。

  2. 將所有比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有比基準(zhǔn)值大的擺在基準(zhǔn)的后面(相同的數(shù)可以到任一邊)；在這個(gè)分區(qū)退出之后，該基準(zhǔn)就處于數(shù)列的中間位置。

  3. 遞歸地把'基準(zhǔn)值前面的子數(shù)列'和'基準(zhǔn)值后面的子數(shù)列'進(jìn)行排序。

  4. 圖文介紹

 

代碼實(shí)現(xiàn)：

  1. /**
  2. *
  3. * 參數(shù)說明：
  4. * a -- 待排序的數(shù)組
  5. * l -- 數(shù)組的左邊界(例如，從起始位置開始排序，則l=0)
  6. * r -- 數(shù)組的右邊界(例如，排序截至到數(shù)組末尾，則r=a.length-1)
  7. */
  8. public static void quickSort(int[] a, int l, int r) {
  10. if (l < r) {
  11. int i,j,x;
  13. i = l;
  14. j = r;
  15. x = a[i];
  16. while (i < j) {
  17. while(i < j && a[j] > x)
  18. j--; // 從右向左找第一個(gè)小于x的數(shù)
  19. if(i < j)
  20. a[i++] = a[j];
  21. while(i < j && a[i] < x)
  22. i++; // 從左向右找第一個(gè)大于x的數(shù)
  23. if(i < j)
  24. a[j--] = a[i];
  25. }
  26. a[i] = x;
  27. quickSort(a, l, i-1); /* 遞歸調(diào)用 */
  28. quickSort(a, i+1, r); /* 遞歸調(diào)用 */
  29. }
  31. }

運(yùn)行：

  2. String aa = '快速排序';
  3. quickSort(a,0,a.length-1);
  7. System.out.print(aa);
  8. for (int d : a) {
  9. 	System.out.print(d+',');
  10. 		}

直接插入排序介紹

直接插入排序(Straight Insertion Sort)的基本思想是：把n個(gè)待排序的元素看成為一個(gè)有序表和一個(gè)無序表。開始時(shí)有序表中只包含1個(gè)元素，無序表中包含有n-1個(gè)元素，排序過程中每次從無序表中取出第一個(gè)元素，將它插入到有序表中的適當(dāng)位置，使之成為新的有序表，重復(fù)n-1次可完成排序過程。

直接插入排序圖文說明

 

代碼實(shí)現(xiàn)：

  1. /**
  2. * @param
  3. * a -- 待排序的數(shù)組
  4. * n -- 數(shù)組的長度
  5. */
  6. public static void insertSort(int[] a, int n) {
  7. int i, j, k;
  9. for (i = 1; i < n; i++) {
  11. //為a[i]在前面的a[0...i-1]有序區(qū)間中找一個(gè)合適的位置
  12. for (j = i - 1; j >= 0; j--)
  13. if (a[j] < a[i])
  14. break;
  16. //如找到了一個(gè)合適的位置
  17. if (j != i - 1) {
  18. //將比a[i]大的數(shù)據(jù)向后移
  19. int temp = a[i];
  20. for (k = i - 1; k > j; k--)
  21. a[k + 1] = a[k];
  22. //將a[i]放到正確位置上
  23. a[k + 1] = temp;
  24. }
  25. }
  26. }

 運(yùn)行和冒泡一樣。。。。。

希爾排序：

希爾(Shell)排序又稱為縮小增量排序，它是一種插入排序。它是直接插入排序算法的一種威力加強(qiáng)版。該方法因DL．Shell于1959年提出而得名。

希爾排序的基本思想是：

把記錄按步長 gap 分組，對(duì)每組記錄采用直接插入排序方法進(jìn)行排序。

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

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

在上面這幅圖中：

初始時(shí)，有一個(gè)大小為 10 的無序序列。

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

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

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

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

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

代碼實(shí)現(xiàn)：

  1. /**
  2. 	   	* 希爾排序
  3. 	   	* @param list
  4. 	   	*/
  5. 	public static void shellSort(int[] a) {
  6. int gap = a.length / 2;
  8. while (1 <= gap) {
  9. // 把距離為 gap 的元素編為一個(gè)組，掃描所有組
  10. for (int i = gap; i < a.length; i++) {
  11. int j = 0;
  12. int temp = a[i];
  14. // 對(duì)距離為 gap 的元素組進(jìn)行排序
  15. for (j = i - gap; j >= 0 && temp < a[j]; j = j - gap) {
  16. a[j + gap] = a[j];
  17. }
  18. a[j + gap] = temp;
  19. }
  21. System.out.format('gap = %d:\t', gap);
  22. printAll(a);
  23. gap = gap / 2; // 減小增量
  24. }
  25. 	}
  26. 	// 打印完整序列
  27. 	public static void printAll(int[] a) {
  28. for (int value : a) {
  29. System.out.print(value + '\t');
  30. }
  31. System.out.println();
  32. 	}

運(yùn)行參考冒泡、、、、、

拓?fù)渑判蚪榻B

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

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

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

在拓?fù)渑判蛑?，如果存在一條從頂點(diǎn)A到頂點(diǎn)B的路徑，那么在排序結(jié)果中B出現(xiàn)在A的后面。

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

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

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

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

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

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

3.2 對(duì)n每一個(gè)鄰接點(diǎn)m(n是起點(diǎn)，m是終點(diǎn))； 

3.2.1 去掉邊<n,m>; 

3.2.2 如果m沒有依賴頂點(diǎn)，則把m放入Q; 

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

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

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

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

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

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

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

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

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

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

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

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

1. 基本定義

  1. public class ListDG {
  2. // 鄰接表中表對(duì)應(yīng)的鏈表的頂點(diǎn)
  3. private class ENode {
  4. int ivex;
  5. // 該邊所指向的頂點(diǎn)的位置
  6. ENode nextEdge;
  7. // 指向下一條弧的指針
  8. }
  10. // 鄰接表中表的頂點(diǎn)
  11. private class VNode {
  12. char data;
  13. // 頂點(diǎn)信息
  14. ENode firstEdge;
  15. // 指向第一條依附該頂點(diǎn)的弧
  16. };
  18. private VNode[] mVexs;
  19. // 頂點(diǎn)數(shù)組
  21. ...
  22. }

  1. ListDG是鄰接表對(duì)應(yīng)的結(jié)構(gòu)體。 mVexs則是保存頂點(diǎn)信息的一維數(shù)組。 

  2. VNode是鄰接表頂點(diǎn)對(duì)應(yīng)的結(jié)構(gòu)體。 data是頂點(diǎn)所包含的數(shù)據(jù)，而firstEdge是該頂點(diǎn)所包含鏈表的表頭指針。 

  3. ENode是鄰接表頂點(diǎn)所包含的鏈表的節(jié)點(diǎn)對(duì)應(yīng)的結(jié)構(gòu)體。 ivex是該節(jié)點(diǎn)所對(duì)應(yīng)的頂點(diǎn)在vexs中的索引，而nextEdge是指向下一個(gè)節(jié)點(diǎn)的。

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

  1. /*
  2. * 拓?fù)渑判?/div>
  3. *
  4. * 返回值：
  5. *     -1 -- 失敗(由于內(nèi)存不足等原因?qū)е?
  6. *      0 -- 成功排序，并輸入結(jié)果
  7. *      1 -- 失敗(該有向圖是有環(huán)的)
  8. */
  9. public int topologicalSort() {
  10. int index = 0;
  11. int num = mVexs.size();
  12. int[] ins;
  13. // 入度數(shù)組
  14. char[] tops;
  15. // 拓?fù)渑判蚪Y(jié)果數(shù)組，記錄每個(gè)節(jié)點(diǎn)的排序后的序號(hào)。
  16. Queue<Integer> queue;
  17. // 輔組隊(duì)列
  19. ins   = new int[num];
  20. tops  = new char[num];
  21. queue = new LinkedList<Integer>();
  23. // 統(tǒng)計(jì)每個(gè)頂點(diǎn)的入度數(shù)
  24. for(int i = 0; i < num; i++) {
  26. ENode node = mVexs.get(i).firstEdge;
  27. while (node != null) {
  28. ins[node.ivex]++;
  29. node = node.nextEdge;
  30. }
  31. }
  33. // 將所有入度為0的頂點(diǎn)入隊(duì)列
  34. for(int i = 0; i < num; i ++)
  35. if(ins[i] == 0)
  36. queue.offer(i);
  37. // 入隊(duì)列
  39. while (!queue.isEmpty()) {
  40. // 隊(duì)列非空
  41. int j = queue.poll().intValue();
  42. // 出隊(duì)列。j是頂點(diǎn)的序號(hào)
  43. tops[index++] = mVexs.get(j).data;
  44. // 將該頂點(diǎn)添加到tops中，tops是排序結(jié)果
  45. ENode node = mVexs.get(j).firstEdge;
  46. // 獲取以該頂點(diǎn)為起點(diǎn)的出邊隊(duì)列
  48. // 將與'node'關(guān)聯(lián)的節(jié)點(diǎn)的入度減1；
  49. // 若減1之后，該節(jié)點(diǎn)的入度為0；則將該節(jié)點(diǎn)添加到隊(duì)列中。
  50. while(node != null) {
  51. // 將節(jié)點(diǎn)(序號(hào)為node.ivex)的入度減1。
  52. ins[node.ivex]--;
  53. // 若節(jié)點(diǎn)的入度為0，則將其'入隊(duì)列'
  54. if( ins[node.ivex] == 0)
  55. queue.offer(node.ivex);
  56. // 入隊(duì)列
  58. node = node.nextEdge;
  59. }
  60. }
  62. if(index != num) {
  63. System.out.printf('Graph has a cycle\n');
  64. return 1;
  65. }
  67. // 打印拓?fù)渑判蚪Y(jié)果
  68. System.out.printf('== TopSort: ');
  69. for(int i = 0; i < num; i ++)
  70. System.out.printf('%c ', tops[i]);
  71. System.out.printf('\n');
  73. return 0;
  74. }

說明： 

  1. queue的作用就是用來存儲(chǔ)沒有依賴頂點(diǎn)的頂點(diǎn)。它與前面所說的Q相對(duì)應(yīng)。 

  2. tops的作用就是用來存儲(chǔ)排序結(jié)果。它與前面所說的T相對(duì)應(yīng)。

歸并排序

基本思想

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

分而治之

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

合并相鄰有序子序列

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

代碼實(shí)現(xiàn)

  1. package sortdemo;
  3. import java.util.Arrays;
  5. /**
  6. * Created by chengxiao on 2016/12/8.
  7. */
  8. public class MergeSort {
  9. public static void main(String []args){
  10. int []arr = {9,8,7,6,5,4,3,2,1};
  11. sort(arr);
  12. System.out.println(Arrays.toString(arr));
  13. }
  14. public static void sort(int []arr){
  15. int []temp = new int[arr.length];
  16. //在排序前，先建好一個(gè)長度等于原數(shù)組長度的臨時(shí)數(shù)組，
  17. //避免遞歸中頻繁開辟空間
  18. sort(arr,0,arr.length-1,temp);
  19. }
  20. private static void sort(int[] arr,int left,int right,int []temp){
  21. if(left<right){
  22. int mid = (left+right)/2;
  23. sort(arr,left,mid,temp);
  24. //左邊歸并排序，使得左子序列有序
  25. sort(arr,mid+1,right,temp);
  26. //右邊歸并排序，使得右子序列有序
  27. merge(arr,left,mid,right,temp);
  28. //將兩個(gè)有序子數(shù)組合并操作
  29. }
  30. }
  31. private static void merge(int[] arr,int left,int mid,int right,int[] temp){
  32. int i = left;//左序列指針
  33. int j = mid+1;//右序列指針
  34. int t = 0;//臨時(shí)數(shù)組指針
  35. while (i<=mid && j<=right){
  36. if(arr[i]<=arr[j]){
  37. temp[t++] = arr[i++];
  38. }else {
  39. temp[t++] = arr[j++];
  40. }
  41. }
  42. while(i<=mid){//將左邊剩余元素填充進(jìn)temp中
  43. temp[t++] = arr[i++];
  44. }
  45. while(j<=right){//將右序列剩余元素填充進(jìn)temp中
  46. temp[t++] = arr[j++];
  47. }
  48. t = 0;
  49. //將temp中的元素全部拷貝到原數(shù)組中
  50. while(left <= right){
  51. arr[left++] = temp[t++];
  52. }
  53. }
  54. }

最后

歸并排序是穩(wěn)定排序，它也是一種十分高效的排序，能利用完全二叉樹特性的排序一般性能都不會(huì)太差。java中Arrays.sort()采用了一種名為TimSort的排序算法，就是歸并排序的優(yōu)化版本。從上文的圖中可看出，每次合并操作的平均時(shí)間復(fù)雜度為O(n)，而完全二叉樹的深度為|log2n|?？偟钠骄鶗r(shí)間復(fù)雜度為O(nlogn)。而且，歸并排序的最好，最壞，平均時(shí)間復(fù)雜度均為O(nlogn)。

本站僅提供存儲(chǔ)服務(wù)，所有內(nèi)容均由用戶發(fā)布，如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請(qǐng)點(diǎn)擊舉報(bào)。
打開APP，閱讀全文并永久保存 查看更多類似文章
猜你喜歡
類似文章
生活服務(wù)
分享 收藏 導(dǎo)長圖 關(guān)注 下載文章
綁定賬號(hào)成功
后續(xù)可登錄賬號(hào)暢享VIP特權(quán)！
如果VIP功能使用有故障，
可點(diǎn)擊這里聯(lián)系客服！

聯(lián)系客服