常用排序算法的总结以及编码（Java实现）

常用排序算法的总结以及编码（Java实现）

本篇主要是总结了常用算法的思路以及相应的编码实现，供复习的时候使用。如果需要深入进行学习，可以使用以下两个网站：

1. GeeksForGeeks网站用于学习相应的原理以及编码
2. Visualgo网站可以查看各种排序算法的动图，容易加深理解

冒泡排序

步骤

冒泡排序主要是通过依次比较相邻的两个元素，慢慢的将最大或者最小的元素“浮”出来。

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

编码实现

1. ---

2. /** 
   

   ---

3. * 最普通的冒泡排序算法 
   

   ---

4. * @param arr 
   

   ---

5. */ 
   

   ---

6. public static void bubbleSort1(int[] arr){ 
   

   ---

7. for (int i = 0; i < arr.length; i++) { 
   

   ---

8. // 在进行了第 i 次比较以后，最大的数据在 arr.length-i 处 
   

   ---

9. // 这个点相当于是个终点--在这个点以后的数据，都不需要在进行比较了，因为这个点以后的数据都已经排序过了 
   

   ---

10. for (int j = 1; j < arr.length - i; j++) { 
    

    ---

11. // 如果前面的数字比较大，将他移到后面去 
    

    ---

12. if(arr[j-1] > arr[j]){ 
    

    ---

13. swap(arr,j-1,j); 
    

    ---

14. } 
    

    ---

15. } 
    

    ---

16. } 
    

    ---

17. } 
    

    ---

18. ---

19. ---

20. /** 
    

    ---

21. * 加上了flag的冒泡排序 
    

    ---

22. * 对于一个大部分数据已经排序了数组，则不需要进行大量的比较以及交换。 
    

    ---

23. * 那么可以设置一个flag，如果这个flag为flase，即没有产生交换，那么就意味着排序已经完成了。 
    

    ---

24. * @param arr 
    

    ---

25. */ 
    

    ---

26. public static void bubbleSort2(int[] arr){ 
    

    ---

27. ---

28. // 初始化这个flag 
    

    ---

29. boolean flag = true; 
    

    ---

30. ---

31. // 需要进行比较的边界点，初始值为数组的长度 
    

    ---

32. int bound = arr.length; 
    

    ---

33. ---

34. while (flag){ 
    

    ---

35. flag = false; 
    

    ---

36. for (int i = 1; i < bound ; i++) { 
    

    ---

37. if (arr[i-1] > arr[i]){ 
    

    ---

38. swap(arr,i-1,i); 
    

    ---

39. flag = true; 
    

    ---

40. } 
    

    ---

41. } 
    

    ---

42. // 每次比较完，都减小一次边界 
    

    ---

43. bound--; 
    

    ---

44. } 
    

    ---

45. } 
    

    ---

46. ---

选择排序

步骤

选择排序的思路是：在没有排序的序列中，找到最小的或者最大的元素，放在已经排序的序列的尾部。

1. 从第一个元素开始，找到之后的序列中比此元素小的值，交换之；
2. 从第二个元素开始，找到之后的序列中比此元素小的值，交换之；
3. 重复直到所有的元素都有序。

编码实现

1. public static void selSort1(int[] arr){ 
   

   ---

2. // 从第i个开始，依次为最小索引 
   

   ---

3. for (int i = 0; i < arr.length; i++) { 
   

   ---

4. int minIndex = i; 
   

   ---

5. // j为未排序元素的第一个数字 
   

   ---

6. for (int j = minIndex + 1; j < arr.length; j++) { 
   

   ---

7. // 如果最小索引位置上的数字比第j个数字大，那么就交换这个两个数字 
   

   ---

8. if(arr[minIndex]>arr[j]){ 
   

   ---

9. swap(arr,j,minIndex); 
   

   ---

10. } 
    

    ---

11. } 
    

    ---

12. } 
    

    ---

13. } 
    

    ---

插入排序

步骤

先指定一个有序的序列，对于没有排序的数据，依次跟有序序列中的数据进行比较，如果比较小，则插入到相应的位置中去。

1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置后
6. 重复步骤2~5

