阅读量:0
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 > right return; } //找到中间点 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); } //个数每次多2 gap *= 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 { @Override public 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; } } 总结
海量数据的排序问题
外部排序：排序过程需要在磁盘等外部存储进行的排序 前提：内存只有 1G，需要排序的数据有 100G
因为内存中因为无法把所有数据全部放下，所以需要外部排序，而归并排序是最常用的外部排序
- 先把文件切分成 200 份，每个 512 M
- 分别对 512 M 排序，因为内存已经可以放的下，所以任意排序方式都可以
- 进行 2路归并，同时对 200 份有序文件做归并过程，最终结果就有序了
