冒泡排序 O(n2)

兩個(gè)數(shù)比較大小，較大的數(shù)下沉，較小的數(shù)冒起來(lái)。

public static void bubbleSort(int[] a) { //臨時(shí)變量 int temp; //i是循環(huán)次數(shù),也是冒泡的結(jié)果位置下標(biāo)，5個(gè)數(shù)組循環(huán)5次 for (int i = 0; i < a.length; i++) { //從最后向前面兩兩對(duì)比，j是比較中下標(biāo)大的值 for (int j = a.length - 1; j > i; j--) {//讓小的數(shù)字排在前面if (a[j] < a[j - 1]) { temp = a[j]; a[j] = a[j - 1]; a[j - 1] = temp;} } } }

選擇排序 O(n2)

在長(zhǎng)度為N的無(wú)序數(shù)組中，第一次遍歷n-1個(gè)數(shù)，找到最小的數(shù)值與第一個(gè)元素交換；第二次遍歷n-2個(gè)數(shù)，找到最小的數(shù)值與第二個(gè)元素交換；。。。第n-1次遍歷，找到最小的數(shù)值與第n-1個(gè)元素交換，排序完成。

public static void selectSort(int[] a) { //臨時(shí)變量 int temp; //i是循環(huán)次數(shù),也是選擇交換的結(jié)果的位置下標(biāo)，5個(gè)數(shù)組循環(huán)5次 for (int i = 0; i < a.length; i++) { //最小值下標(biāo) int min = i; for (int j = i + 1; j < a.length; j++) {if (a[min] > a[j]) { min = j;} } temp = a[i]; a[i] = a[min]; a[min] = temp; } }

插入排序 O(n2)

在要排序的一組數(shù)中，假定前n-1個(gè)數(shù)已經(jīng)排好序，現(xiàn)在將第n個(gè)數(shù)插到前面的有序數(shù)列中，使得這n個(gè)數(shù)也是排好順序的。如此反復(fù)循環(huán)，直到全部排好順序。

public static void insertSort(int[] a) { int temp; //i是循環(huán)次數(shù),也是插入的隊(duì)列的長(zhǎng)度，最后一位是a[i] //所以一開(kāi)始a[0]是排好的一個(gè)隊(duì)列，比較a.length-1次，最后一次循環(huán)是a[a.length-1]插入a[0]~a[a.length-2] for (int i = 0; i < a.length - 1; i++) { //a[j]是要插入的數(shù)字，從a[j]往a[0]比較 for (int j = i + 1; j > 0; j--) {//如果插入的數(shù)小，交換位置if (a[j] < a[j - 1]) { temp = a[j]; a[j] = a[j - 1]; a[j - 1] = temp;} else { //因?yàn)槟J(rèn)a[0]~a[i]是排好的，a[i+1]比a[i]大的話，就不用比較后面了 break;} } } }

希爾排序 O(n1.5)

在要排序的一組數(shù)中，根據(jù)某一增量分為若干子序列，并對(duì)子序列分別進(jìn)行插入排序。然后逐漸將增量減小,并重復(fù)上述過(guò)程。直至增量為1,此時(shí)數(shù)據(jù)序列基本有序,最后進(jìn)行插入排序。

public static void shellSort(int[] a) { int temp; int d = a.length; for (; ; ) { d = d / 2; //根據(jù)差值分組為子序列 for (int k = 0; k < d; k++) {//此時(shí)對(duì)每組數(shù)列進(jìn)行插入排序，數(shù)組為a[k+d],a[k+2d]...a[k+n*d]for (int i = k + d; i < a.length; i += d) { // a[j]是要插入的數(shù)字，從a[j]往a[0]比較,跨度為d for (int j = i; j > k; j -= d) { //如果插入的數(shù)小，交換位置 if (a[j] < a[j - d]) { temp = a[j]; a[j] = a[j - d]; a[j - d] = temp; } else { //因?yàn)槟J(rèn)a[0]~a[i]是排好的，a[i+1]比a[i]大的話，就不用比較后面了 break; } }} } if (d == 1) {break; } } }

快速排序 O(N*logN)

先從數(shù)列中取出一個(gè)數(shù)作為base值；將比這個(gè)數(shù)小的數(shù)全部放在它的左邊，大于或等于它的數(shù)全部放在它的右邊；對(duì)左右兩個(gè)小數(shù)列重復(fù)第二步，直至各區(qū)間只有1個(gè)數(shù)。

public void quickSort(int a[], int l, int r) { //左邊必須大于右邊 if (l >= r) { return; } int i = l; int j = r; //選擇第一個(gè)數(shù)為基準(zhǔn) int base = a[l]; while (i < j) { //從右向左找第一個(gè)小于base的值，如果大于左移一位，直到找到小值或者i/j重合 while (i < j && a[j] > base) {j--; } //從左向右找第一個(gè)大于base的值,如果小于右移一位，直到找到大值或者i/j重合 while (i < j && a[i] < base) {i++; } //交換 if (i < j) {int temp = a[j];a[j] = a[i];a[i] = temp; } } //將基準(zhǔn)值放到i右移到的位置 a[i] = base; //將i左邊和i右邊分別排序 quickSort(a, l, i - 1);//遞歸調(diào)用 quickSort(a, i + 1, r);//遞歸調(diào)用 }

歸并排序 O(N*logN)

歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法的一個(gè)非常典型的應(yīng)用。首先考慮下如何將2個(gè)有序數(shù)列合并。這個(gè)非常簡(jiǎn)單，只要從比較2個(gè)數(shù)列的第一個(gè)數(shù)，誰(shuí)小就先取誰(shuí)，取了后就在對(duì)應(yīng)數(shù)列中刪除這個(gè)數(shù)。然后再進(jìn)行比較，如果有數(shù)列為空，那直接將另一個(gè)數(shù)列的數(shù)據(jù)依次取出即可。

private static void mergeSort(int[] a, int first, int last, int temp[]) { if (first < last) { //中間值 int middle = (first + last) / 2; //左半部分排序 mergeSort(a, first, middle, temp); //右半部分排序 mergeSort(a, middle + 1, last, temp); //合并左右部分 mergeArray(a, first, middle, last, temp); } } private static void mergeArray(int a[], int first, int middle, int end, int temp[]) { int i = first; int m = middle; int j = middle + 1; int n = end; int k = 0; while (i <= m && j <= n) { if (a[i] <= a[j]) {temp[k] = a[i];k++;i++; } else {temp[k] = a[j];k++;j++; } } while (i <= m) { temp[k] = a[i]; k++; i++; } while (j <= n) { temp[k] = a[j]; k++; j++; } for (int r = 0; r < k; r++) { a[first + r] = temp[r]; } }

堆排序 O(N*logN)

利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。堆是一個(gè)近似完全二叉樹(shù)的結(jié)構(gòu)，并同時(shí)滿足堆積的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)。

public static void heapSort(int a[]) { //堆頂最大值和數(shù)組最后（葉節(jié)點(diǎn)）交換 長(zhǎng)度-1 次 for (int i = a.length - 1; i > 0; i--) { //構(gòu)建大頂堆（最大堆） buildHeap(a, i); //堆頂最大值和數(shù)組最后（葉節(jié)點(diǎn)）交換 swap(a, 0, i); } } //構(gòu)建大頂堆（最大堆） public static void buildHeap(int a[], int lastIndex) { //排最后的非葉節(jié)點(diǎn)為 長(zhǎng)度/2-1，從第i檢查到堆頂?shù)?項(xiàng)，上浮大值 for (int i = (lastIndex + 1) / 2 - 1; i >= 0; i--) { //必定存在的左葉節(jié)點(diǎn)，不一定存在的右葉節(jié)點(diǎn) int left = i * 2 + 1; int right = i * 2 + 2; //max為左右葉節(jié)點(diǎn)中的最大值 int max = left; if (right <= lastIndex) {if (a[left] < a[right]) { max = right;} } //上浮大值 if (a[i] < a[max]) {swap(a, i, max); } } } //交換值 public static void swap(int a[], int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; }

基數(shù)排序 O(d(n+r))

【d代表關(guān)鍵字有d位，n代表n個(gè)記錄，r代表r個(gè)空隊(duì)列】基數(shù)排序(radix sort)，相對(duì)于常見(jiàn)的比較排序，基數(shù)排序是一種分配式排序，即通過(guò)將所有數(shù)字分配到應(yīng)在的位置最后再覆蓋到原數(shù)組完成排序的過(guò)程。

public static void radixSort(int[] a) { //位數(shù) int digit = 1; //作為排序后數(shù)組的新下標(biāo) int newIndex = 0; //供基數(shù)排序使用的二維數(shù)組，第一維度固定10位0~9，第二維度根據(jù)下標(biāo)依次存放每次基數(shù)排序的結(jié)果 int[][] container = new int[10][a.length]; //第一維度每個(gè)數(shù)組的內(nèi)容計(jì)數(shù)，最少為10，防止數(shù)組全是個(gè)位數(shù)時(shí)越界，例如五位數(shù)組最大值為8，counter.length=5 ，counter[8]就越界 int counterLength = 10; if (a.length > 10) { counterLength = a.length; } int[] counter = new int[counterLength]; //算出數(shù)組中最大的值，用來(lái)確定最大位 int max = a[0]; int maxDigit = 0; for (int i = 0; i < a.length; i++) { if (a[i] > max) {max = a[i]; } } while (max > 0) { max /= 10; maxDigit++; } //對(duì)每位進(jìn)行排序 while (digit <= maxDigit) { //對(duì)每個(gè)數(shù)值該位取余,container[remainder]，并計(jì)數(shù)該位置上數(shù)值的下標(biāo)counter[remainder] for (int num : a) {int remainder = (num / digit) % 10;container[remainder][counter[remainder]] = num;counter[remainder]++; } //將上一步放入容器的數(shù)值依次覆蓋到遠(yuǎn)數(shù)組中 for (int i = 0; i < 10; i++) {for (int j = 0; j < counter[i]; j++) { a[newIndex] = container[i][j]; newIndex++;}counter[i] = 0; } digit *= 10; newIndex = 0; } }

以上就是Java實(shí)現(xiàn)8種排序算法的示例代碼的詳細(xì)內(nèi)容，更多關(guān)于Java實(shí)現(xiàn)8種排序算法的資料請(qǐng)關(guān)注好吧啦網(wǎng)其它相關(guān)文章！