原始链接：https://blog.csdn.net/yuan_qh/article/details/100139910

十大经典排序算法的java实现以及原理讲解

首先，这篇博客的来源是因为我在学习排序算法的时候，看到了一位大神写的十大经典排序算法，写的真的很不错，可是遗憾的是没有java版本实现，所以我按照每个排序来写了一个java版本实现，如有错误，欢迎指正。

所以说，学习这篇文章时，建议和十大经典排序算法一起看。

1、冒泡排序

1. package cn.yqh.interview.sort;

2.  
3.  

4. /**

5. * @author 袁

6. * @create 2019/8/27-15:27

7. */

8. public class BubbleSort {

9. public static int[] bubbleSort(int[] array) {

10. if (array == null || array.length == 0) {

11. return null;

12. }

13. for (int i = 0; i

14. for (int j = 0; j

15. if (array[j]

16. swap(array, j, j + 1);

17. }

18. }

19. }

20. return array;

21. }

22.  

23. private static void swap(int[] arr, int i, int i1) {

24. int tem = arr[i];

25. arr[i] = arr[i1];

26. arr[i1] = tem;

27. }

28.  

29. public static void main(String[] args) {

30. int[] arr = {5, 3, 7, 2, 9, 4, 1};

31. int[] sort = bubbleSort(arr);

32. for (int i : sort) {

33. System.out.print(i + " ");

34. }

35. }

36. }




2、选择排序

1. package cn.yqh.interview.sort;

2.  
3.  

4. /**

5. * @author 袁

6. * @create 2019/8/27-15:27

7. */

8. public class SelectionSort {

9. public static int[] selectionSort(int[] array) {

10. if (array == null || array.length == 0) {

11. return null;

12. }

13. for (int i = 0; i

14. //先假设每次循环时，最小（大）数的索引为i

15. int minIndex = i;

16. //每一个元素都和剩下的未排序的元素比较

17. for (int j = i + 1; j

18. if (array[minIndex] > array[j]) minIndex = j; //第一次写代码犯错：每比较一次，就交换一次，这样显然没有记录最小值的索引然后在最后交换一次的好

19. } //第二次写代码犯错：这里应该是array[minIndex] > array[j]比较，而不是array[i] > array[j]比较

20.  

21. //进过一轮循环，即可找出第一个最值的索引，然后把最值放到i的位置

22. swap(array, i, minIndex);

23.  

24. }

25. return array;

26. }

27.  

28. private static void swap(int[] arr, int i, int i1) {

29. int tem = arr[i];

30. arr[i] = arr[i1];

31. arr[i1] = tem;

32. }

33.  

34. public static void main(String[] args) {

35. int[] arr = {5, 3, 7, 2, 9, 4, 1};

36. int[] sort = selectionSort(arr);

37. for (int i : sort) {

38. System.out.print(i + " ");

39. }

40. }

41. }




3、插入排序

1. package cn.yqh.interview.sort;

2.  
3.  

4. /**

5. * @author 袁

6. * @create 2019/8/27-15:27

7. */

8. public class InsertionSort {

9.  
10.  

11. // 版本1，双for循环

12. public static int[] insertionSort(int[] array) {

13.  

14. int current, index;

15.  

16. if (array == null && array.length == 0) {

17. return null;

18. }

19. for (int i = 1; i

20.  

21. current = array[i]; //取出元素

22. index = i; //记下当前元素的索引位置

23.  

24. for (int j = i - 1; j >= 0; j--) {

25. if (current

26. array[j + 1] = array[j]; //将这个较大的结点后移

27. index = j; //通过index记下current将要放置的位置

28. }

29. }

30. if (index != i) array[index] = current; //如果array刚刚好是有顺序的，则到这里时，这个元素就不用移动了

31. }

32. return array;

33. }

34.  

35. // 版本2，for循环加while循环（大众版本）

36. public static int[] insertionSort2(int[] array) {

37.  

38. int current, index, j;

39.  

40. if (array == null || array.length == 0) {

41. return null;

42. }

43. for (int i = 1; i

44.  

45. current = array[i]; //取出元素,避免若前面的元素小于当前元素，前面元素后移导致当前元素被覆盖

46. index = i; //记下当前元素的索引位置

47. j = i-1; //记录当前元素的前一个元素的位置

48.  

49. while (j >= 0 && array[j] > current) {

50. array[j+1] = array[j]; //元素后移

51. index = j--; //先赋值再减减（j--就是继续往前寻找组中前面的元素）

52.  

53. }

54. if (index != i) array[index] = current; //如果array刚刚好是有顺序的，则到这里时，这个元素就不用移动了

55. //也可以不适用index，直接用最后的j+1，其实和index是一样的，这里加入index为了更好理解

56. }

57. return array;

58. }

59.  
60.  

61. public static void main(String[] args) {

62. int[] arr = {5, 3, 7, 2, 9, 4, 1};

63. int[] sort = insertionSort2(arr);

64. for (int i : sort) {

65. System.out.print(i + " ");

66. }

67. }

68. }




