您好,登錄后才能下訂單哦!
這篇文章主要介紹“Java有哪些排序算法”,在日常操作中,相信很多人在Java有哪些排序算法問題上存在疑惑,小編查閱了各式資料,整理出簡(jiǎn)單好用的操作方法,希望對(duì)大家解答”Java有哪些排序算法”的疑惑有所幫助!接下來,請(qǐng)跟著小編一起來學(xué)習(xí)吧!
冒泡排序介紹
冒泡排序(Bubble Sort),又被稱為氣泡排序或泡沫排序。
它是一種較簡(jiǎn)單的排序算法。它會(huì)遍歷若干次要排序的數(shù)列,每次遍歷時(shí),它都會(huì)從前往后依次的比較相鄰兩個(gè)數(shù)的大?。蝗绻罢弑群笳叽?,則交換它們的位置。這樣,一次遍歷之后,最大的元素就在數(shù)列的末尾! 采用相同的方法再次遍歷時(shí),第二大的元素就被排列在最大元素之前。重復(fù)此操作,直到整個(gè)數(shù)列都有序?yàn)橹梗?/p>
冒泡排序圖文說明
/* * a -- 待排序的數(shù)組 * n -- 數(shù)組的長(zhǎng)度 */ 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; } } } }
運(yùn)行:
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)使用分治法策略。
它的基本思想是:選擇一個(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ù)變成有序序列。
快速排序流程:
從數(shù)列中挑出一個(gè)基準(zhǔn)值。 將所有比基準(zhǔn)值小的擺放在基準(zhǔn)前面,所有比基準(zhǔn)值大的擺在基準(zhǔn)的后面(相同的數(shù)可以到任一邊);在這個(gè)分區(qū)退出之后,該基準(zhǔn)就處于數(shù)列的中間位置。 遞歸地把"基準(zhǔn)值前面的子數(shù)列"和"基準(zhǔn)值后面的子數(shù)列"進(jìn)行排序。 圖文介紹
代碼實(shí)現(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--; // 從右向左找第一個(gè)小于x的數(shù) if(i < j) a[i++] = a[j]; while(i < j && a[i] < x) i++; // 從左向右找第一個(gè)大于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)用 */ } }
運(yùn)行:
String aa = "快速排序"; quickSort(a,0,a.length-1); System.out.print(aa); for (int d : a) { System.out.print(d+","); }
直接插入排序介紹
直接插入排序(Straight Insertion Sort)的基本思想是:把n個(gè)待排序的元素看成為一個(gè)有序表和一個(gè)無序表。開始時(shí)有序表中只包含1個(gè)元素,無序表中包含有n-1個(gè)元素,排序過程中每次從無序表中取出第一個(gè)元素,將它插入到有序表中的適當(dāng)位置,使之成為新的有序表,重復(fù)n-1次可完成排序過程。
直接插入排序圖文說明
代碼實(shí)現(xiàn):
/** * @param * a -- 待排序的數(shù)組 * n -- 數(shù)組的長(zhǎng)度 */ 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ū)間中找一個(gè)合適的位置 for (j = i - 1; j >= 0; j--) if (a[j] < a[i]) break; //如找到了一個(gè)合適的位置 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; } } }
運(yùn)行和冒泡一樣。。。。。
希爾排序:
希爾(Shell)排序又稱為縮小增量排序,它是一種插入排序。它是直接插入排序算法的一種威力加強(qiáng)版。該方法因DL.Shell于1959年提出而得名。
希爾排序的基本思想是:
把記錄按步長(zhǎng) gap 分組,對(duì)每組記錄采用直接插入排序方法進(jìn)行排序。
隨著步長(zhǎng)逐漸減小,所分成的組包含的記錄越來越多,當(dāng)步長(zhǎ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):
/** * 希爾排序 * @param list */ public static void shellSort(int[] a) { int gap = a.length / 2; while (1 <= gap) { // 把距離為 gap 的元素編為一個(gè)組,掃描所有組 for (int i = gap; i < a.length; i++) { int j = 0; int temp = a[i]; // 對(duì)距離為 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(); }
運(yùn)行參考冒泡、、、、、
拓?fù)渑判蚪榻B
拓?fù)渑判?Topological Order)是指,將一個(gè)有向無環(huán)圖(Directed Acyclic Graph簡(jiǎn)稱DAG)進(jìn)行排序進(jìn)而得到一個(gè)有序的線性序列。
這樣說,可能理解起來比較抽象。下面通過簡(jiǎn)單的例子進(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中。
將B加入到排序結(jié)果中,然后去掉邊<B,A>和<B,D>;此時(shí),由于A和D沒有依賴頂點(diǎn),因此并將A和D加入到隊(duì)列Q中。
將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. 基本定義
public class ListDG { // 鄰接表中表對(duì)應(yīng)的鏈表的頂點(diǎn) private class ENode { int ivex; // 該邊所指向的頂點(diǎn)的位置 ENode nextEdge; // 指向下一條弧的指針 } // 鄰接表中表的頂點(diǎn) private class VNode { char data; // 頂點(diǎn)信息 ENode firstEdge; // 指向第一條依附該頂點(diǎn)的弧 }; private VNode[] mVexs; // 頂點(diǎn)數(shù)組 ...}
ListDG是鄰接表對(duì)應(yīng)的結(jié)構(gòu)體。 mVexs則是保存頂點(diǎn)信息的一維數(shù)組。 VNode是鄰接表頂點(diǎn)對(duì)應(yīng)的結(jié)構(gòu)體。 data是頂點(diǎn)所包含的數(shù)據(jù),而firstEdge是該頂點(diǎn)所包含鏈表的表頭指針。 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ù)渑判?/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ù)組,記錄每個(gè)節(jié)點(diǎn)的排序后的序號(hào)。 Queue<Integer> queue; // 輔組隊(duì)列 ins = new int[num]; tops = new char[num]; queue = new LinkedList<Integer>(); // 統(tǒng)計(jì)每個(gè)頂點(diǎn)的入度數(shù) for(int i = 0; i < num; i++) { ENode node = mVexs.get(i).firstEdge; while (node != null) { ins[node.ivex]++; node = node.nextEdge; } } // 將所有入度為0的頂點(diǎn)入隊(duì)列 for(int i = 0; i < num; i ++) if(ins[i] == 0) queue.offer(i); // 入隊(duì)列 while (!queue.isEmpty()) { // 隊(duì)列非空 int j = queue.poll().intValue(); // 出隊(duì)列。j是頂點(diǎn)的序號(hào) tops[index++] = mVexs.get(j).data; // 將該頂點(diǎn)添加到tops中,tops是排序結(jié)果 ENode node = mVexs.get(j).firstEdge; // 獲取以該頂點(diǎn)為起點(diǎn)的出邊隊(duì)列 // 將與"node"關(guān)聯(lián)的節(jié)點(diǎn)的入度減1; // 若減1之后,該節(jié)點(diǎn)的入度為0;則將該節(jié)點(diǎn)添加到隊(duì)列中。 while(node != null) { // 將節(jié)點(diǎn)(序號(hào)為node.ivex)的入度減1。 ins[node.ivex]--; // 若節(jié)點(diǎn)的入度為0,則將其"入隊(duì)列" if( ins[node.ivex] == 0) queue.offer(node.ivex); // 入隊(duì)列 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;}
說明:
queue的作用就是用來存儲(chǔ)沒有依賴頂點(diǎn)的頂點(diǎn)。它與前面所說的Q相對(duì)應(yīng)。 tops的作用就是用來存儲(chǔ)排序結(jié)果。它與前面所說的T相對(duì)應(yīng)。
歸并排序
基本思想
歸并排序(MERGE-SORT)是利用歸并的思想實(shí)現(xiàn)的排序方法,該算法采用經(jīng)典的分治(pide-and-conquer)策略(分治法將問題分(pide)成一些小的問題然后遞歸求解,而治(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)
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]; //在排序前,先建好一個(gè)長(zhǎng)度等于原數(shù)組長(zhǎng)度的臨時(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); //將兩個(gè)有序子數(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í)數(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é)束了,希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí),快去試試吧!若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí),請(qǐng)繼續(xù)關(guān)注億速云網(wǎng)站,小編會(huì)繼續(xù)努力為大家?guī)砀鄬?shí)用的文章!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。