首页    技术博客    PHP教程    数据库技术    前端开发   HTML5    Nginx    php论坛
新用户注册 | 会员登录
加入会员，解锁专属内容
取消
热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

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

作者：羊咩咩0_581 | 来源：互联网 | 2023-09-15 16:25
原始链接：https:blog.csdn.netyuan_qharticledetails100139910十大经典排序算法的java实现以及原理讲解首先，这篇博客的来源是因为我在

原始链接：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




推荐阅读
author-avatar
羊咩咩0_581
这个家伙很懒，什么也没留下！
Tags | 热门标签
RankList | 热门文章
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有