4、希尔排序

1. package cn.yqh.interview.sort;

2.  

3. /**

4. * @author 袁

5. * @create 2019/8/27-19:33

6. */

7. public class ShellSort {

8.  
9.  

10. public static int[] shellSort(int[] array) {

11.  

12. int current, index, j;

13.  

14. if (array == null || array.length == 0) {

15. return null;

16. }

17.  

18. for (int gap = array.length / 2; gap > 0; gap = gap / 2) { //选取gap，采用推荐的默认/2取gap的方式

19. for (int i = gap; i

20. //接下来采用插入排序对每个组进行排序

21. current = array[i]; //取出当前元素，避免前组中前一个元素后移导致此元素被覆盖

22. j = i - gap; //取得这个组中的前一个元素的位置

23. while (j >= 0 && array[j] > current) {

24. array[j + gap] = array[j]; //元素后移,注意移动的个数为gap，第一次编程写错了array[j + 1] = array[j];

25. j -= gap; //j继续往前寻找组中前面的元素

26. }

27. array[j + gap] = current; //j+gpa即为array[i]该移动的位置

28. }

29. }

30.  

31. return array;

32. }

33.  
34.  

35. public static void main(String[] args) {

36. int[] arr = {5, 3, 7, 2, 9, 4, 1};

37. int[] sort = shellSort(arr);

38. for (int i : sort) {

39. System.out.print(i + " ");

40. }

41. }

42. }

43.  
44.  
45.  



5、归并排序

1. package cn.yqh.interview.sort;

2.  

3. /**

4. * @author 袁

5. * @create 2019/8/27-19:33

6. */

7. public class MergeSort {

8.  
9.  

10. public static int[] sort(int[] a, int low, int high) {

11. int mid = (low + high) / 2;

12. if (low

13. sort(a, low, mid);

14. sort(a, mid + 1, high);

15. merge(a, low, mid, high);

16. }

17. return a;

18. }

19.  

20. public static void merge(int[] a, int low, int mid, int high) {

21. if (a == null || a.length == 0) {

22. return;

23. }

24.  

25. int[] temp = new int[high - low + 1];

26. int k = 0; //记录temp数组的下标

27. int i = low, j = mid + 1; //定义两个指针，i指向前一半的第一个元素的位置，j指向mid+1的位置

28. while (i <= mid && j <= high) {

29. if (a[i]

30. temp[k++] = a[i++];

31. } else {

32. temp[k++] = a[j++];

33. }

34. }

35.  

36. while (i <= mid) {

37. temp[k++] = a[i++];

38. }

39.  
40.  

41. while (j <= high) {

42. temp[k++] = a[j++];

43. }

44.  

45. for (int l = 0; l

46. a[low + l] = temp[l];

47. }

48. }

49.  
50.  

51. public static void main(String[] args) {

52. int[] arr = {5, 3, 7, 2, 9, 4, 1};

53. int[] sort = sort(arr, 0, 6);

54. for (int i : sort) {

55. System.out.print(i + " ");

56. }

57.  

58. }

59. }

60.  
61.  
62.  



6、快速排序

1. package cn.yqh.interview.sort;

2.  

3. /**

4. * @author 袁

5. * @create 2019/8/28-15:47

6. * https://blog.csdn.net/Yexiaofen/article/details/78018204

7. */

