• 七大基于比较的排序算法基本原理及实现（Java版）

    目录

    常见的排序算法：

    一、直接插入排序

    1、 实现思路：

    2、 代码实现：

    3、 特性总结：

    二、希尔排序

    1、 实现思路：

    2、 代码实现：

    3、 特性总结：

    三、选择排序

    1、 实现思路：

    2、 代码实现：

    3、 特性总结：

    四、堆排序

    1、 实现思路：

    2、 代码实现：

    3、 特性总结：

    五、冒泡排序

    1、 实现思路：

    2、 代码实现：

    3、 特性总结：

    六、快速排序

    1、 基本思想：

    2、 代码实现：

    1、 Hoare版

    2、 挖坑法

    3、前后指针法

    4、快速排序优化

    5、快速排序非递归版

    3、 特性总结：

    七、归并排序

    1、 实现思路：

    2、 代码实现：

    1、递归版

    2、非递归版

    3、 特性总结：

    常见的排序算法：

    （以下排序方法都按从小到大升序排列为例）

    一、直接插入排序

    1、 实现思路：

    直接插入排序比较简单，但是它用途很广泛，其基本实现思路为：

    从给定数组的1下标开始，在该下标的左边找比它小的数据，找到后就把小的数据往前移，找完一个下标的，再找另一个下标的。

    举个栗子：

    给定一个序列array{1,5,3,4,7,2，3}，按照直接插入排序的思路把它变为一个升序序列。

    如果 j 下标的值大于 i 下标的值，那么就让 j 下标的值往后退一下，即array[j+1] = array[ j ]

    当 j 再往前走，发现 j 下标的值小于 i 下标的值，那么 j 停止移动，说明 j 之前已经是排好序的了，此时我们把，存放 i 的值的tmp赋给 j + 1下标，就完成了小的数字前移，大的数字后移：

     经过不停地循环，直到……

    此时， i 走到数组最后时又找到了一个 3 ，继续刚才的循环，看看这个 3 究竟会被放在哪里：

    我们发现，3 被放在了 3 的后面，在排序前，3 也位于 3 的后面，而此时数组的排序已经完成了，那么我们就称这个直接插入排序是一个稳定的排序算法。

    稳定性：如果在一个待排序的序列中，有多个相同的元素，在经过排序后，这些元素在序列中的位置相对不变，则称这个排序算法是稳定的；否则为不稳定的。

    2、 代码实现：

    1. public static void insertSort(int[] array){
    2.      for (int i = 1; i < array.length; i++) {
    3.         int j = i - 1;
    4.         int tmp = array[i];
    5.         for (; j >= 0 ; j--) {
    6.             if (array[j] > tmp){
    7.                 array[j+1] = array[j];
    8.             }else {
    9.                 break;
    10.             }
    11.         }
    12.         array[j+1] = tmp;
    13.     }
    14. }

    3、 特性总结：

    根据直接插入排序的时间复杂度，我们可以得出一个结论：

    数据越有序，直接插入排序的速度就越快。

    希尔排序应运而生。

    二、希尔排序

    1、 实现思路：

    希尔排序的基本思想：对一个数组进行分组，然后对分组后的每组数据进行直接插入排序，不断地重复这个分组、排序的工作，当最后分为一组排序后，这组数据就成为了有序数组。

    Q1：为什么要分组排序呢？

    A1：因为分组可以加快排序的速度。

    假设我们现在有10000个待排序的数据：

    Q2：如何分组？

    Q3：两种分组有什么区别呢？

    我们对两种分组中的每组数据都进行直接插入排序，得到以下结果：

    可以发现，通过希尔排序分组的数据，在排序之后，较大的数字都会放在后边，较小的数字都会放在前边，数组逐渐趋于有序。

    而一般情况分组的数据在经过排序后，不一定会达到上述效果。

    所以我们选择第二种分组方式。

    希尔排序又叫做缩小增量排序，这个增量指的就是每次所分的组的数量，当这个增量不断减小，数组就会不断趋于有序，当增量为1时，再进行一次排序，数组就会变得有序。

    那么问题来了~

    Q4：如何确定增量？

    A4：

            希尔排序的分析是一个复杂的问题，因为它的时间是所取“增量”序列的函数，这涉及一些数学上尚未解决的难题。因此，到目前为止尚未有人求得一种最好的增量序列。

    ——严蔚敏《数据结构(C语言版)》

    目前没有一个准确的确定增量的方法，你可以选择gap = n / 2，或者gap = n / 3，或者是其他的，只要让增量逐渐减小到1就行(gap表示增量，n表示数组长度)。

    希尔排序本身就是对直接插入排序的一种优化排序，我们只要把刚才的直接插入排序稍微改动一下，即可实现希尔排序：

    如果分组后的一组数据内不止2个元素，有多个元素呢？也是同理：

    先比较一次红色组的数据，再比较一次绿色组的数据，只要我们每次让 j  -= gap ，那么每次比较时，每组数据就不会互相影响：

    2、 代码实现：

    1. private static void shell(int[] array, int gap){
    2.         for (int i = gap; i < array.length; i++) {
    3.             int j = i - gap;
    4.             int tmp = array[i]; //把i的值先存起来
    5.             for (; j >= 0; j -= gap) {
    6.                 if (array[j] > tmp) {
    7.                     array[j + gap] = array[j];//此时需要交换的是j和j+gap下标的值
    8.                 } else {
    9.                     break;
    10.                 }
    11.             }
    12.             array[j + gap] = tmp;//把tmp的值赋给j+gap下标
    13.         }
    14.     }
    15.     public static void shellSort(int[] array){
    16.         int gap = array.length / 2; //自己确定gap的取值
    17.         while (gap > 1){
    18.             shell(array,gap); //每次分组后都进行一次直接插入排序
    19.             gap /= 2;
    20.         }
    21.         shell(array,gap);//最后一次排序
    22.     }

    3、 特性总结：

    由于增量gap没有一个标准的取值方法，所以希尔排序的时间复杂度是不固定的。

    三、选择排序

    1、 实现思路：

    选择排序又叫直接选择排序，它的实现思路非常简单：每次从待排序的数据中选择最小值(或最大值)放到序列的起始位置，直到全部待排序的数据排完。

    2、 代码实现：

    1. public class SelectSort {
    2.     public static void swap(int[] array,int i,int j){
    3.         int temp = array[i];
    4.         array[i] = array[j];
    5.         array[j] = temp;
    6.     }
    7.     public static void selectSort(int[] array){
    8.         for (int i = 0; i < array.length; i++) {
    9.             int minIndex = i;
    10.             for (int j = i + 1; j < array.length ; j++) {
    11.                 if(array[j] < array[minIndex]){
    12.                     minIndex = j;
    13.                 }
    14.             }
    15.             swap(array,i,minIndex);
    16.         }
    17.     }
    18. }

    上述代码中，每次遍历待排序的序列只找到了最小值的下标，如果每次遍历既可以找到最小值的下标，又可以找到最大值的下标，那么排序速度就会变快很多：

    1. public class SelectSort {
    2.     public static void swap(int[] array,int i,int j){
    3.         int temp = array[i];
    4.         array[i] = array[j];
    5.         array[j] = temp;
    6.     }
    7.  
    8.     public static void selectSort2(int[] array){
    9.         int left = 0;
    10.         int right = array.length - 1;
    11.         while (left < right){
    12.             int minIndex = left;//记录最小值的下标
    13.             int maxIndex = left;//记录最大值的下标
    14.             for (int i = left; i < right; i++) {
    15.                 if(array[i] < array[minIndex]){
    16.                     minIndex = i;
    17.                 }
    18.                 if(array[i] > array[maxIndex]){
    19.                     maxIndex = i;
    20.                 }
    21.             }
    22.             //最小值移动到序列前段
    23.             swap(array,left,minIndex);
    24.             //判断left处是否为最大值的下标
    25.             if(left == maxIndex){
    26.                 maxIndex = minIndex;
    27.             }
    28.             //最大值移动到序列末端
    29.             swap(array,right,maxIndex);
    30.             left++;
    31.             right--;
    32.         }
    33.     }
    34. }

    当 maxIndex 和 left 相同时，需要将 maxIndex 指向 minIndex (因为前一步的 swap()方法把 left 和 minIndex 的值进行了交换)：

    3、 特性总结：

    时间复杂度O(N^2)
    空间复杂度O(1)
    稳定性不稳定

    四、堆排序

    1、 实现思路：

    (1)创建一个大根堆(降序创建小根堆)；

    (2)将堆顶元素(最大值)和待排序元素中的最后一个元素进行交换；

    (3)交换完成后向下调整。然后重复第二步，直到排序完所有元素。

    2、 代码实现：

    1. public class HeapSort {
    2.     public static void swap(int[] array,int i,int j){
    3.         int temp = array[i];
    4.         array[i] = array[j];
    5.         array[j] = temp;
    6.     }
    7.     public void heapSort(int[] array){
    8.         createBigHeap(array);
    9.         int end = array.length - 1;
    10.         while (end > 0){
    11.             //交换堆顶元素和最后一个元素
    12.             swap(array,0,end);
    13.             //向下调整堆顶元素
    14.             shiftDown(array,0,end);
    15.             end--;
    16.         }
    17.     }
    18.     //创建大根堆
    19.     public void createBigHeap(int[] array){
    20.         for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {
    21.             shiftDown(array,parent,array.length);
    22.         }
    23.     }
    24.     public void shiftDown(int[] array,int parent,int len){
    25.         int child = parent * 2 + 1;//左孩子节点的下标
    26.         while (child < len){
    27.             //判断是否有右孩子，并且右孩子的值是否大于左孩子的值
    28.             if(child + 1 < len && array[child + 1] > array[child]){
    29.                 child += 1;
    30.             }
    31.             //判断较大的孩子节点的值和双亲节点的值的大小
    32.             if(array[child] > array[parent]){
    33.                 swap(array,child,parent);
    34.                 //交换完成后需要判断后续的子堆是否为大根堆
    35.                 parent = child;
    36.                 child = parent * 2 + 1;
    37.             }else {
    38.                 break;
    39.             }
    40.         }
    41.     }
    42. }

    3、 特性总结：

    时间复杂度        O(N*logN)
    空间复杂度        O(1)
    稳定性不稳定

    五、冒泡排序

    1、 实现思路：

    冒泡排序的思路很容易理解：每次从0下标开始，把当前元素和下一个元素进行比较，如果当前元素大于它下一个元素，则进行交换，直到把最大的元素换到待排序序列的最后一个位置。

    2、 代码实现：

    1. public class BubbleSort {
    2.     public static void swap(int[] array,int i,int j){
    3.         int temp = array[i];
    4.         array[i] = array[j];
    5.         array[j] = temp;
    6.     }
    7.     public void bubbleSort(int[] array){
    8.         int len = array.length;
    9.         for (int i = 0; i < len - 1; i++) {
    10.             //i确定排序的趟数,一共有len个元素，最多排len - 1趟
    11.  
    12.             boolean flg = false;
    13.  
    14.             for (int j = 0; j < len - 1 - i; j++) {
    15.                 //j确定每趟排序需要比较的元素个数
    16.                 //每排一趟就减少一个比较的元素
    17.                 if(array[j] > array[j+1]){
    18.                     swap(array,j,j+1);
    19.                     flg = true;
    20.                 }
    21.             }
    22.             //如果flg为false，说明这趟排序中一对元素都没有进行交换
    23.             //也说明当前序列已经是有序序列了，没必要再进行后续的比较了
    24.             if(!flg){
    25.                 break;
    26.             }
    27.         }
    28.     }
    29. }

    3、 特性总结：

    时间复杂度O(N^2)
    空间复杂度O(1)
    稳定性稳定

    六、快速排序

    1、 基本思想：

    (1)任取待排序元素中的某一个元素作为基准值；

    (2)将当前序列分割成两个子序列，左子序列的元素均小于基准值，右子序列的元素均大于基准值；

    (3)左右子序列重复上述两个步骤，直到待排序序列变为有序。

    2、 代码实现：

    将待排序序列按基准值划分为左右两个部分的常见方式有以下三种：

    1、 Hoare版

    主要思路：

    (1)找基准值下标：从数组末端(right)往前找比数组首元素小的值，再从数组前端(left)往后找比数组首元素大的值，然后交换两个数值，right继续往前找，left继续往后找，直到二者相遇，最后把相遇位置的值和起始位置元素的值进行交换，相遇位置就是基准值所在的下标。

    (2)根据基准值，递归基准值左边的子序列，再递归基准值右边的子序列。

    1. public class QuickSort {
    2.     public void swap(int[] array,int i, int j){
    3.         int temp = array[i];
    4.         array[i] = array[j];
    5.         array[j] = temp;
    6.     }
    7.  
    8.     //找基准值下标
    9.     public int getPivot(int[] array,int left, int right){
    10.         //记录left的起始位置
    11.         int temp = left;
    12.         //记录基准值
    13.         int key = array[left];
    14.         while (left < right){
    15.             //从右边找比基准值小的元素的下标
    16.             while (left < right && array[right] >= key){
    17.                 right--;
    18.             }
    19.             //从左边找比基准值大的元素的下标
    20.             while (left < right && array[left] <= key){
    21.                 left++;
    22.             }
    23.             //交换
    24.             swap(array,left,right);
    25.         }
    26.         //left和right相遇点即基准值下标
    27.         //交换起始位置元素和基准值
    28.         swap(array,left,temp);
    29.         return left;
    30.     }
    31.  
    32.     public void hoare(int[] array,int start, int end){
    33.         //递归终止条件
    34.         if(start >= end){
    35.             return;
    36.         }
    37.         //获取基准值下标
    38.         int pivot = getPivot(array,start,end);
    39.         //递归基准值左子序列
    40.         hoare(array,start,pivot-1);
    41.         //递归基准值右子序列
    42.         hoare(array,pivot+1,end);
    43.     }
    44.  
    45.     public void sort(int[] array){
    46.         hoare(array,0, array.length - 1);
    47.     }
    48. }

    2、 挖坑法

    主要思路：

    (1)找基准值下标：将当前序列的其实元素存起来，然后从序列末端(right)找比当前序列起始位置小的元素，找到后，把该元素移到序列前端(left)位置，再从序列前端往后找比起始位置大的元素，找到后，把该元素移到right位置。

    (2)重复循环上述步骤，直到left和right相遇，相遇点就是基准值下标，把起始位置的元素放到基准值下标处。

    (3)根据基准值，递归基准值左边的子序列，再递归基准值右边的子序列。

    1. public class QuickSort2 {
    2.     public void swap(int[] array,int i, int j){
    3.         int temp = array[i];
    4.         array[i] = array[j];
    5.         array[j] = temp;
    6.     }
    7.  
    8.     //找基准值下标
    9.     public int getPivot(int[] array,int left, int right){
    10.         //存放起始位置元素
    11.         int key = array[left];
    12.         while (left < right){
    13.             //从后往前找比key小的元素
    14.             while (left < right && array[right] >= key){
    15.                 right--;
    16.             }
    17.             //找到后放到left位置
    18.             array[left] = array[right];
    19.             //从前往后找比key大的元素
    20.             while (left < right && array[left] <= key){
    21.                 left++;
    22.             }
    23.             //找到后放到right位置
    24.             array[right] = array[left];
    25.         }
    26.         //left和right相遇位置即基准值下标
    27.         //把起始位置元素放到基准值下标处
    28.         array[left] = key;
    29.         return left;
    30.     }
    31.  
    32.     public void hole(int[] array, int start, int end){
    33.         //递归终止条件
    34.         if(start >= end){
    35.             return;
    36.         }
    37.         //获取基准值下标
    38.         int pivot = getPivot(array,start,end);
    39.         //递归基准值左子序列
    40.         hole(array,start,pivot-1);
    41.         //递归基准值右子序列
    42.         hole(array,pivot+1,end);
    43.     }
    44.  
    45.     public void sort(int[] array){
    46.         hole(array,0, array.length - 1);
    47.     }
    48. }

    3、前后指针法

    主要思路：

    (1)刚开始时，定义prev指针指向序列起始位置，定义cur指针指向prev的后面一个位置，cur和prev同时向后一步一步走，当cur遇到比起始位置元素大的值时，prev这次不往后走，cur往后走，当cur再次遇到比起始位置元素小的值时，交换prev和cur位置的元素。

    (2)当cur遍历完整个序列后，prev所在位置即基准值下标，交换序列起始位置的元素和基准值下标的元素。

    (3)根据基准值，递归基准值左边的子序列，再递归基准值右边的子序列。

    1. public class QuickSort3 {
    2.     public void swap(int[] array,int i, int j){
    3.         int temp = array[i];
    4.         array[i] = array[j];
    5.         array[j] = temp;
    6.     }
    7.     //找基准值下标
    8.     public int getPivot(int[] array,int left, int right){
    9.         //存放起始位置元素
    10.         int key = array[left];
    11.         int prev = left;
    12.         int cur = left + 1;
    13.         while (cur <= right){
    14.             //cur向后找比key大的值
    15.             if(array[cur] < key && array[++prev] != array[cur]){
    16.                 swap(array,prev,cur);
    17.             }
    18.             cur++;
    19.         }
    20.         //遍历完整个数组后，prev所在的位置就是基准值下标
    21.         //交换起始位置元素和基准值下标的元素
    22.         swap(array,prev,left);
    23.         return prev;
    24.     }
    25.     public void doublePointer(int[] array, int start, int end){
    26.         //递归终止条件
    27.         if(start >= end){
    28.             return;
    29.         }
    30.         //获取基准值下标
    31.         int pivot = getPivot(array,start,end);
    32.         //递归基准值左子序列
    33.         doublePointer(array,start,pivot-1);
    34.         //递归基准值右子序列
    35.         doublePointer(array,pivot+1,end);
    36.     }
    37.     public void sort(int[] array){
    38.         doublePointer(array,0, array.length - 1);
    39.     }
    40. }

    4、快速排序优化

    上述三种快速排序的方式，在针对一个有序序列进行排序时，时间复杂度会达到O(N^2)，并且，如果序列内的元素过多，递归的深度就会非常深，可能会导致栈溢出，因此，我们需要对上述三种方式进行优化。

    (1)三数取中法选基准值

    上述三种快速排序的方式，在进行第一次递归时，都是使用了0下标的值来作为初始的基准值，所以在针对有序序列进行排序时，时间复杂度会达到O(N^2)，所以，只要我们不使用0下标作为初始基准值即可减少时间复杂度。

    三数取中法是从待排序序列的首元素、最后一个元素和中间位置的元素，三个元素中选择一个数值第二大的元素和首元素进行交换，这样就可以在针对有序序列进行排序时，出现时间复杂度为O(N^2)的情况。

    1.  
    2.     //找第二大的数的下标
    3.     public int getMidNumIndex(int[] array,int start,int end){
    4.         //中间元素的下标
    5.         int mid = (start + end) / 2;
    6.         
    7.         int num1 = array[start];
    8.         int num2 = array[mid];
    9.         int num3 = array[end];
    10.  
    11.         if(num1 > num2){
    12.             if(num1 > num3){
    13.                 if(num2 > num3){
    14.                     return mid;
    15.                 }else {
    16.                     return end;
    17.                 }
    18.             }else {
    19.                 return start;
    20.             }
    21.         }else {
    22.             //num1 <= num2
    23.             if(num2 > num3){
    24.                 if(num1 > num3){
    25.                     return start;
    26.                 }else{
    27.                     return end;
    28.                 }
    29.             }else {
    30.                 return mid;
    31.             }
    32.         }
    33.     }

    找到第二大的元素后，再把它和首元素进行交换即可：

    1.     public void hole(int[] array, int start, int end){
    2.         //递归终止条件
    3.         if(start >= end){
    4.             return;
    5.         }
    6.  
    7.         //交换首元素和第二大的元素
    8.         int midNumIndex = getMidNumIndex(array,start,end);
    9.         swap(array,start,midNumIndex);
    10.  
    11.         //获取基准值下标
    12.         int pivot = getPivot(array,start,end);
    13.         //递归基准值左子序列
    14.         hole(array,start,pivot-1);
    15.         //递归基准值右子序列
    16.         hole(array,pivot+1,end);
    17.     }

    (2)递归到元素数量少的子区间时，可以考虑使用插入排序 

    假设在最好的情况，每次排序都可以通过基准值均分左右子序列，如果将每个子序列看做是一个节点，那么递归的所有结果可以看作一棵完全二叉树：

    元素数量越少，递归的次数越多，时间复杂度也就越高，但是此时的子序列已经是趋于有序了，因此我们可以在元素数量较少的时候，使用插入排序来对剩余的元素进行排序，这样就可以大大减少时间复杂度。

    1.     public void insertSort(int[] array, int start, int end){
    2.         for (int i = start + 1; i <= end; i++) {
    3.             int temp = array[i];
    4.             int j = i - 1;
    5.             for (; j >= start; j--) {
    6.                 if(array[j] > temp){
    7.                     array[j+1] = array[j];
    8.                 }else {
    9.                     break;
    10.                 }
    11.             }
    12.             array[j + 1] = temp;
    13.         }
    14.     }
    15.     public void hole(int[] array, int start, int end){
    16.         //递归终止条件
    17.         if(start >= end){
    18.             return;
    19.         }
    20.         if(end - start + 1 < 8){
    21.             //子序列的元素小于8个的时候使用直接插入排序
    22.             insertSort(array,start,end);
    23.             return;
    24.         }
    25.         //交换首元素和第二大的元素
    26.         int midNumIndex = getMidNumIndex(array,start,end);
    27.         swap(array,start,midNumIndex);
    28.  
    29.         //获取基准值下标
    30.         int pivot = getPivot(array,start,end);
    31.         //递归基准值左子序列
    32.         hole(array,start,pivot-1);
    33.         //递归基准值右子序列
    34.         hole(array,pivot+1,end);
    35.     }

    5、快速排序非递归版

    为了彻底解决栈溢出的问题，我们可以使用非递归版的快速排序：

    主要思路：

    (1)借助一个栈或者队列，把基准值的左、右子序列的起始位置和结束位置分别入队；

    (2)每次弹出两个元素作为新区间的起始位置和结束位置，再次找基准值，循环第一步操作；

    (3)当栈内为空时结束循环。

    1. public class QuickSort {
    2.     //找基准值下标
    3.     public int getPivot(int[] array,int left, int right){
    4.         //存放起始位置元素
    5.         int key = array[left];
    6.         while (left < right){
    7.             //从后往前找比key小的元素
    8.             while (left < right && array[right] >= key){
    9.                 right--;
    10.             }
    11.             //找到后放到left位置
    12.             array[left] = array[right];
    13.             //从前往后找比key大的元素
    14.             while (left < right && array[left] <= key){
    15.                 left++;
    16.             }
    17.             //找到后放到right位置
    18.             array[right] = array[left];
    19.         }
    20.         //left和right相遇位置即基准值下标
    21.         //把起始位置元素放到基准值下标处
    22.         array[left] = key;
    23.         return left;
    24.     }
    25.  
    26.     //非递归版快速排序
    27.     public void quickSort(int[] array,int start,int end){
    28.         Stack stack = new Stack<>();
    29.         int pivot = getPivot(array,start,end);
    30.         int left = start;
    31.         int right = end;
    32.  
    33.         if(left < pivot - 1){
    34.             stack.push(left);
    35.             stack.push(pivot - 1);
    36.         }
    37.         if(right > pivot + 1){
    38.             stack.push(pivot + 1);
    39.             stack.push(right);
    40.         }
    41.  
    42.         while (!stack.empty()){
    43.             right = stack.pop();
    44.             left = stack.pop();
    45.             pivot = getPivot(array,left,right);
    46.             if(left < pivot - 1){
    47.                 stack.push(left);
    48.                 stack.push(pivot - 1);
    49.             }
    50.             if(right > pivot + 1){
    51.                 stack.push(pivot + 1);
    52.                 stack.push(right);
    53.             }
    54.         }
    55.     }
    56. }

    3、 特性总结：

    时间复杂度(最好)时间复杂度(最坏)空间复杂度(最好)空间复杂度(最坏)稳定性
    O(N*logN)O(N^2)O(logN)O(N)不稳定

    七、归并排序

    1、 实现思路：

    (1)根据序列长度，将序列均分为左子序列和右子序列；

    (2)对第一步进行递归，直到子序列中只有一个元素时进行合并；

    (3)合并时，归并排序的问题就会被转换为对两个有序数组进行排序的简单问题。

    2、 代码实现：

    1、递归版

    1. public class MergeSort {
    2.     //分解
    3.     public void mergeSort(int[] array,int left,int right){
    4.         //终止条件
    5.         if(left >= right){
    6.             return;
    7.         }
    8.  
    9.         int mid = (left + right) / 2;
    10.  
    11.         //1.分解左边
    12.         mergeSort(array,left,mid);
    13.         //2.分解右边
    14.         mergeSort(array,mid + 1,right);
    15.         //3.合并
    16.         merge(array,left,right,mid);
    17.     }
    18.     
    19.     //合并
    20.     public void merge(int[] array,int start,int end,int midIndex){
    21.         //记录左子序列的起始位置
    22.         int ret = start;
    23.         //创建一个临时数组
    24.         int[] temp = new int[end - start + 1];
    25.         //临时数组的下标
    26.         int k = 0;
    27.         //右子序列的起始位置
    28.         int start2 = midIndex + 1;
    29.  
    30.         //两个子序列中都有元素的情况：
    31.         while (start <= midIndex && start2 <= end){
    32.             if(array[start] <= array[start2]){
    33.                 temp[k++] = array[start++];
    34.             }else {
    35.                 temp[k++] = array[start2++];
    36.             }
    37.         }
    38.         //只有一个子序列有元素的情况：
    39.         while (start <= midIndex){
    40.             temp[k++] = array[start++];
    41.         }
    42.         while (start2 <= end){
    43.             temp[k++] = array[start2++];
    44.         }
    45.  
    46.         //把temp数组的内容拷贝到array数组中
    47.         for (int i = 0; i < temp.length; i++) {
    48.             array[ret + i] = temp[i];
    49.         }
    50.     }
    51. }

    2、非递归版

    非递归版的归并排序省去了分解的过程，直接开始合并：

    1. public class MergeSort {
    2.     public void mergeSort(int[] array){
    3.         //gap表示每个子序列的元素个数
    4.         int gap = 1;
    5.  
    6.         while (gap <= array.length){
    7.             for (int i = 0; i < array.length; i += gap*2) {
    8.                 //左子序列起始位置
    9.                 int s1 = i;
    10.                 //左子序列结束位置
    11.                 int e1 = i + gap - 1;
    12.                 //右子序列结束位置
    13.                 int e2 = e1 + gap;
    14.                 //如果e2超过数组长度就越界了
    15.                 if(e2 < array.length){
    16.                     merge(array,s1,e2,e1);//合并
    17.                 }
    18.             }
    19.             gap *= 2;
    20.         }
    21.     }
    22.     //合并
    23.     public void merge(int[] array,int start,int end,int midIndex){
    24.         //记录左子序列的起始位置
    25.         int ret = start;
    26.         //创建一个临时数组
    27.         int[] temp = new int[end - start + 1];
    28.         //临时数组的下标
    29.         int k = 0;
    30.         //右子序列的起始位置
    31.         int start2 = midIndex + 1;
    32.  
    33.         //两个子序列中都有元素的情况：
    34.         while (start <= midIndex && start2 <= end){
    35.             if(array[start] <= array[start2]){
    36.                 temp[k++] = array[start++];
    37.             }else {
    38.                 temp[k++] = array[start2++];
    39.             }
    40.         }
    41.         //只有一个子序列有元素的情况：
    42.         while (start <= midIndex){
    43.             temp[k++] = array[start++];
    44.         }
    45.         while (start2 <= end){
    46.             temp[k++] = array[start2++];
    47.         }
    48.  
    49.         //把temp数组的内容拷贝到array数组中
    50.         for (int i = 0; i < temp.length; i++) {
    51.             array[ret + i] = temp[i];
    52.         }
    53.     }
    54. }

    3、 特性总结：

    时间复杂度O(N*logN)
    空间复杂度O(N)
    稳定性稳定

  • 相关阅读:
    Java面试题
    基于Java搬家预约系统设计实现(源码+lw+部署文档+讲解等)
    Python接口自动化之unittest单元测试
    是时候，升级你的 Windows 了「GitHub 热点速览」
    如何使用ebpf kprobe探测内核函数
    Springboot毕设项目个性化学习推荐网站ua750（java+VUE+Mybatis+Maven+Mysql）
    华科重要实验
    Unity3D学习笔记10——纹理数组
    BCS2024│云原生安全论坛启动
    Redis的各数据类型及其用法
  • 原文地址：https://blog.csdn.net/m0_67683346/article/details/125852057