Java数据结构第二十一期：解构排序算法的艺术与科学(三)

专栏：Java数据结构秘籍

个人主页：手握风云

目录

一、常见排序算法的实现

1.1. 归并排序

二、排序算法复杂度及稳定性分析

---

一、常见排序算法的实现

1.1. 归并排序

        归并排序是建⽴在归并操作上的⼀种有效的排序算法,该算法是采⽤分治法的一个⾮常典型的应⽤。将已有序的⼦序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。如下图所示。

        类似于快速排序，利用数组下标的中间值mid进行分解，当left=right时，说明左树已经分解完毕，然后再去分解右树，然后再进行排序与合并。

    public void MergeSort(int[] array) {MergeSortChild(array, 0, array.length - 1);}private void MergeSortChild(int[] array, int left, int right) {if(left >= right){return;}int mid =(left+right)/2;MergeSortChild(array,left,mid);//递归左树MergeSortChild(array,mid+1,right);//递归右树//开始合并Merge(array,left,mid,right);}

        我们接下来说一下合并有序数组的思路。首先，我们需要额外定义一个临时数组用来储存合并后的数据。我们先定义三个指针，先让三个指针同时指向三个数组的第一个下标，比较nums[s1]与nums[s2]的值。如果nums[s1]>nums[s2]，将nums[s1]放入nums里面，同时s1、s向右移动；如果nums[s1]<nums[s2]，将nums[s2]放入nums里面，同时s2、s向右移动。在移动期间，要保证指针不会越界。

    private void Merge(int[] array, int left, int mid, int right) {int[] tmpArr = new int[right + left + 1];int k = 0;int s1 = left, e1 = mid, s2 = mid + 1, e2 = right;while (s1 <= e1 && s2 <= e2) {if (array[s1] <= array[s2]) {tmpArr[k++] = array[s1++];} else {tmpArr[k++] = array[s2++];}}while (s1 <= e1) {tmpArr[k++] = array[s1++];}while (s2 <= e2) {tmpArr[k++] = array[s2++];}}

        这样临时数组中储存的就是有序数据，但原数组还不是有序的，我们将临时数组拷贝到原始数组中。

        for (int i = 0; i < k; i++) {array[i + left] = tmpArr[i];}

        完整代码：

import java.util.Random;public class Sort {public void MergeSort(int[] array) {MergeSortChild(array, 0, array.length - 1);}private void MergeSortChild(int[] array, int left, int right) {if(left >= right) {return;}int mid = (left + right) / 2;MergeSortChild(array,left,mid);MergeSortChild(array,mid+1,right);//开始合并Merge(array,left,mid,right);}private void Merge(int[] array, int left, int mid, int right) {int[] tmpArr = new int[right - left + 1];int k = 0;int s1 = left, e1 = mid, s2 = mid + 1, e2 = right;while (s1 <= e1 && s2 <= e2) {if (array[s1] <= array[s2]) {tmpArr[k++] = array[s1++];} else {tmpArr[k++] = array[s2++];}}while (s1 <= e1) {tmpArr[k++] = array[s1++];}while (s2 <= e2) {tmpArr[k++] = array[s2++];}//临时数组当中存储的是有序的数据 -> 拷贝数据到原始数组当中for (int i = 0; i < k; i++) {array[i+left] = tmpArr[i];}}public void DsiOrder(int[] array) {Random ran = new Random();for (int i = 0; i < array.length; i++) {array[i] = ran.nextInt(1, 100);}}
}

import java.util.Arrays;public class Test {public static void main(String[] args) {Sort sort = new Sort();int[] array = new int[7];sort.DsiOrder(array);System.out.println("排序前："+ Arrays.toString(array));sort.MergeSort(array);System.out.println("排序后："+ Arrays.toString(array));}
}

        归并排序还可以进行非递归实现。要想进行非递归的实现，就要模拟出递归的过程。上面采用了分解与合并的过程，非递归的方式我们就可以省去分解的过程。我们对数组里的元素进行分组，每一个单独的元素都是有序的；然后缩小分组，对两个元素进行排序，变成每两个元素有序……直到数组里的每个元素都有序，也就是gap大于数组长度时。由于合并需要3个参数，根据上一种做法的分析，left=i，mid=left+gap-1，right=mid+gap。

    public void MergeSort(int[] array){int gap=1;while(gap < array.length){for (int i = 0; i < array.length; i=i+2*gap) {int left = i;int mid = left+gap-1;int right = mid+gap;Merge(array,left,mid,right);}gap = 2*gap;}}

        代码写到这里，我们需要考虑mid和right是否会越界的问题。

        完整代码实现：

import java.util.Random;public class Sort {public void DisOrder(int[] array) {Random in = new Random();for (int i = 0; i < array.length; i++) {array[i] = in.nextInt(1, 100);}}public void MergeSort(int[] array) {int gap = 1;while (gap < array.length) {for (int i = 0; i < array.length; i = i + 2 * gap) {int left = i;int mid = left + gap - 1;if (mid >= array.length) {mid = array.length - 1;}int right = mid + gap;if (right >= array.length) {right = array.length - 1;}Merge(array, left, mid, right);}gap = 2 * gap;}}private void Merge(int[] array, int left, int mid, int right) {int[] tmpArr = new int[right - left + 1];int k = 0;int s1 = left, e1 = mid, s2 = mid + 1, e2 = right;while (s1 <= e1 && s2 <= e2) {if (array[s1] <= array[s2]) {tmpArr[k++] = array[s1++];} else {tmpArr[k++] = array[s2++];}}while (s1 <= e1) {tmpArr[k++] = array[s1++];}while (s2 <= e2) {tmpArr[k++] = array[s2++];}//临时数组当中存储的是有序的数据 -> 拷贝数据到原始数组当中for (int i = 0; i < k; i++) {array[i + left] = tmpArr[i];}}
}

import java.util.Arrays;public class Test {public static void main(String[] args) {Sort sort = new Sort();int[] array = new int[6];sort.DisOrder(array);System.out.println("排序前："+ Arrays.toString(array));sort.MergeSort(array);System.out.println("排序后："+ Arrays.toString(array));}
}

        归并排序是稳定的。时间复杂度，每次递归都需要合并，；空间复杂度上，申请的临时数组与原数组长度一样，。

        归并排序而已用于海量数据的排序问题。比如在磁盘等外部存储进行的排序，内存只有1G，需要排序的数据有100G。我们把100G内存分成200份，每一份512M。每一个文件都经过内存的排序后，每个文件都单独有序了。进行2路归并，同时对 200 份有序⽂件做归并过程，最终结果就有序了。

二、排序算法复杂度及稳定性分析

排序方式	最好情况	最坏情况	空间复杂度	稳定性
冒泡排序			1	稳定
插入排序			1	稳定
选择排序			1	不稳定
希尔排序			1	不稳定
堆排序			1	不稳定
快速排序				不稳定
归并排序			n	稳定