8. public class QuickSort {

9. public static void quickSort(int[] a, int low, int high) {

10. if (a == null || a.length == 0) {

11. return;

12. }

13. //1,找到递归算法的出口

14. if (low > high) {

15. return;

16. }

17. //2, 存

18. int i = low;

19. int j = high;

20. //3,key

21. int key = a[low];

22. //4，完成一趟排序

23. while (i

24. //4.1 ，从右往左找到第一个小于key的数

25. while (i key) {

26. j--;

27. }

28. // 4.2 从左往右找到第一个大于key的数

29. while (i

30. i++;

31. }

32. //4.3 交换

33. if (i

34. int p = a[i];

35. a[i] = a[j];

36. a[j] = p;

37. }

38. }

39. // 4.4，调整key的位置

40. swap(a, i, low);

41. //5, 对key左边的数快排

42. quickSort(a, low, i - 1);

43. //6, 对key右边的数快排

44. quickSort(a, i + 1, high);

45.  

46. }

47.  

48. private static void swap(int[] arr, int i, int i1) {

49. int tem = arr[i];

50. arr[i] = arr[i1];

51. arr[i1] = tem;

52. }

53.  

54. public static void main(String[] args) {

55. int[] arr = {22, 3, 0, 85, 7, 6, 25, 24, 56, 22};

56. quickSort(arr, 0, arr.length - 1);

57. for (int i : arr) {

58. System.out.print(i + " ");

59. }

60. }

61. }




7、堆排序

1. package cn.yqh.interview.sort;

2.  

3. /**

4. * @author 袁

5. * @create 2019/8/27-19:33

6. * https://www.jianshu.com/p/11655047ab58

7. */