编码实现

1. public static void insertSort(int[] arr){ 
   

   ---

2. // 表示已经排序的数组的下标，在这个下标之前的数据都已经进行了排序了 
   

   ---

3. int j; 
   

   ---

4. ---

5. // i 代表循环次数，从1开始，因为默认第一个元素是已经排序的 
   

   ---

6. for (int i = 1; i < arr.length; i++) { 
   

   ---

7. // 临时变量，获取第i个元素的值 
   

   ---

8. int tmp = arr[i]; 
   

   ---

9. ---

10. // 在已经排序的前j个数据中，先从第i个开始，依次跟前一个值进行比较 
    

    ---

11. // 如果tmp的值比较小，将大元素也就是 arr[j-1] 往后移 
    

    ---

12. // 额，这里j是不能=0的，=0都TM溢出了 j-1 都小于0了！！ 
    

    ---

13. for(j = i; j > 0 && tmp < arr[j - 1];j--){ 
    

    ---

14. // 将大的元素往后移 
    

    ---

15. arr[j] = arr[j - 1]; 
    

    ---

16. } 
    

    ---

17. // 如果没有比tmp小的了，或者j已经是0了，则在第j个位置插入该元素 
    

    ---

18. arr[j] = tmp; 
    

    ---

19. System.out.println(Arrays.toString(arr)); 
    

    ---

20. } 
    

    ---

21. } 
    

    ---

希尔排序

步骤

希尔排序可以说是插入排序的一个比较高效的实现方式。插入排序在对几户已经排序好的数据进行操作时，具有比较高的效率。因此希尔排序就是将一个数组中的元素分割成为几组，对每一组中的数据进行排序，然后再对整个数组进行排序。

编码实现

1. public static void shellSort(int[] arr){ 
   

   ---

2. int delta; 
   

   ---

3. // 定义分组的间隔，初始为数组长度的2的一半 
   

   ---

4. for(delta = arr.length/2; delta >= 1 ; delta/=2){ 
   

   ---

5. // 以下就是插入排序的过程 
   

   ---

6. for (int i = delta; i < arr.length ; i++) { 
   

   ---

7. int j = i; 
   

   ---

8. int tmp = arr[i]; 
   

   ---

9. // 这里与插入式排序不一样，是可以 = 0的，此时代表的是数组的第0个元素 
   

   ---

10. while (j - delta >= 0 && tmp < arr[j - delta]){ 
    

    ---

11. arr[j] = arr[j - delta]; 
    

    ---

12. j -= delta; 
    

    ---

13. } 
    

    ---

14. arr[j] = tmp; 
    

    ---

15. System.out.println(Arrays.toString(arr)); 
    

    ---

16. } 
    

    ---

17. } 
    

    ---

18. } 
    

    ---

堆排序

原理

堆排序是利用了最大堆、或者最小堆的性质进行排序的一种算法，这两种类型的堆分别具有以下的特点：父节点的值要大于（最小堆是小于）其左右子节点的值。由此，根节点的值为最大值（或者最小值）。交换根节点的值与数组末尾节点的值，再对剩余的元素进行重复的调整即可。

如果数组起始下标为0，那么节点i：

• 左节点为 2*i + 1
• 右节点为 2*i + 2
• 父节点为 (i-1) / 2

编码实现

1. /** 
   

   ---

2. * 堆排序 
   

   ---

3. * @param arr 
   

   ---

4. */ 
   

   ---

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

   ---

6. ---

7. // 初始化最大堆 
   

   ---

8. // 当 i = n/2 时，n为奇数时，左节点为n，偶数时，左节点为n 
   

   ---

9. // 当 i> n/2时，左右节点的下标均 > n 
   

   ---

10. // 因此 n/2 是最后一个有子节点的节点了 
    

    ---

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

    ---

12. maxHeapify(arr,i,arr.length); 
    

    ---

13. //minHeapify(arr,i,arr.length); 
    

    ---

14. } 
    

    ---

15. ---

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

    ---

17. // 交换根节点--最大或者最小节点，与最后一个节点的值 
    

    ---

