為什么80%的碼農都做不了架構師？>>> ??

日常操作中常見的排序方法有：冒泡排序、快速排序、選擇排序、插入排序、希爾排序，甚至還有基數排序、雞尾酒排序、桶排序、鴿巢排序、歸并排序等。

冒泡排序是一種簡單的排序算法。它重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端。

/** * 冒泡法排序 * 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。 * 對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對。在這一點，最后的元素應該會是最大的數。 * 針對所有的元素重復以上的步驟，除了最后一個。* 持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。 * * @param numbers * 需要排序的整型數組 */ public static void bubbleSort(int[] numbers) { int temp; // 記錄臨時中間值 int size = numbers.length; // 數組大小 for (int i = 0; i < size - 1; i++) { for (int j = i + 1; j < size; j++) { if (numbers[i] < numbers[j]) { // 交換兩數的位置 temp = numbers[i]; numbers[i] = numbers[j]; numbers[j] = temp; } } } }

快速排序使用分治法策略來把一個序列分為兩個子序列。

/** * 快速排序* * 從數列中挑出一個元素，稱為“基準”* 重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數可以到任一邊）。在這個分割之后， * 該基準是它的最后位置。這個稱為分割（partition）操作。* 遞歸地把小于基準值元素的子數列和大于基準值元素的子數列排序。 * * * @param numbers * @param start * @param end */ public static void quickSort(int[] numbers, int start, int end) { if (start < end) { int base = numbers[start]; // 選定的基準值（第一個數值作為基準值） int temp; // 記錄臨時中間值 int i = start, j = end; do { while ((numbers[i] < base) && (i < end)) i++; while ((numbers[j] > base) && (j > start)) j--; if (i <= j) { temp = numbers[i]; numbers[i] = numbers[j]; numbers[j] = temp; i++; j--; } } while (i <= j); if (start < j) quickSort(numbers, start, j); if (end > i) quickSort(numbers, i, end); } }

?

選擇排序是一種簡單直觀的排序方法，每次尋找序列中的最小值，然后放在最末尾的位置。

/** * 選擇排序 * 在未排序序列中找到最小元素，存放到排序序列的起始位置 * 再從剩余未排序元素中繼續尋找最小元素，然后放到排序序列末尾。 * 以此類推，直到所有元素均排序完畢。 * * @param numbers */ public static void selectSort(int[] numbers) { int size = numbers.length, temp; for (int i = 0; i < size; i++) { int k = i; for (int j = size - 1; j >i; j--) { if (numbers[j] < numbers[k]) k = j; } temp = numbers[i]; numbers[i] = numbers[k]; numbers[k] = temp; } }

?

?

插入排序的工作原理是通過構建有序序列，對于未排序數據，在已排序序列中從后向前掃描，找到相應位置并插入。其具體步驟參見代碼及注釋。

/** * 插入排序 * * 從第一個元素開始，該元素可以認為已經被排序 * 取出下一個元素，在已經排序的元素序列中從后向前掃描 * 如果該元素（已排序）大于新元素，將該元素移到下一位置* 重復步驟3，直到找到已排序的元素小于或者等于新元素的位置 * 將新元素插入到該位置中 * 重復步驟2 * * * @param numbers */ public static void insertSort(int[] numbers) { int size = numbers.length, temp, j; for(int i=1; i<size; i++) { temp = numbers[i]; for(j = i; j > 0 && temp < numbers[j-1]; j--) numbers[j] = numbers[j-1]; numbers[j] = temp; } }

歸并排序是建立在歸并操作上的一種有效的排序算法，歸并是指將兩個已經排序的序列合并成一個序列的操作。參考代碼如下：

/** * 歸并排序 * * 申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并后的序列 * 設定兩個指針，最初位置分別為兩個已經排序序列的起始位置* 比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一 位置 * 重復步驟3直到某一指針達到序列尾> * 將另一序列剩下的所有元素直接復制到合并序列尾 * * * @param numbers */ public static void mergeSort(int[] numbers, int left, int right) { int t = 1;// 每組元素個數 int size = right - left + 1; while (t < size) { int s = t;// 本次循環每組元素個數 t = 2 * s; int i = left; while (i + (t - 1) < size) { merge(numbers, i, i + (s - 1), i + (t - 1)); i += t; } if (i + (s - 1) < right) merge(numbers, i, i + (s - 1), right); } } /** * 歸并算法實現 * * @param data * @param p * @param q * @param r */ private static void merge(int[] data, int p, int q, int r) { int[] B = new int[data.length]; int s = p; int t = q + 1; int k = p; while (s <= q && t <= r) { if (data[s] <= data[t]) { B[k] = data[s]; s++; } else { B[k] = data[t]; t++; } k++; } if (s == q + 1) B[k++] = data[t++]; else B[k++] = data[s++]; for (int i = p; i <= r; i++) data[i] = B[i]; }

?

將之前介紹的所有排序算法整理成NumberSort類，代碼

package?test.sort;??? import?java.util.Random;??? //Java實現的排序類?? public?class?NumberSort?{???//私有構造方法，禁止實例化??private?NumberSort()?{???super();???}????//冒泡法排序?public?static?void?bubbleSort(int[]?numbers)?{???int?temp;?//?記錄臨時中間值???int?size?=?numbers.length;?//?數組大小???for?(int?i?=?0;?i?<?size?-?1;?i++)?{???for?(int?j?=?i?+?1;?j?<?size;?j++)?{???if?(numbers[i]?<?numbers[j])?{?//?交換兩數的位置???temp?=?numbers[i];???numbers[i]?=?numbers[j];???numbers[j]?=?temp;???}???}???}???}???//快速排序public?static?void?quickSort(int[]?numbers,?int?start,?int?end)?{???if?(start?<?end)?{???int?base?=?numbers[start];?//?選定的基準值（第一個數值作為基準值）???int?temp;?//?記錄臨時中間值???int?i?=?start,?j?=?end;???do?{???while?((numbers[i]?<?base)?&&?(i?<?end))???i++;???while?((numbers[j]?>?base)?&&?(j?>?start))???j--;???if?(i?<=?j)?{???temp?=?numbers[i];???numbers[i]?=?numbers[j];???numbers[j]?=?temp;???i++;???j--;???}???}?while?(i?<=?j);???if?(start?<?j)???quickSort(numbers,?start,?j);???if?(end?>?i)???quickSort(numbers,?i,?end);???}???}???//選擇排序?public?static?void?selectSort(int[]?numbers)?{???int?size?=?numbers.length,?temp;???for?(int?i?=?0;?i?<?size;?i++)?{???int?k?=?i;???for?(int?j?=?size?-?1;?j?>?i;?j--)?{???if?(numbers[j]?<?numbers[k])???k?=?j;???}???temp?=?numbers[i];???numbers[i]?=?numbers[k];???numbers[k]?=?temp;???}???}???//插入排序????//?@param?numbers??public?static?void?insertSort(int[]?numbers)?{???int?size?=?numbers.length,?temp,?j;???for?(int?i?=?1;?i?<?size;?i++)?{???temp?=?numbers[i];???for?(j?=?i;?j?>?0?&&?temp?<?numbers[j?-?1];?j--)???numbers[j]?=?numbers[j?-?1];???numbers[j]?=?temp;???}???}???//歸并排序??public?static?void?mergeSort(int[]?numbers,?int?left,?int?right)?{???int?t?=?1;//?每組元素個數???int?size?=?right?-?left?+?1;???while?(t?<?size)?{???int?s?=?t;//?本次循環每組元素個數???t?=?2?*?s;???int?i?=?left;???while?(i?+?(t?-?1)?<?size)?{???merge(numbers,?i,?i?+?(s?-?1),?i?+?(t?-?1));???i?+=?t;???}???if?(i?+?(s?-?1)?<?right)???merge(numbers,?i,?i?+?(s?-?1),?right);???}???}????//歸并算法實現??private?static?void?merge(int[]?data,?int?p,?int?q,?int?r)?{???int[]?B?=?new?int[data.length];???int?s?=?p;???int?t?=?q?+?1;???int?k?=?p;???while?(s?<=?q?&&?t?<=?r)?{???if?(data[s]?<=?data[t])?{???B[k]?=?data[s];???s++;???}?else?{???B[k]?=?data[t];???t++;???}???k++;???}???if?(s?==?q?+?1)???B[k++]?=?data[t++];???else??B[k++]?=?data[s++];???for?(int?i?=?p;?i?<=?r;?i++)???data[i]?=?B[i];???}???} ?

?

轉載于:https://my.oschina.net/zion/blog/821915

總結

以上是生活随笔為你收集整理的Java实现几种常见排序方法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。