【数据结构】排序 —— 归并排序（mergeSort）、计数排序、基数排序

Hi~！这里是奋斗的明志，很荣幸您能阅读我的文章，诚请评论指点，欢迎欢迎 ~~
🌱🌱个人主页：奋斗的明志
🌱🌱所属专栏：数据结构、LeetCode专栏

在这里插入图片描述

📚本系列文章为个人学习笔记，在这里撰写成文一为巩固知识，二为展示我的学习过程及理解。文笔、排版拙劣，望见谅。

在这里插入图片描述

一、归并排序

1.分治法

归并排序(Merge Sort)是用分治策略（分治法）实现对n个元素进行排序的一种高速的、稳定的排序算法。

在介绍归并排序之前，我们首先简单的认识一下分治法

分治法

基本思想：
将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且原问题相同。递归地解这些子问题，然后将各子问题的解合并得到原问题的解。
精髓：
分——将问题分解为规模更小的子问题。
治——将这些规模更小的子问题逐个击破。
合——将已解决的子问题合并，最终得到原问题的解。

2.归并排序基本思想

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：

在这里插入图片描述

3.动图演示

在这里插入图片描述

4.算法步骤

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
设定两个指针，最初位置分别为两个已经排序序列的起始位置；
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
重复步骤 3 直到某一指针达到序列尾；
将另一序列剩下的所有元素直接复制到合并序列尾。

5.递归思路

代码如下（示例）：

/*** 归并排序** @param array*/public static void mergeSort(int[] array) {//首先要进行分解mergeFunc(array, 0, array.length - 1);}private static void mergeFunc(int[] array, int left, int right) {//递归结束时的判断条件if (left >= right) {//需要考虑什么时候 left > rightreturn;}//找到中间点int mid = left + ((right - left) >> 1);//分界左边mergeFunc(array, left, mid);//分解右边mergeFunc(array, mid + 1, right);//进行合并//封装成一个方法merge(array, left, mid, right);}private static void merge(int[] array, int left, int mid, int right) {//定义四个变量进行理解int s1 = left;int e1 = mid;int s2 = mid + 1;int e2 = right;int k = 0;//申请一个额外的数组空间int[] tmpArray = new int[right - left + 1];//首先要保证两个原本的两段内容不为空，才能持续比较while (s1 <= e1 && s2 <= e2) {if (array[s1] >= array[s2]) {tmpArray[k++] = array[s2++];} else {tmpArray[k++] = array[s1++];}}//看哪个部分还有数据，拷贝到临时数组while (s1 <= e1) {tmpArray[k++] = array[s1++];}while (s2 <= e2) {tmpArray[k++] = array[s2++];}//再次拷贝到原数组for (int i = 0; i < k; i++) {array[i + left] = tmpArray[i];}}

6.非递归思路

    /*** 归并排序非递归** @param array*/public static void mergeSortNor(int[] array) {//首先定义每组排序的个数int gap = 1;while (gap < array.length) {//当gap = array.length时，说明这组数据有序for (int i = 0; i < array.length - 1; i = i + 2 * gap) {int left = i;int mid = left + gap - 1;//判断 mid  是否越界if (mid >= array.length){//重新赋值mid = array.length - 1;}int right = mid + gap;//判断 right  是否越界if (right >= array.length){//重新赋值right = array.length - 1;}//进行归并merge(array,left,mid,right);}//个数每次多2gap *= 2;}}

二、非基于比较的排序

1.计数排序

思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。

使用场景，如果给的数据集中到某一个范围的时候，建议使用计数排序，但是空间复杂度较高

【用空间来换取时间】

首先申请一个额外数组，从头到尾遍历原数组
该数字出现几次，进行统计，额外数组里面的值就++
最后遍历额外数组，进行排序

在这里插入图片描述

【注意点】

假设给 90 ~ 99 之间的数据呢？
利用哈希的思想

代码如下（示例）：

public static void countSort(int[] array){//首先要求该数组的最值//先假设int min = array[0];int max = array[0];for (int i = 0; i < array.length; i++) {if (min > array[i]){min = array[i];}if (max < array[i]){max = array[i];}}//创建一个计数数组int[] countArray = new int[max - min + 1];for (int i = 0; i < countArray.length; i++) {int index = array[i] - min;countArray[index]++;}//遍历计数数组//定义一个 k 记录array数组的下标int k = 0;for (int i = 0; i < countArray.length; i++) {while (countArray[i] != 0){array[k] = i + min;k++;countArray[i]--;}}}

public static void main(String[] args) {int[] array = {1,9,5,6,8,8,6,5,4,3,10};Sort.countSort(array);System.out.println(Arrays.toString(array));}

在这里插入图片描述

【总结】

计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
时间复杂度： O(MAX(N,范围))
空间复杂度： O(范围)
稳定性：稳定

2.基数排序

2.1 图解

【首先按每个数的个位数进行存放】

在这里插入图片描述

【再依次按照顺序出，如果一个框里面有多个数据，按照先进先出的原则】

在这里插入图片描述
【再按每个数的十位数进行存放】

【再依次按照顺序出，如果一个框里面有多个数据，按照先进先出的原则】

在这里插入图片描述

【再按每个数的百位数进行存放】
在这里插入图片描述

【最后出的时候是有序的】

在这里插入图片描述

2.2 动图演示

在这里插入图片描述

3.代码展示

/*** 基数排序*/
public class RadixSort implements IArraySort {@Overridepublic int[] sort(int[] sourceArray) throws Exception {// 对 arr 进行拷贝，不改变参数内容int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);int maxDigit = getMaxDigit(arr);return radixSort(arr, maxDigit);}/*** 获取最高位数*/private int getMaxDigit(int[] arr) {int maxValue = getMaxValue(arr);return getNumLenght(maxValue);}private int getMaxValue(int[] arr) {int maxValue = arr[0];for (int value : arr) {if (maxValue < value) {maxValue = value;}}return maxValue;}protected int getNumLenght(long num) {if (num == 0) {return 1;}int lenght = 0;for (long temp = num; temp != 0; temp /= 10) {lenght++;}return lenght;}private int[] radixSort(int[] arr, int maxDigit) {int mod = 10;int dev = 1;for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {// 考虑负数的情况，这里扩展一倍队列数，其中 [0-9]对应负数，[10-19]对应正数 (bucket + 10)int[][] counter = new int[mod * 2][0];for (int j = 0; j < arr.length; j++) {int bucket = ((arr[j] % mod) / dev) + mod;counter[bucket] = arrayAppend(counter[bucket], arr[j]);}int pos = 0;for (int[] bucket : counter) {for (int value : bucket) {arr[pos++] = value;}}}return arr;}/*** 自动扩容，并保存数据** @param arr* @param value*/private int[] arrayAppend(int[] arr, int value) {arr = Arrays.copyOf(arr, arr.length + 1);arr[arr.length - 1] = value;return arr;}
}