18. swap(arr,0,i); 
    

    ---

19. // 对剩余的数据再次进行最大堆调整 
    

    ---

20. maxHeapify(arr,0,i); 
    

    ---

21. //minHeapify(arr,0,i); 
    

    ---

22. System.out.println(Arrays.toString(arr)); 
    

    ---

23. } 
    

    ---

24. } 
    

    ---

25. ---

26. ---

27. /** 
    

    ---

28. * 最大堆化 
    

    ---

29. * @param arr 需要最大堆化的数组 
    

    ---

30. * @param parent 
    

    ---

31. * @param length 
    

    ---

32. */ 
    

    ---

33. private static void maxHeapify(int[] arr,int parent,int length){ 
    

    ---

34. ---

35. int temp = arr[parent]; 
    

    ---

36. // 从左节点开始 
    

    ---

37. int child = 2 * parent + 1; 
    

    ---

38. ---

39. while (child < length){ 
    

    ---

40. // 如果有孩子节点存在，且有孩子节点的值比左孩子节点的值要大，那么替换为右孩子节点 
    

    ---

41. if (child + 1 < length && arr[child] < arr[child + 1]){ 
    

    ---

42. child ++; 
    

    ---

43. } 
    

    ---

44. ---

45. // 如果父节点的值最大，那么就已经不需要调整了 
    

    ---

46. if (temp >= arr[child]){ 
    

    ---

47. break; 
    

    ---

48. } 
    

    ---

49. ---

50. // 将孩子节点的值赋予父节点 
    

    ---

51. arr[parent] = arr[child]; 
    

    ---

52. ---

53. // 从孩子节点的左孩子节点继续循环 
    

    ---

54. parent = child; 
    

    ---

55. child = 2*child + 1; 
    

    ---

56. } 
    

    ---

57. ---

58. // 有两个作用 
    

    ---

59. // 1: 如果没有parent没有子节点，那么就把parent节点的值设置回来 
    

    ---

60. // 2: 如果parent有子节点，且符合交换的条件，那么现在这个parent就是之前的子节点，因为之前的子节点的值已经被替换到了父节点上，因此此操作是为了将父节点的值赋给之前的子节点 
    

    ---

61. arr[parent] = temp; 
    

    ---

62. ---

63. } 
    

    ---

归并排序

原理

现将一个数组进行拆分， 然后使得这个子数组有序，然后再合并数组。重复，直到这个数组有序。

编码实现

1. /** 
   

   ---

2. * 归并排序算法的实现 -- 使用递归 
   

   ---

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

   ---

4. * @param left 左边开始的节点 
   

   ---

5. * @param right 右边开始的节点 
   

   ---

6. * @param tmp 临时数组 
   

   ---

7. */ 
   

   ---

8. private static void sort(int[] arr, int left, int right, int[] tmp) { 
   

   ---

9. if(left < right){ 
   

   ---

10. // 定义中间节点 
    

    ---

11. int mid = (left + right) / 2; 
    

    ---

12. ---

13. // 对左边子序列进行归并排序 
    

    ---

14. sort(arr,left,mid,tmp); 
    

    ---

15. ---

16. // 对右边子序列进行归并排序 
    

    ---

17. sort(arr,mid + 1,right,tmp); 
    

    ---

18. ---

19. // 合并左右两个子序列 
    

    ---

20. merge(arr,left,mid,right,tmp); 
    

    ---

21. } 
    

    ---

22. } 
    

    ---

23. ---

24. /** 
    

    ---

25. * 对左右子序列进行合并操作 
    

    ---

26. * @param arr 
    

    ---

27. * @param left 
    

    ---

28. * @param mid 
    

    ---

29. * @param right 
    

    ---

30. * @param tmp 
    

    ---

31. */ 
    

    ---

