溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章將為大家詳細講解有關關于Java中8種排序算法的案例，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。
冒泡排序 O(n2)
兩個數比較大小，較大的數下沉，較小的數冒起來。
public static void bubbleSort(int[] a) {
//臨時變量
int temp;
//i是循環次數,也是冒泡的結果位置下標，5個數組循環5次
for (int i = 0; i < a.length; i++) {
//從最后向前面兩兩對比，j是比較中下標大的值
for (int j = a.length - 1; j > i; j--) {
//讓小的數字排在前面
if (a[j] < a[j - 1]) {
temp = a[j];
a[j] = a[j - 1];
a[j - 1] = temp;
}
}
}
}選擇排序 O(n2)
在長度為N的無序數組中，第一次遍歷n-1個數，找到最小的數值與第一個元素交換；
第二次遍歷n-2個數，找到最小的數值與第二個元素交換；
。。。
第n-1次遍歷，找到最小的數值與第n-1個元素交換，排序完成。
public static void selectSort(int[] a) {
//臨時變量
int temp;
//i是循環次數,也是選擇交換的結果的位置下標，5個數組循環5次
for (int i = 0; i < a.length; i++) {
//最小值下標
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)
在要排序的一組數中，假定前n-1個數已經排好序，現在將第n個數插到前面的有序數列中，使得這n個數也是排好順序的。如此反復循環，直到全部排好順序。
public static void insertSort(int[] a) {
int temp;
//i是循環次數,也是插入的隊列的長度，最后一位是a[i]
//所以一開始a[0]是排好的一個隊列，比較a.length-1次，最后一次循環是a[a.length-1]插入a[0]~a[a.length-2]
for (int i = 0; i < a.length - 1; i++) {
//a[j]是要插入的數字，從a[j]往a[0]比較
for (int j = i + 1; j > 0; j--) {
//如果插入的數小，交換位置
if (a[j] < a[j - 1]) {
temp = a[j];
a[j] = a[j - 1];
a[j - 1] = temp;
} else {
//因為默認a[0]~a[i]是排好的，a[i+1]比a[i]大的話，就不用比較后面了
break;
}
}
}
}希爾排序 O(n1.5)
在要排序的一組數中，根據某一增量分為若干子序列，并對子序列分別進行插入排序。
然后逐漸將增量減小,并重復上述過程。直至增量為1,此時數據序列基本有序,最后進行插入排序。
public static void shellSort(int[] a) {
int temp;
int d = a.length;
for (; ; ) {
d = d / 2;
//根據差值分組為子序列
for (int k = 0; k < d; k++) {
//此時對每組數列進行插入排序，數組為a[k+d],a[k+2d]...a[k+n*d]
for (int i = k + d; i < a.length; i += d) {
// a[j]是要插入的數字，從a[j]往a[0]比較,跨度為d
for (int j = i; j > k; j -= d) {
//如果插入的數小，交換位置
if (a[j] < a[j - d]) {
temp = a[j];
a[j] = a[j - d];
a[j - d] = temp;
} else {
//因為默認a[0]~a[i]是排好的，a[i+1]比a[i]大的話，就不用比較后面了
break;
}
}
}
}
if (d == 1) {
break;
}
}
}快速排序 O(N*logN)
先從數列中取出一個數作為base值；
將比這個數小的數全部放在它的左邊，大于或等于它的數全部放在它的右邊；
對左右兩個小數列重復第二步，直至各區間只有1個數。
public void quickSort(int a[], int l, int r) {
//左邊必須大于右邊
if (l >= r) {
return;
}
int i = l;
int j = r;
//選擇第一個數為基準
int base = a[l];
while (i < j) {
//從右向左找第一個小于base的值，如果大于左移一位，直到找到小值或者i/j重合
while (i < j && a[j] > base) {
j--;
}
//從左向右找第一個大于base的值,如果小于右移一位，直到找到大值或者i/j重合
while (i < j && a[i] < base) {
i++;
}
//交換
if (i < j) {
int temp = a[j];
a[j] = a[i];
a[i] = temp;
}
}
//將基準值放到i右移到的位置
a[i] = base;
//將i左邊和i右邊分別排序
quickSort(a, l, i - 1);//遞歸調用
quickSort(a, i + 1, r);//遞歸調用
}歸并排序 O(N*logN)
歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法的一個非常典型的應用。
首先考慮下如何將2個有序數列合并。
這個非常簡單，只要從比較2個數列的第一個數，誰小就先取誰，取了后就在對應數列中刪除這個數。
然后再進行比較，如果有數列為空，那直接將另一個數列的數據依次取出即可。
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)
利用堆這種數據結構所設計的一種排序算法。堆是一個近似完全二叉樹的結構，并同時滿足堆積的性質：即子結點的鍵值或索引總是小于（或者大于）它的父節點。
public static void heapSort(int a[]) {
//堆頂最大值和數組最后（葉節點）交換 長度-1 次
for (int i = a.length - 1; i > 0; i--) {
//構建大頂堆（最大堆）
buildHeap(a, i);
//堆頂最大值和數組最后（葉節點）交換
swap(a, 0, i);
}
}
//構建大頂堆（最大堆）
public static void buildHeap(int a[], int lastIndex) {
//排最后的非葉節點為 長度/2-1，從第i檢查到堆頂第0項，上浮大值
for (int i = (lastIndex + 1) / 2 - 1; i >= 0; i--) {
//必定存在的左葉節點，不一定存在的右葉節點
int left = i * 2 + 1;
int right = i * 2 + 2;
//max為左右葉節點中的最大值
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;
}基數排序 O(d(n+r))
【d代表關鍵字有d位，n代表n個記錄，r代表r個空隊列】
基數排序(radix sort)，相對于常見的比較排序，基數排序是一種分配式排序，即通過將所有數字分配到應在的位置最后再覆蓋到原數組完成排序的過程。
public static void radixSort(int[] a) {
//位數
int digit = 1;
//作為排序后數組的新下標
int newIndex = 0;
//供基數排序使用的二維數組，第一維度固定10位0~9，第二維度根據下標依次存放每次基數排序的結果
int[][] container = new int[10][a.length];
//第一維度每個數組的內容計數，最少為10，防止數組全是個位數時越界，例如五位數組最大值為8，counter.length=5 ，counter[8]就越界
int counterLength = 10;
if (a.length > 10) {
counterLength = a.length;
}
int[] counter = new int[counterLength];
//算出數組中最大的值，用來確定最大位
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++;
}
//對每位進行排序
while (digit <= maxDigit) {
//對每個數值該位取余,container[remainder]，并計數該位置上數值的下標counter[remainder]
for (int num : a) {
int remainder = (num / digit) % 10;
container[remainder][counter[remainder]] = num;
counter[remainder]++;
}
//將上一步放入容器的數值依次覆蓋到遠數組中
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中8種排序算法的案例就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