8. public class HeapSort {

9.  
10.  

11. /**

12. * 堆排序

13. */

14. public static void heapSort(int[] arr) {

15. if (arr == null || arr.length == 0) {

16. return;

17. }

18. //对初始的数组构造大顶堆

19. //对最后一个非叶子结点开始到根节点为止进行排序,使数组构成大顶堆

20. for (int i = arr.length / 2 - 1; i >= 0; i--) {

21. //调用headADjust排序

22. headAdjust(arr, arr.length, i);

23. }

24. //排序完成,大顶堆已构成

25. //依次取出根元素与最后第一个元素,最后第二个元素,最后第三个元素...交换位置(根元素此时已经最大)

26. for (int i = arr.length - 1; i >= 1; i--) {

27. swap(arr, 0, i);

28. //交换之后,此时的根元素就一定是最大的元素了,所以进行堆调整,使根元素再次最大

29. headAdjust(arr, i, 0); //此时由于数组已经排出了一个最大元素放在最后,所以我们 只对剩下的length--进行排序,故长度为i

30. }

31. }

32.  
33.  

34. /**

35. * @param arr 需要排序的数组

36. * @param len 数组的长度

37. * @param i 需要排序的结点的索引

38. *

39. * 把要进行调整的结点i当做根节点,进行调整

40. */

41. private static void headAdjust(int[] arr, int len, int i) {

42. if (arr == null || arr.length == 0) {

43. return;

44. }

45. //把要进行调整的结点i当做根节点,则children

46. int root = i, index = 2 * root + 1; //index指向root直接结点中的最大值

47. while (index

48. if (index + 1

49. if (arr[index]

50. }

51. //到这里就找到了root的孩子的最大值的索引

52. if (arr[index] > arr[root]) {

53. swap(arr, index, root);

54. }

55. //交换完之后继续把被交换的子节点变为父节点继续调整,因为交换操作可能会破坏堆

56. //这里应该注意到,当操作树的倒数第二层,也就是非叶子结点的倒数第一层时,运行到这里while就结束了

57. //但是如果是倒数第三次或者更高时,那么下面的倒数第二层已经是被排序过了的

58. root = index;

59. index = 2 * root + 1;

60.  

61. //这里可以改成这样,若交换了则继续更新下面的节点,没交换则不用更新

62. /*if (arr[index] > arr[root]) {

63. swap(arr, root, index);

64. root = index;

65. index = 2 * root + 1;

66. } else {

67. break;

68. }*/

69. }

70. }

71.  
72.  

73. private static void swap(int[] arr, int i, int i1) {

74. int tem = arr[i];

75. arr[i] = arr[i1];

76. arr[i1] = tem;

77. }

78.  

79. public static void main(String[] args) {

80. int[] arr = {5, 3, 7, 2, 9, 4, 1};

81. heapSort(arr);

82. for (int i : arr) {

83. System.out.print(i + " ");

84. }

85. }

86. }

87.  
88.  
89.  



8、计数排序

1. package cn.yqh.interview.sort;

2.  

3. /**

4. * @author 袁

5. * @create 2019/8/27-19:33

6. * https://www.cnblogs.com/zer0Black/p/6169858.html

7. */

8.  

9. public class CountingSort {

10.  
11.  

12. /**

13. * 堆排序

14. */

15. public static void countingSort(int[] arr) {

16. if (arr == null || arr.length == 0) {

17. return;

18. }

19.  

20. int max = 0, min = 0;

21.  

22. //找出数组中最大最小值

23. for (int i = 0; i

24. max = Math.max(max, arr[i]);

25. min = Math.min(min, arr[i]);

26. }

27.  

28. int[] count = new int[max - min + 1];

29.  

30. //对数组中每个出现的元素计数

31. for (int i = 0; i

32. count[arr[i] - min]++;

33. }

34.  

35. //然后通过count数组得到数据的顺序

36. int index = 0;

37. for (int i = 0; i

38. while (count[i]-- > 0) { //这里count[i]先与0比较,后--

39. arr[index++] = i + min; //这里arr[index]=i+min之后,index再++

40. }

41. }

42.  

43. }

44.  
45.  

46. public static void main(String[] args) {

47. int[] arr = {5, 5, 3, 7, 2, 9, 4, 1};

48. countingSort(arr);

49. for (int i : arr) {

50. System.out.print(i + " ");

51. }

52.  

53. }

54. }

55.  
56.  
57.  



9、桶排序

1. package cn.yqh.interview.sort;

2.  

3. import java.util.ArrayList;

4. import java.util.Collections;

5. import java.util.List;

6.  

7. /**

8. * @author 袁

9. * @create 2019/8/27-19:33

10. * https://www.cnblogs.com/zer0Black/p/6169858.html

11. */

12.  

13. public class BucketSort {

14.  
15.  

16. /**

17. * 桶排序

18. */

19. public static List bucketSort(int[] arr) {

20. if (arr == null || arr.length == 0) {

21. return null;

22. }

23.  

24. int max = 0, min = 0;

25.  

26. //找出数组中最大最小值

27. for (int i = 0; i

28. max = Math.max(max, arr[i]);

29. min = Math.min(min, arr[i]);

30. }

31.  

32. // 先计算桶的数量

33. int bucketCount = (max - min) / arr.length + 1;

34. //创建桶数组

35. ArrayList> bucketArray = new ArrayList>(bucketCount);

36. for (int i = 0; i

37. bucketArray.add(new ArrayList());

38. }

39. //把数据放入桶中

40. for (int i = 0; i

41. bucketArray.get((arr[i] - min) / arr.length).add(arr[i]);

42. }

43. //对每个桶中的数据排序

44. for (int i = 0; i

45. Collections.sort(bucketArray.get(i));

46. }

47. return bucketArray;

48. }

49.  
50.  

51. public static void main(String[] args) {

52. int[] arr = {5, 5, 3, 7, 2, 9, 4, 1};

53. ArrayList list = (ArrayList) bucketSort(arr);

54. System.out.println(list.toString());

55. }

56. }

57.  
58.  
59.  



10、基数排序

1. package cn.yqh.interview.sort;

2.  

3. /**

4. * @author 袁

5. * @create 2019/8/27-19:33

6. * https://www.cnblogs.com/developerY/p/3172379.html

7. */

8.  

9. public class RadixSort {

10.  
11.  

12. /**

13. * 基数排序

14. */

15. public static void RadixSort(int[] arr, int maxDigit) {

16. if (arr == null || arr.length == 0) {

17. return;

18. }

19.  

20. int mod = 1; //n取1,10,100...

21. int k = 0; //当把桶中的数据取出到arr时使用

22. int len = arr.length;

23. int[][] bucket = new int[10][len]; //桶,用来装每个数据

24. int[] count = new int[10]; //用来记每个桶中有几个数据

25.  

26. while (mod

27. //把当前的数据按照顺序存到桶中

28. for (int i : arr) {

29. int digit = (i / mod) % 10;

30. bucket[digit][count[digit]] = i;

31. count[digit]++;

32. }

33.  

34. //一次排序完,则把数据从桶中放回数组中,

35. for (int i = 0; i

36. if (count[i] != 0) { //如果这个桶有数据,则取出

37. for (int j = 0; j

38. arr[k++] = bucket[i][j];

39. }

40. }

41. //每遍历完一个桶,把计数器归零

42. count[i] = 0;

43. }

44. mod *= 10; //继续比较下一位

45. k = 0;

46. }

47.  

48. }

49.  
50.  

51. public static void main(String[] args) {

52. int[] arr = {5555, 5, 3, 7, 2, 999, 4, 1};

53. RadixSort(arr, 10000);

54. for (int i : arr) {

55. System.out.print(i + " ");

56. }

57. }

58. }

59.  
60.  
61.  



以上便是这是个算法的java实现版本，再次鸣谢大佬的分享：https://www.cnblogs.com/onepixel/articles/7674659.ht