32. private static void merge(int[] arr, int left, int mid, int right, int[] tmp) { 
    

    ---

33. ---

34. // 左子序列指针的初始化 
    

    ---

35. int i = left; 
    

    ---

36. // 右子序列指针的初始化 
    

    ---

37. int j = mid + 1; 
    

    ---

38. // 临时数组指针的初始化 
    

    ---

39. int t = 0; 
    

    ---

40. ---

41. // 比较左右子序列的值，将较小的值依次放入tmp临时数组中 
    

    ---

42. while (i <= mid && j <= right){ 
    

    ---

43. if(arr[i] <= arr[j]){ 
    

    ---

44. tmp[t++] = arr[i++]; 
    

    ---

45. }else { 
    

    ---

46. tmp[t++] = arr[j++]; 
    

    ---

47. } 
    

    ---

48. } 
    

    ---

49. ---

50. // 比较结束以后，会存在某一个子序列的值，还没有放进临时数组，因此需要将这些值放入临时数组 
    

    ---

51. ---

52. // 将左子序列剩余元素放入数组 
    

    ---

53. while (i <= mid){ 
    

    ---

54. tmp[t++] = arr[i++]; 
    

    ---

55. } 
    

    ---

56. ---

57. // 将右子序列剩余元素放入数组 
    

    ---

58. while (j <= right){ 
    

    ---

59. tmp[t++] = arr[j++]; 
    

    ---

60. } 
    

    ---

61. ---

62. // 将临时数组的指针置为0 
    

    ---

63. t = 0; 
    

    ---

64. ---

65. // 将临时数组中的数据复制到目标数组中 
    

    ---

66. while (left<=right){ 
    

    ---

67. arr[left++] = tmp[t++]; 
    

    ---

68. } 
    

    ---

69. System.out.println(Arrays.toString(arr)); 
    

    ---

70. } 
    

    ---

快速排序

原理

快速排序一样是使用了分治的思想，先选取一个枢纽值，将数组分成两个部分：在数组左边的数字都比枢纽值小，在数组右边的数字都比枢纽值大。重复，直到数组有序。

编码实现

1. /** 
   

   ---

2. * 快速排序算法，本代码中使用数组中的最后一个元素作为pivot 
   

   ---

3. * @param arr 
   

   ---

4. */ 
   

   ---

5. public static void quickSort(int[] arr){ 
   

   ---

6. sort(arr,0,arr.length-1); 
   

   ---

7. } 
   

   ---

8. ---

9. public static void sort(int[] arr, int left, int right){ 
   

   ---

10. if (left < right){ 
    

    ---

11. int pivot = partition(arr,left,right); 
    

    ---

12. sort(arr,left,pivot-1); 
    

    ---

13. sort(arr,pivot+1,right); 
    

    ---

14. } 
    

    ---

15. ---

16. } 
    

    ---

17. ---

18. /** 
    

    ---

19. * 此方法的目的有三个： 
    

    ---

20. * 1、 将比pivot值小的数字放在其前面 
    

    ---

21. * 2、 将比pivot值大的数字放在其后面 
    

    ---

22. * 3、 将pivot放在数组中正确的位置 
    

    ---

23. * 注意： 此处选择pivot的值为数组最后一个数字 
    

    ---

24. * @param arr 
    

    ---

25. * @param left 
    

    ---

26. * @param right 
    

    ---

27. * @return 
    

    ---

28. */ 
    

    ---

29. private static int partition(int[] arr, int left, int right) { 
    

    ---

30. ---

31. int pivot = arr[right]; 
    

    ---

32. // 存放较小数字的索引 
    

    ---

33. int i = left - 1; 
    

    ---

34. for (int j = left; j <= right - 1 ; j++) { 
    

    ---

35. // 如果数字小于pivot，交换i j两个位置的值 
    

    ---

36. if(arr[j] <= pivot){ 
    

    ---

37. i++; 
    

    ---

38. swap(arr,i,j); 
    

    ---

39. } 
    

    ---

40. } 
    

    ---

41. ---

42. // 第i个数字存放的数字永远小于pivot，因此将i+1的值设置为pivot 
    

    ---

43. // 这样就可以保证pivot将数组分为了两个部分，前半部分都小于pivot，后半部分都大于pivot 
    

    ---

44. swap(arr,i+1,right); 
    

    ---

45. return i+1; 
    

    ---

46. } 
    

    ---

源码地址： https://gitee.com/cjh95/SortAlgorithm