经典十大排序算法（含升序降序，基数排序含负数排序）【Java版完整代码】【建议收藏系列】
經(jīng)典十大排序算法【Java版完整代碼】
寫在前面的話
十大排序算法對比
冒泡排序
快速排序
直接選擇排序
堆排序
歸并排序
插入排序
希爾排序
計數(shù)排序
桶排序
基數(shù)排序
完整測試類
寫在前面的話
???????雖然已經(jīng)有很多人總結過這十大排序算法，優(yōu)秀的文章也不少，但是Java完整版的好像不多，還存在某些文章代碼存在錯誤的情況，同時也為了自己練手，決定把所有的寫一遍鞏固下，同時也真誠的希望閱讀到這篇文章的小伙伴們可以自己去從頭敲一遍，不要粘貼復制！希望我的文章對你有所幫助，每天進步一點點！！！
???????我用通俗的理解寫下對算法的解釋，對某個算法的運行過程不是很理解的話或者想看比較官方的解釋的話，單獨搜索某個算法，看幾篇不同的解釋，就可以有自己的理解了，這里我主要展示代碼以及進行通俗的解釋！整起來，再強調(diào)一次，一定要自己敲一遍，這樣才能理解的更深刻！
十大排序算法對比
關于最后一列的穩(wěn)定性，我稍微解釋下，例如對序列：1 2 4 2 6 排序，序列中存在兩個2，如果我們把這兩個2標記上（讓他倆不同），排序之后，前面的2還在前面，那么就稱這種排序是穩(wěn)定的，反之不穩(wěn)定。
冒泡排序
簡單解釋：
???????原理就如算法名字一樣，就像水中的氣泡一樣，每次我都把最大的或最小的放到最后面，這樣總共需要n-1趟即可完成排序，這就是第一層循環(huán)，第二次循環(huán)就是遍歷未被固定的那些數(shù)（理解成數(shù)組左邊的數(shù)，因為每層循環(huán)都會把最大或最小的數(shù)升到最右邊固定起來，下次就不遍歷這些數(shù)了），兩層循環(huán)遍歷結束后，所有的數(shù)就排好序了。
???????兩層循環(huán)所以冒泡排序算法的時間復雜度是O(n 2 n^{2}n?
2
?)，是一個非常高的時間復雜度，我在下面的代碼進行了優(yōu)化，加了一個標志位，如果上一次循環(huán)未發(fā)生交換，就說明已經(jīng)是有序的了，就不繼續(xù)下去了，反之繼續(xù)進行下一輪。
本文的圖片來源網(wǎng)絡，僅用于大家學習，侵權聯(lián)系刪除！（下同）
完整代碼：
package com.keafmd.Sequence;
/**
?* Keafmd
?*
?* @ClassName: BubbleSort
?* @Description: 冒泡排序
?* @author: 牛哄哄的柯南
?* @date: 2021-06-24 10:31
?*/
public class BubbleSort {
? ? //冒泡排序
? ? public static void bubbleSort(int[] arr, boolean ascending) { //exchange標志表示為升序排序還是降序排序
? ? ? ? boolean flag = true; //加一個標志位，記錄上一次是否發(fā)生了交換，如果是，我們則進行下一輪，如果沒有，說明已經(jīng)冒泡好了
? ? ? ? for (int i = 1; i < arr.length && flag; i++) { //控制次數(shù)，第幾趟排序，只需要n-1趟，有交換時進行，只有flag=false就說明上一次一個元素都沒有進行交換
? ? ? ? ? ? /*System.out.print("第"+i+"次遍歷：");
? ? ? ? ? ? for (int i1 : arr) {
? ? ? ? ? ? ? ? System.out.print(i1+" ");
? ? ? ? ? ? }
? ? ? ? ? ? System.out.println();*/
? ? ? ? ? ? flag = false; //假定未交換
? ? ? ? ? ? for (int j = 0; j < arr.length - i; j++) {
? ? ? ? ? ? ? ? if (ascending ? arr[j] > arr[j + 1] : arr[j] < arr[j + 1]) { //控制升序還是降序
? ? ? ? ? ? ? ? ? ? int temp = arr[j];
? ? ? ? ? ? ? ? ? ? arr[j] = arr[j + 1];
? ? ? ? ? ? ? ? ? ? arr[j + 1] = temp;
? ? ? ? ? ? ? ? ? ? flag = true;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? //冒泡排序 -- 默認不傳參升序
? ? public static void bubbleSort(int[] arr) {
? ? ? ? bubbleSort(arr, true);
? ? }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
測試代碼：
升序排序（從小到大）
package com.keafmd.Sequence;
import java.util.*;
import java.util.stream.IntStream;
import java.util.stream.Stream;
/**
?* Keafmd
?*
?* @ClassName: Sort
?* @Description: 十大排序算法
?* @author: 牛哄哄的柯南
?* @date: 2021-06-16 21:27
?*/
public class Sort {
? ? public static void main(String[] args) {
? ? ? ? int[] nums = {12, 4, 25, 47, 58, 34, 25, 9, 99, 26, 1, -13, 162, 10093, -66, -1};
? ? ? ? int[] temparr;
? ? ? ? //測試冒泡排序
? ? ? ? System.out.println("測試冒泡排序:");
? ? ? ? temparr = nums.clone();
? ? ? ? BubbleSort.bubbleSort(temparr);
? ? ? ? //逆序排序
? ? ? ? //BubbleSort.bubbleSort(temparr,false);
? ? ? ? for (int i = 0; i < temparr.length; i++) {
? ? ? ? ? ? System.out.print(temparr[i] + " ");
? ? ? ? }
? ? ? ? System.out.println();
? ? }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
運行結果：
測試冒泡排序:
-66 -13 -1 1 4 9 12 25 25 26 34 47 58 99 162 10093?
1
2
降序排序（從大到小）
//測試冒泡排序
System.out.println("測試冒泡排序:");
temparr = nums.clone();
BubbleSort.bubbleSort(temparr,false);
for (int i = 0; i < temparr.length; i++) {
? ? System.out.print(temparr[i] + " ");
}
System.out.println();
1
2
3
4
5
6
7
8
運行結果：
測試冒泡排序:
10093 162 99 58 47 34 26 25 25 12 9 4 1 -1 -13 -66?
1
2
下面幾個算法的測試也就是換了下類名和方法名（換成相應的排序算法），如果想降序就在數(shù)組后面?zhèn)鱾€false即可。我就不一一復制了，我在最下面給出含所有算法的測試類，需要的自取即可。
快速排序
簡單解釋：
快速排序就是每次找一個基點（第一個元素），然后兩個哨兵，一個從最前面往后走，一個從最后面往前面走，如果后面那個哨兵找到了一個比基點大的數(shù)停下來，前面那個哨兵找到比基點大的數(shù)停下來，然后交換兩個哨兵找到的數(shù)，如果找不到最后兩個哨兵就會碰到一起就結束，最后交換基點和哨兵相遇的地方的元素，然后就將一個序列分為比基點小的一部分和比基點大的一部分，然后遞歸左半部分和右半部分，最后的結果就是有序的了。
完整代碼：
package com.keafmd.Sequence;
/**
?* Keafmd
?*
?* @ClassName: QuickSort
?* @Description: 快速排序
?* @author: 牛哄哄的柯南
?* @date: 2021-06-24 10:32
?*/
public class QuickSort {
? ? //快速排序
? ? public static void quickSort(int[] arr) {
? ? ? ? quickSort(arr, true);
? ? }
? ? public static void quickSort(int[] arr, boolean ascending) {
? ? ? ? if (ascending) {
? ? ? ? ? ? quickSort(arr, 0, arr.length - 1, true);
? ? ? ? } else {
? ? ? ? ? ? quickSort(arr, 0, arr.length - 1, false);
? ? ? ? }
? ? }
? ? public static void quickSort(int[] arr, int begin, int end, boolean ascending) {
? ? ? ? if (ascending)
? ? ? ? ? ? quickSort(arr, begin, end);
? ? ? ? else
? ? ? ? ? ? quickSortDescending(arr, begin, end);
? ? }
? ? //快排序升序 -- 默認
? ? public static void quickSort(int[] arr, int begin, int end) {
? ? ? ? if (begin > end) { //結束條件
? ? ? ? ? ? return;
? ? ? ? }
? ? ? ? int base = arr[begin];
? ? ? ? int i = begin, j = end;
? ? ? ? while (i < j) { // 兩個哨兵（i左邊，j右邊）沒有相遇
? ? ? ? ? ? while (arr[j] >= base && i < j) { //哨兵j沒找到比base小的
? ? ? ? ? ? ? ? j--;
? ? ? ? ? ? }
? ? ? ? ? ? while (arr[i] <= base && i < j) { //哨兵i沒找到比base大的
? ? ? ? ? ? ? ? i++;
? ? ? ? ? ? }
? ? ? ? ? ? if (i < j) { //如果滿足條件則交換
? ? ? ? ? ? ? ? int temp = arr[i];
? ? ? ? ? ? ? ? arr[i] = arr[j];
? ? ? ? ? ? ? ? arr[j] = temp;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? //最后將基準為與i和j相等位置的數(shù)字交換
? ? ? ? arr[begin] = arr[i];
? ? ? ? arr[i] = base;
? ? ? ? quickSort(arr, begin, i - 1); //遞歸調(diào)用左半數(shù)組
? ? ? ? quickSort(arr, i + 1, end); //遞歸調(diào)用右半數(shù)組
? ? }
? ? //快排序降序
? ? public static void quickSortDescending(int[] arr, int begin, int end) {
? ? ? ? if (begin > end) { //結束條件
? ? ? ? ? ? return;
? ? ? ? }
? ? ? ? int base = arr[begin];
? ? ? ? int i = begin, j = end;
? ? ? ? while (i < j) { // 兩個哨兵（i左邊，j右邊）沒有相遇
? ? ? ? ? ? while (arr[j] <= base && i < j) { //哨兵j沒找到比base大的
? ? ? ? ? ? ? ? j--;
? ? ? ? ? ? }
? ? ? ? ? ? while (arr[i] >= base && i < j) { //哨兵i沒找到比base小的
? ? ? ? ? ? ? ? i++;
? ? ? ? ? ? }
? ? ? ? ? ? if (i < j) { //如果滿足條件則交換
? ? ? ? ? ? ? ? int temp = arr[i];
? ? ? ? ? ? ? ? arr[i] = arr[j];
? ? ? ? ? ? ? ? arr[j] = temp;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? //最后將基準為與i和j相等位置的數(shù)字交換
? ? ? ? arr[begin] = arr[i];
? ? ? ? arr[i] = base;
? ? ? ? quickSortDescending(arr, begin, i - 1); //遞歸調(diào)用左半數(shù)組
? ? ? ? quickSortDescending(arr, i + 1, end); //遞歸調(diào)用右半數(shù)組
? ? }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
直接選擇排序
簡單解釋：
數(shù)組分為已排序部分（前面）和待排序序列（后面）
第一次肯定所有的數(shù)都是待排序的
從待排序的序列中找到最大或最小的那個元素，放到前面的已排序部分，然后一直找，不斷縮小待排序的范圍，直到所有的數(shù)都是已排序的了
完整代碼：
package com.keafmd.Sequence;
/**
?* Keafmd
?*
?* @ClassName: SelectSort
?* @Description: 選擇排序
?* @author: 牛哄哄的柯南
?* @date: 2021-06-24 10:33
?*/
public class SelectSort {
? ? //直接選擇排序
? ? public static void selectSort(int[] arr, boolean ascending) {
? ? ? ? for (int i = 0; i < arr.length; i++) {
? ? ? ? ? ? int m = i; //最小值或最小值的下標
? ? ? ? ? ? for (int j = i + 1; j < arr.length; j++) {
? ? ? ? ? ? ? ? if (ascending ? arr[j] < arr[m] : arr[j] > arr[m]) {
? ? ? ? ? ? ? ? ? ? m = j; //找到待排序的數(shù)中最小或最大的那個數(shù)，記錄下標
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? ? ? //交換位置
? ? ? ? ? ? int temp = arr[i];
? ? ? ? ? ? arr[i] = arr[m];
? ? ? ? ? ? arr[m] = temp;
? ? ? ? }
? ? }
? ? public static void selectSort(int[] arr) {
? ? ? ? selectSort(arr, true);
? ? }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
堆排序
先理解下大頂堆和小頂堆，看圖
大頂堆，雙親結點的值比每一個孩子結點的值都要大。根結點值最大
小頂堆，雙親結點的值比每一個孩子結點的值都要小。根結點值最小
簡單解釋：
構建好大頂堆或小頂堆結構，這樣最上面的就是最大值或最小值，那么我們?nèi)〕龆秧斣?#xff0c;然后重新構建結構，一直取，一直重新構建，那么最后達到排序的效果了。
完整代碼：
package com.keafmd.Sequence;
/**
?* Keafmd
?*
?* @ClassName: HeapSort
?* @Description: 堆排序
?* @author: 牛哄哄的柯南
?* @date: 2021-06-24 10:34
?*/
public class HeapSort {
? ? //堆排序
? ? public static void heapSort(int[] arr) {
? ? ? ? //對傳入的數(shù)組進行建立堆，這里默認建立大頂堆，進行升序排列
? ? ? ? heapSort(arr, true);
? ? }
? ? public static void heapSort(int[] arr, boolean maxheap) {
? ? ? ? //1.構建大頂堆
? ? ? ? for (int i = arr.length / 2 - 1; i >= 0; i--) {
? ? ? ? ? ? //從第一個非葉子結點從下至上，從右至左調(diào)整結構
? ? ? ? ? ? sift(arr, i, arr.length , maxheap);
? ? ? ? }
? ? ? ? //2.調(diào)整堆結構+交換堆頂元素與末尾元素
? ? ? ? for (int j = arr.length - 1; j > 0; j--) {
? ? ? ? ? ? //現(xiàn)在的數(shù)組第一個就是根結點，最小值所在，進行交換，把它放到最右邊
? ? ? ? ? ? int temp = arr[j];
? ? ? ? ? ? arr[j] = arr[0];
? ? ? ? ? ? arr[0] = temp;
? ? ? ? ? ? //重新建立堆
? ? ? ? ? ? sift(arr, 0, j , maxheap); //重新對堆進行調(diào)整
? ? ? ? }
? ? }
? ? //建立堆的方法
? ? /**
? ? ?* 私有方法，只允許被堆排序調(diào)用
? ? ?*
? ? ?* @param arr ? ? 要排序數(shù)組
? ? ?* @param parent ?當前的雙親節(jié)點
? ? ?* @param len ? ? 數(shù)組長度
? ? ?* @param maxheap 是否建立大頂堆
? ? ?*/
? ? private static void sift(int[] arr, int parent, int len, boolean maxheap) {
? ? ? ? int value = arr[parent]; //先取出當前元素i
? ? ? ? for (int child = 2 * parent + 1; child < len; child = child * 2 + 1) { //從parent結點的左子結點開始，也就是2*parent+1處開始
? ? ? ? ? ? if (child+1 < len && (maxheap ? arr[child] < arr[child + 1] : arr[child] > arr[child + 1])) { //如果左子結點小于右子結點，child指向右子結點
? ? ? ? ? ? ? ? child++; //右孩子如果比左孩子大，我們就將現(xiàn)在的孩子換到右孩子
? ? ? ? ? ? }
? ? ? ? ? ? //判斷是否符合大頂堆的特性， 如果右孩子大于雙親，自然左孩子也大于雙親，符合
? ? ? ? ? ? //如果子節(jié)點大于父節(jié)點，將子節(jié)點值賦給父節(jié)點（不用進行交換)
? ? ? ? ? ? if (maxheap ? value < arr[child] : value > arr[child]) {
? ? ? ? ? ? ? ? arr[parent]=arr[child];
? ? ? ? ? ? ? ? parent = child;
? ? ? ? ? ? }
? ? ? ? ? ? else {//如果不是，說明已經(jīng)符合我們的要求了。
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? arr[parent] =value; //將value值放到最終的位置
? ? }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
歸并排序
簡單解釋：
該算法是采用分治法，把數(shù)組不斷分割，直至成為單個元素，然后比較再合并（合并的過程就是兩部分分別從頭開始比較，取出最小或最大元素的放到新的區(qū)域內(nèi)，繼續(xù)取兩部分中最大或最小的元素，直到這兩部分合并完，最后所有的都合并完，最后形成完整的有序序列）
完整代碼：
package com.keafmd.Sequence;
/**
?* Keafmd
?*
?* @ClassName: MergeSort
?* @Description: 歸并排序
?* @author: 牛哄哄的柯南
?* @date: 2021-06-24 10:35
?*/
public class MergeSort {
? ? //歸并排序
? ? public static void mergeSort(int []arr ,boolean ascending){
? ? ? ? int[] temp = new int[arr.length]; //在排序前，先建好一個長度等于原數(shù)組長度的臨時數(shù)組，避免遞歸中頻繁開辟空間
? ? ? ? mergeSort(arr,0,arr.length-1,temp,ascending);
? ? }
? ? public static void mergeSort(int []arr){
? ? ? ? mergeSort(arr,true);
? ? }
? ? /**
? ? ?*
? ? ?* @param arr 傳入的數(shù)組
? ? ?* @param left 當前子數(shù)組的起始下標
? ? ?* @param right 當前子數(shù)組的結束下標
? ? ?* @param temp 拷貝暫存數(shù)組
? ? ?*/
? ? public static void mergeSort(int []arr,int left,int right,int[] temp,boolean ascending){
? ? ? ? if(left
? ? ? ? ? ? //對半分，比如總長度是10，left=0，right=9，mid=4確實是中間分了，0~4，5~9
? ? ? ? ? ? //當長度9，left=0，right=8，mid=4，0~4，5~8
? ? ? ? ? ? int mid = left + (right-left)/2; // 防止越界的寫法
? ? ? ? ? ? //int mid = (left+right)/2;
? ? ? ? ? ? mergeSort(arr,left,mid,temp,ascending); //左邊歸并排序，使得左子序列有序
? ? ? ? ? ? mergeSort(arr,mid+1,right,temp,ascending); //右邊歸并排序，使得右子序列有序
? ? ? ? ? ? merge(arr,left,mid,right,temp,ascending); //將兩個有序子數(shù)組合并操作
? ? ? ? }
? ? }
? ? private static void merge(int[] arr,int left,int mid,int right,int[] temp,boolean ascending){
? ? ? ? int i = left; //左序列起始下標
? ? ? ? int j = mid+1; //右序列起始下標
? ? ? ? int t = 0; //臨時數(shù)組指針
? ? ? ? while(i<=mid&&j<=right){
? ? ? ? ? ? if(ascending?arr[i]arr[j]){ //比較兩個序列第一個元素誰小，誰小先拷貝誰到temp，然后對應子序列下標加1
? ? ? ? ? ? ? ? temp[t++] = arr[i++];
? ? ? ? ? ? }else {
? ? ? ? ? ? ? ? temp[t++] = arr[j++];
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? while(i<=mid){ //將左邊剩余元素填充進temp中——左序列有一些數(shù)總是比右邊的大的數(shù)
? ? ? ? ? ? temp[t++] = arr[i++];
? ? ? ? }
? ? ? ? while(j<=right){ //將右序列剩余元素填充進temp中——右序列有一些數(shù)總是比左邊的大的數(shù)
? ? ? ? ? ? temp[t++] = arr[j++];
? ? ? ? }
? ? ? ? t = 0;
? ? ? ? //將temp中的元素全部拷貝到原數(shù)組中
? ? ? ? while(left<=right){
? ? ? ? ? ? arr[left++] = temp[t++];
? ? ? ? }
? ? }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
插入排序
簡單解釋：
最簡單的理解就是打地主時我們拿到牌后的整理過程，從第二個牌（假設我們拿起來這個牌開始比較）開始，（說下升序）從后往前比較如果比前面的那個牌小，就把牌往后移動，直到找到一個合適的位置（這個位置的前面的那個牌不比這個要放下的牌大）就把這個牌放到這個位置，慢慢的前面的部分變得有序，直至全部有序即可。
完整代碼：
package com.keafmd.Sequence;
/**
?* Keafmd
?*
?* @ClassName: StraghtInsertSort
?* @Description: 插入排序
?* @author: 牛哄哄的柯南
?* @date: 2021-06-24 10:36
?*/
public class StraghtInsertSort {
? ? //插入排序
? ? public static void straghtInsertSort(int[] arr) {
? ? ? ? straghtInsertSort(arr, true);//默認進行升序
? ? }
? ? public static void straghtInsertSort(int[] arr, boolean ascending) {
? ? ? ? for (int i = 1; i < arr.length; i++) {
? ? ? ? ? ? int temp = arr[i];
? ? ? ? ? ? int j=0; //這就是那個合適的位置
? ? ? ? ? ? for (j = i - 1; j >= 0 && (ascending ? temp < arr[j] : temp > arr[j]); j--) {
? ? ? ? ? ? ? ? arr[j + 1] = arr[j];
? ? ? ? ? ? }
? ? ? ? ? ? //把牌放下，為啥是j+1，
? ? ? ? ? ? //是因為上面的循環(huán)遍歷到不符合情況的時候 j是合適的位置的前面的那個數(shù)的位置
? ? ? ? ? ? //有點拗口，但是就是這個意思，看圖方便理解下
? ? ? ? ? ? arr[j + 1] = temp;
? ? ? ? }
? ? }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
希爾排序
簡單解釋：
希爾排序是插入排序的改進版，我們理解一個叫做下標差的的東西，也就是下面那個圖中的增量d，初始下標差為arr.length/2，然后繼續(xù)/2，對在同一下標差（相當于把這幾個數(shù)單獨拿出來了）的若干個數(shù)進行插入排序即可。
完整代碼：
package com.keafmd.Sequence;
/**
?* Keafmd
?*
?* @ClassName: ShellSort
?* @Description: 希爾排序
?* @author: 牛哄哄的柯南
?* @date: 2021-06-24 10:39
?*/
public class ShellSort {
? ? public static void shellSort(int[] arr) {
? ? ? ? shellSort(arr,true);
? ? }
? ? public static void shellSort(int[] arr,boolean ascending) {
? ? ? ? for(int d = arr.length/2;d>0;d/=2){
? ? ? ? ? ? for(int i=d;i< arr.length;i++){
? ? ? ? ? ? ? ? int temp = arr[i];
? ? ? ? ? ? ? ? int j=0;
? ? ? ? ? ? ? ? for(j=i-d;j>=0&&(ascending?temparr[j]);j-=d){
? ? ? ? ? ? ? ? ? ? arr[j+d]=arr[j];
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? arr[j+d] = temp;
? ? ? ? ? ? }
? ? ? ? }
? ? }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
計數(shù)排序
簡單解釋：
這個排序算法看名字也很好理解，就是就是額外找個數(shù)組來計數(shù)，然后在這個數(shù)組從小到大或從大到小把數(shù)取出來即可。
完整代碼：
package com.keafmd.Sequence;
/**
?* Keafmd
?*
?* @ClassName: CountSort
?* @Description: 計數(shù)排序
?* @author: 牛哄哄的柯南
?* @date: 2021-06-24 11:31
?*/
public class CountSort {
? ? public static void countSort(int[]arr){
? ? ? ? countSort(arr,true);
? ? }
? ? public static void countSort(int[]arr,boolean ascending){
? ? ? ? int d,min=arr[0],max=arr[0];
? ? ? ? //找出最大、最小值
? ? ? ? for(int i=0;i< arr.length;i++){
? ? ? ? ? ? if(arr[i] ? ? ? ? ? ? ? ? min =arr[i];
? ? ? ? ? ? }
? ? ? ? ? ? if(arr[i]>max){
? ? ? ? ? ? ? ? max = arr[i];
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? //建立一個用于計數(shù)的數(shù)組
? ? ? ? d = min;
? ? ? ? int[] count_map = new int[max-min+1];
? ? ? ? for(int i=0;i< arr.length;i++){
? ? ? ? ? ? count_map[arr[i]-d]++;
? ? ? ? }
? ? ? ? int k =0;
? ? ? ? if(ascending){
? ? ? ? ? ? for(int i=0;i< arr.length;){
? ? ? ? ? ? ? ? if(count_map[k]>0){
? ? ? ? ? ? ? ? ? ? arr[i] = k+d;
? ? ? ? ? ? ? ? ? ? i++;
? ? ? ? ? ? ? ? ? ? count_map[k]--;
? ? ? ? ? ? ? ? }else
? ? ? ? ? ? ? ? ? ? k++;
? ? ? ? ? ? }
? ? ? ? }else {
? ? ? ? ? ? for(int i=arr.length-1;i>=0;){
? ? ? ? ? ? ? ? if(count_map[k]>0){
? ? ? ? ? ? ? ? ? ? arr[i] = k+d;
? ? ? ? ? ? ? ? ? ? i--;
? ? ? ? ? ? ? ? ? ? count_map[k]--;
? ? ? ? ? ? ? ? }else
? ? ? ? ? ? ? ? ? ? k++;
? ? ? ? ? ? }
? ? ? ? }
? ? }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
桶排序
簡單解釋：
就是把一個數(shù)組分成幾個桶（其實是幾個區(qū)間，從小到大或從大到小的幾個區(qū)間）裝，然后讓每個桶（區(qū)間）有序，然后取出來放一起就可以了，相當于把幾個有序的段拿出來放一起，自然還是有序的，當然需要是按照區(qū)間的順序拿了。
完整代碼：
package com.keafmd.Sequence;
import java.util.ArrayList;
import java.util.Collections;
/**
?* Keafmd
?*
?* @ClassName: BucketSort
?* @Description: 桶排序
?* @author: 牛哄哄的柯南
?* @date: 2021-06-24 13:32
?*/
public class BucketSort {
? ? public static void bucketSort(int[] arr){
? ? ? ? bucketSort(arr,true);
? ? }
? ? public static void bucketSort(int[] arr,boolean ascending){
? ? ? ? if(arr==null||arr.length==0){
? ? ? ? ? ? return;
? ? ? ? }
? ? ? ? //計算最大值與最小值
? ? ? ? int max = Integer.MIN_VALUE;
? ? ? ? int min = Integer.MAX_VALUE;
? ? ? ? for(int i=0;i ? ? ? ? ? ? max = Math.max(arr[i],max);
? ? ? ? ? ? min = Math.min(arr[i],min);
? ? ? ? }
? ? ? ? //計算桶的數(shù)量
? ? ? ? int bucketNUm = (max-min)/ arr.length+1;
? ? ? ? ArrayList> bucketArr = new ArrayList<>(bucketNUm);
? ? ? ? for(int i=0;i ? ? ? ? ? ? bucketArr.add(new ArrayList<>());
? ? ? ? }
? ? ? ? //將每個元素放入桶中
? ? ? ? for(int i=0;i ? ? ? ? ? ? int num = (arr[i]-min)/ (arr.length);
? ? ? ? ? ? bucketArr.get(num).add(arr[i]);
? ? ? ? }
? ? ? ? //對每個桶進行排序
? ? ? ? for (int i = 0; i < bucketArr.size(); i++) {
? ? ? ? ? ? //用系統(tǒng)的排序，速度肯定沒話說
? ? ? ? ? ? Collections.sort(bucketArr.get(i));
? ? ? ? }
? ? ? ? //將桶中元素賦值到原序列
? ? ? ? int index;
? ? ? ? if(ascending){
? ? ? ? ? ? index=0;
? ? ? ? }else{
? ? ? ? ? ? index=arr.length-1;
? ? ? ? }
? ? ? ? for(int i=0;i ? ? ? ? ? ? for(int j= 0;j ? ? ? ? ? ? ? ? arr[index] = bucketArr.get(i).get(j);
? ? ? ? ? ? ? ? if(ascending){
? ? ? ? ? ? ? ? ? ? index++;
? ? ? ? ? ? ? ? }else{
? ? ? ? ? ? ? ? ? ? index--;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
基數(shù)排序
簡單解釋：
首先說一下，我發(fā)現(xiàn)好多人寫的基數(shù)排序只能排序正整數(shù)，其實只要處理下就可以排序含有負數(shù)的了，就是我們排序前先把所有的數(shù)整體變大（就是減上最小的負數(shù)，也就是加了），都變成正數(shù)，然后排序好之后，在減下來（加上最小的負數(shù)，也就減了）就好了。
基數(shù)排序就是按數(shù)位排序可分為LSD（從最低位[也就是個位]開始排序）和MSD（從最高位開始排序），下面寫的事LSD基數(shù)排序。
基數(shù)排序就是把數(shù)按位考慮，讓后我們一位數(shù)只能是[0，9]，就是我們在考慮某位（個位、百位· · ·）的時候就只看這個位的數(shù)，放到在[0，9]相應的位置，然后順序取出，最后再按其它位這樣操作（上面說了要不從低位開始到高位，要不就是從高位到低位）
完整代碼：
package com.keafmd.Sequence;
/**
?* Keafmd
?*
?* @ClassName: RadixSort
?* @Description: 基數(shù)排序
?* @author: 牛哄哄的柯南
?* @date: 2021-06-24 14:32
?*/
public class RadixSort {
? ? public static void radixSort(int[] arr){
? ? ? ? radixSort(arr,true);
? ? }
? ? public static void radixSort(int[]arr,boolean ascending){
? ? ? ? int max = Integer.MIN_VALUE;
? ? ? ? int min = Integer.MAX_VALUE;
? ? ? ? //求出最大值、最小值
? ? ? ? for (int i = 0; i < arr.length; i++) {
? ? ? ? ? ? max = Math.max(max, arr[i]);
? ? ? ? ? ? min = Math.min(min, arr[i]);
? ? ? ? }
? ? ? ? if (min<0) {?? ?//如果最小值小于0，那么把每個數(shù)都減去最小值，這樣可以保證最小的數(shù)是0
? ? ? ? ? ? for (int i = 0; i < arr.length; i++) {
? ? ? ? ? ? ? ? arr[i] -= min;
? ? ? ? ? ? }
? ? ? ? ? ? max -= min; //max也要處理！
? ? ? ? }
? ? ? ? //很巧妙求出最大的數(shù)有多少位
? ? ? ? int maxLength = (max+"").length();
? ? ? ? int[][] bucket = new int[10][arr.length]; //一個二維數(shù)組，一維代表0到9，二維存放符合數(shù)
? ? ? ? int[] bucketElementCount = new int[10]; // 用于記錄0到9某位存在數(shù)字的個數(shù)
? ? ? ? for (int i = 0 ,n = 1 ; i < maxLength ; i++,n*=10) { //個位 十位 百位 這樣遍歷
? ? ? ? ? ? for (int j = 0; j < arr.length ; j++) {
? ? ? ? ? ? ? ? int value = arr[j]/n % 10;
? ? ? ? ? ? ? ? bucket[value][bucketElementCount[value]] = arr[j];
? ? ? ? ? ? ? ? bucketElementCount[value]++;
? ? ? ? ? ? }
? ? ? ? ? ? //升序
? ? ? ? ? ? if(ascending) {
? ? ? ? ? ? ? ? int index = 0;
? ? ? ? ? ? ? ? //從左到右，從下到上取出每個數(shù)
? ? ? ? ? ? ? ? for (int j = 0; j < bucketElementCount.length; j++) {
? ? ? ? ? ? ? ? ? ? if (bucketElementCount[j] != 0) {
? ? ? ? ? ? ? ? ? ? ? ? for (int k = 0; k < bucketElementCount[j]; k++) {
? ? ? ? ? ? ? ? ? ? ? ? ? ? arr[index] = bucket[j][k];
? ? ? ? ? ? ? ? ? ? ? ? ? ? index++;
? ? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? bucketElementCount[j] = 0;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }else { // 降序
? ? ? ? ? ? ? ? int index=0;
? ? ? ? ? ? ? ? //從右到左，從下到上取出每個數(shù)
? ? ? ? ? ? ? ? for (int j = bucketElementCount.length-1; j >=0; j--) {
? ? ? ? ? ? ? ? ? ? if (bucketElementCount[j] != 0) {
? ? ? ? ? ? ? ? ? ? ? ? for (int k = 0; k ? ? ? ? ? ? ? ? ? ? ? ? ? ? arr[index] = bucket[j][k];
? ? ? ? ? ? ? ? ? ? ? ? ? ? index++;
? ? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? bucketElementCount[j] = 0;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? ? ? /*for (int i1 = 0; i1 < arr.length; i1++) {
? ? ? ? ? ? ? ? System.out.print(arr[i1]+" ");
? ? ? ? ? ? }
? ? ? ? ? ? System.out.println();*/
? ? ? ? }
? ? ? ? if (min<0){
? ? ? ? ? ? for (int i = 0; i < arr.length ; i++) {
? ? ? ? ? ? ? ? arr[i] += min;
? ? ? ? ? ? }
? ? ? ? }
? ? }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
完整測試類
package com.keafmd.Sequence;
import java.util.*;
import java.util.stream.IntStream;
import java.util.stream.Stream;
/**
?* Keafmd
?*
?* @ClassName: Sort
?* @Description: 十大排序算法測試類
?* @author: 牛哄哄的柯南
?* @date: 2021-06-16 21:27
?*/
public class Sort {
? ? public static void main(String[] args) {
? ? ? ? int[] nums = {12, 4, 25, 47, 58, 34, 25, 9, 99, 26, 1, -13, 162, 10093, -66, -1};
// ? ? ? ?int[] nums = {12, 43,56,42,26,11};
? ? ? ? int[] temparr;
? ? ? ? //利用系統(tǒng)Collections.sort方法進行對比
? ? ? ? //將int數(shù)組轉換為Integer數(shù)組
? ? ? ? //1、先將int數(shù)組轉換為數(shù)值流
? ? ? ? temparr = nums.clone();
? ? ? ? IntStream stream = Arrays.stream(temparr);
? ? ? ? //2、流中的元素全部裝箱，轉換為流 ---->int轉為Integer
? ? ? ? Stream integerStream = stream.boxed();
? ? ? ? //3、將流轉換為數(shù)組
? ? ? ? Integer[] integers = integerStream.toArray(Integer[]::new);
? ? ? ? //把數(shù)組轉為List
? ? ? ? List tempList = new ArrayList<>(Arrays.asList(integers));
? ? ? ? //使用Collections.sort()排序
? ? ? ? System.out.println("使用系統(tǒng)的Collections.sort()的對比:");
? ? ? ? //Collections.sort
? ? ? ? Collections.sort(tempList, new Comparator() {
? ? ? ? ? ? @Override
? ? ? ? ? ? public int compare(Integer o1, Integer o2) {
? ? ? ? ? ? ? ? return o1-o2;
? ? ? ? ? ? ? ? //return o2-o1;
? ? ? ? ? ? }
? ? ? ? });
? ? ? ? //tempList.sort 也可以排序
? ? ? ?/* tempList.sort(new Comparator() {
? ? ? ? ? ? @Override
? ? ? ? ? ? public int compare(Integer o1, Integer o2) {
? ? ? ? ? ? ? ? //return o1-o2;
? ? ? ? ? ? ? ? return o2-o1;
? ? ? ? ? ? }
? ? ? ? });*/
? ? ? ? //遍歷輸出結果
? ? ? ? for (Integer integer : tempList) {
? ? ? ? ? ? System.out.print(integer+" ");
? ? ? ? }
? ? ? ? System.out.println();
? ? ? ? //測試冒泡排序
? ? ? ? System.out.println("測試冒泡排序:");
? ? ? ? temparr = nums.clone();
? ? ? ? BubbleSort.bubbleSort(temparr);
? ? ? ? //降序
? ? ? ? //BubbleSort.bubbleSort(temparr,false);
? ? ? ? for (int i = 0; i < temparr.length; i++) {
? ? ? ? ? ? System.out.print(temparr[i] + " ");
? ? ? ? }
? ? ? ? System.out.println();
? ? ? ? //測試快速排序
? ? ? ? System.out.println("測試快速排序:");
? ? ? ? temparr = nums.clone();
? ? ? ? QuickSort.quickSort(temparr);
? ? ? ? //QuickSort.quickSort(temparr,false);
? ? ? ? for (int i = 0; i < temparr.length; i++) {
? ? ? ? ? ? System.out.print(temparr[i] + " ");
? ? ? ? }
? ? ? ? System.out.println();
? ? ? ? //測試直接選擇排序
? ? ? ? System.out.println("測試直接選擇排序:");
? ? ? ? temparr = nums.clone();
? ? ? ? SelectSort.selectSort(temparr);
? ? ? ? //SelectSort.selectSort(temparr,false);
? ? ? ? for (int i = 0; i < temparr.length; i++) {
? ? ? ? ? ? System.out.print(temparr[i] + " ");
? ? ? ? }
? ? ? ? System.out.println();
? ? ? ? //測試堆排序
? ? ? ? System.out.println("測試堆排序:");
? ? ? ? temparr = nums.clone();
? ? ? ? HeapSort.heapSort(temparr);
? ? ? ? //HeapSort.heapSort(temparr,false);
? ? ? ? for (int i = 0; i < temparr.length; i++) {
? ? ? ? ? ? System.out.print(temparr[i] + " ");
? ? ? ? }
? ? ? ? System.out.println();
? ? ? ? //測試歸并排序
? ? ? ? System.out.println("測試歸并排序:");
? ? ? ? temparr = nums.clone();
? ? ? ? MergeSort.mergeSort(temparr);
? ? ? ? //MergeSort.mergeSort(temparr,false);
? ? ? ? for (int i = 0; i < temparr.length; i++) {
? ? ? ? ? ? System.out.print(temparr[i] + " ");
? ? ? ? }
? ? ? ? System.out.println();
? ? ? ? //測試插入排序
? ? ? ? System.out.println("測試插入排序:");
? ? ? ? temparr = nums.clone();
? ? ? ? StraghtInsertSort.straghtInsertSort(temparr);
? ? ? ? //StraghtInsertSort.straghtInsertSort(temparr,false);
? ? ? ? for (int i = 0; i < temparr.length; i++) {
? ? ? ? ? ? System.out.print(temparr[i] + " ");
? ? ? ? }
? ? ? ? System.out.println();
? ? ? ? //測試希爾排序
? ? ? ? System.out.println("測試希爾排序:");
? ? ? ? temparr = nums.clone();
? ? ? ? ShellSort.shellSort(temparr);
? ? ? ? //ShellSort.shellSort(temparr,false);
? ? ? ? for (int i = 0; i < temparr.length; i++) {
? ? ? ? ? ? System.out.print(temparr[i] + " ");
? ? ? ? }
? ? ? ? System.out.println();
? ? ? ? //測試計數(shù)排序
? ? ? ? System.out.println("測試計數(shù)排序:");
? ? ? ? temparr = nums.clone();
? ? ? ? CountSort.countSort(temparr);
? ? ? ? //CountSort.countSort(temparr,false);
? ? ? ? for (int i = 0; i < temparr.length; i++) {
? ? ? ? ? ? System.out.print(temparr[i] + " ");
? ? ? ? }
? ? ? ? System.out.println();
? ? ? ? //測試桶排序
? ? ? ? System.out.println("測試桶排序:");
? ? ? ? temparr = nums.clone();
? ? ? ? BucketSort.bucketSort(temparr);
? ? ? ? //BucketSort.bucketSort(temparr,false);
? ? ? ? for (int i = 0; i < temparr.length; i++) {
? ? ? ? ? ? System.out.print(temparr[i] + " ");
? ? ? ? }
? ? ? ? System.out.println();
? ? ? ? //測試基數(shù)排序
? ? ? ? System.out.println("測試基數(shù)排序:");
? ? ? ? temparr = nums.clone();
? ? ? ? RadixSort.radixSort(temparr);
? ? ? ? //RadixSort.radixSort(temparr,false);
? ? ? ? for (int i = 0; i < temparr.length; i++) {
? ? ? ? ? ? System.out.print(temparr[i] + " ");
? ? ? ? }
? ? ? ? System.out.println();
? ? }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
每天進步一點點！
不進則退！
版權聲明：
原創(chuàng)博主：牛哄哄的柯南
博主原文鏈接：https://keafmd.blog.csdn.net/
看完如果對你有幫助，感謝點贊支持！
如果你是電腦端，看到右下角的 “一鍵三連” 了嗎，沒錯點它[哈哈]
加油！
共同努力！
Keafmd
————————————————
版權聲明：本文為CSDN博主「牛哄哄的柯南」的原創(chuàng)文章，遵循CC 4.0 BY-SA版權協(xié)議，轉載請附上原文出處鏈接及本聲明。
原文鏈接：https://blog.csdn.net/weixin_43883917/article/details/118193663
總結
以上是生活随笔為你收集整理的经典十大排序算法（含升序降序，基数排序含负数排序）【Java版完整代码】【建议收藏系列】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 紫涵名字的寓意
- 下一篇： 芸字取名的寓意是什么？