文章目录
排序
概念
排序，就是使一串记录，按照其中的某个 或 某些关键字的大小，递增 或 递减 的 排列起来的操作。
平时的上下文中，如果提到排序，通常指的是 排升序（非降序）。
通常意义上的排序，都是指的原地排序（in place sort）
原地排序：就是指在排序过程中不申请多余的存储空间，只利用原来存储待排数据的存储空间进行比较和交换的数据排序。
稳定性（重要）
两个相等的数据，如果经过排序后，排序算法能保证其相对位置不发生变化，则我们称该算法是具备稳定性的排序算法。
应用 - 举例
1.、各大商城的价格从低到高等
2、中国大学排名
常见的排序算法（8 种）- 总览
直接插入排序
插入排序：非常简单！仅次于冒泡排序。
根据这个思维：第一个数据是有序的，也就是说：在我们遍历的时候，是从下标1 开始的。
具体的操作见下图：
模拟实现 - 插入排序
importjava.util.Arrays;publicclassDirectInsertionSort{/*
* 时间复杂度： O(N^2)
* 最好情况： O(N) 数组有序的情况
* 空间复杂度：O(1) 只有 一个 tmp 变量是常驻的
* 稳定性：稳定
* */publicstaticvoidinsertionSort(int[] array){for(int i =1;i < array.length;i++){int tmp = array[i];int j = i -1;for(; j >=0;j--){// 前移if(tmp < array[j]){
array[j +1]= array[j];}else{break;}}// 插入【无论是找到了合适插入的位置，还是不存在比 tmp更小的值，j自减到 -1.执行的代码都是一样的】
array[j+1]= tmp;}}publicstaticvoidmain(String[] args){int[] array ={23,45,56,68,8,9};insertionSort(array);System.out.println(Arrays.toString(array));}}
稳定性分析
结论
一个稳定的排序，可以实现为 不稳定的排序。
但是，一个本身就不稳定的排序是 无法变成 稳定的排序。
直接插入排序 是 有序的。
它的时间复杂度是 O(N^2)；最好情况:O(N【数组有序】
也就是说：对于直接插入排序，数据越有序越快！
由此，不难联想到：直接插入排序 有时候 会用于 优化 排序。
【假设：假设我们有一百万个数据需要排序，在排序的过程中，区间越来越小，数据越来越有序。直接插入排序的时间复杂度为 O(N),N 越来越小，那么，使用 直接插入排序是不是越来越快！也就是说：直接插入排序 有时候会 用于 排序优化】
直接插入排序经常使用在 数据量不多，且整体数据趋于有序的。
importjava.util.Random;publicclassDirectInsertionSort{/*
* 时间复杂度： O(N^2)
* 空间复杂度：O(1) 只有 一个 tmp 变量是常驻的
* 稳定性：稳定
* */publicstaticvoidinsertionSort(int[] array){for(int i =1;i < array.length;i++){int tmp = array[i];int j = i -1;for(; j >=0;j--){if(tmp < array[j]){
array[j +1]= array[j];}else{break;}}
array[j+1]= tmp;}}// 有序publicstaticvoidtest1(int capacity){int[] array =newint[capacity];for(int i =0; i < capacity; i++){
array[i]= i;}// 记录开始排序开始时间long start =System.currentTimeMillis();insertionSort(array);// 记录开始排序结束时间long end =System.currentTimeMillis();// 输出 整个排序过程的时间System.out.println(end - start);}// 无序publicstaticvoidtest2(int capacity){int[] array =newint[capacity];Random random =newRandom();for(int i =0; i < capacity; i++){
array[i]= random.nextInt(capacity);}// 记录开始排序开始时间long start =System.currentTimeMillis();insertionSort(array);// 记录开始排序结束时间long end =System.currentTimeMillis();// 输出 整个排序过程的时间System.out.println(end - start);}publicstaticvoidmain(String[] args){test1(10000);test2(10000);}}
希尔排序
思考
假设，现有 1 00 00 个 数据，如果对着组数据进行排序，使用插入排序。
时间复杂度为 O(N^2)【最坏情况：逆序的情况】
故 1 00 00 * 1 00 00 == 1 亿（量化）
它不是 1 万个数据嘛。那么，我们可以不可以这么去想：将这 一万个数据拆分成 100 组【每组100个数据】，对其中一组进行直接插入排序的时间复杂度为 100*100 ==1 00 00（量化），这样的分组还有99个，也就是将这一百组使用直接插入排序的时间复杂度为 1 00 00 * 1 00 = 1 百万（量化）。
有没有发现，分组过后，时间复杂度效率 提高很多，由1亿 变成了 1百万。
也就是说：如果采用分组的思想，我们会发现 时间复杂度会有一个很大的改变。
而这种分组的思想 就是 希尔排序。
原理
希尔排序又称缩小增量法。希尔排序法的基本思想是：先选定一个整数 n，把待排序文件中所有数据分成 n 组，所有距离为 数据量 / n 的 分在同一组。并且对每一组内的数据进行排序。然后，重复上述 分组 和 排序工作。当分组的组数为 1 是，所有数据 在进行 一个排序。
1、希尔排序 是对直接插入排序的优化。
2、当 group > 1 时都是预排序，目的是让数组更接近于有序。当 group == 1时，数组已经接近有序了，这样就会更快。对于整体而言，可以达到优化的效果。
那么，问题来了！我们怎去确定分多少组，而且越分越少。
【取自清华大学出版的一本书《数据结构》】
科学家的分组思维
现在这组数据，我们相当于只排序了一组数据，就走人了。数组整体还不是有序的。那么，我们该怎么解决这个问题？往下看！
模拟实现 - 希尔排序
importjava.util.Arrays;publicclassShellSort{/*
* 时间复杂度和增量有关系，所以无法得出准确的时间复杂度
* 但只需要记住：在一定的范围里，希尔排序的时间复杂度为 O(N^1.3 ~ N^1.5)
* 空间复杂度为 O(1)
* 稳定性：不稳定
* 判断稳定性的技巧：如果在比较的过程中 发生了 跳跃式交换。那么，就是不稳定的排序。
* */publicstaticvoidshell(int[] array,int group){for(int i = group; i < array.length; i +=1){int tmp = array[i];int j = i-group;for(; j >=0; j-=group){if(tmp < array[j]){
array[j+group]= array[j];}else{break;}}
array[j+group]= tmp;}}publicstaticvoidshellSort(int[] array){int group = array.length;// 预排序while(group >1){// 第一次分组委 数组的长度，即 头尾判断。// 其后，每次分组个数，缩小一倍。shell(array,group);
group /=2;}// 最后调整shell(array,1);}publicstaticvoidmain(String[] args){int[] array ={12,5,9,34,6,8,33,56,89,0,7,4,22,55,77};shellSort(array);System.out.println(Arrays.toString(array));}}
总结
其实 希尔排序就是一个直接插入排序。
选择排序
直接选择排序 - 原理
优化
定义 一个 变量， 用来记录 此时的 i 后面最小值的下标。等 j 遍历完了，最小值的下标也就拿到了。此时，再进行交换。
这样就不必让上面那样，遇到比 i下标元素 小的，就交换。
代码如下
importjava.util.Arrays;publicclassSelectSort{/*
* 稳定性： 不稳定 见附图
* 时间复杂度：O(N^2) 》》 外层循环 n -1，内层循环 n -1
* 空间复杂度：O(1)
* */publicstaticvoidselectSort(int[] array){for(int i =0; i < array.length-1; i++){int index = i;for(int j = i +1; j < array.length; j++){if(array[index]> array[j]){
index = j;}}int tmp = array[i];
array[i]= array[index];
array[index]= tmp;}}publicstaticvoidmain(String[] args){int[] array ={12,6,10,3,5};selectSort(array);System.out.println(Arrays.toString(array));}}
附图
双向选择排序 （了解）
每一次从无序区间选出最小 + 最大的元素，存放在无序区间的最前和最后，直到全部待排序的数据元素排完 。
代码如下
importjava.util.Arrays;publicclassSelectSortOP{publicstaticvoidselectSortOP(int[] array){int low =0;int high = array.length -1;// [low,high] 表示整个无序区间while(low < high){int min = low;int max = low;for(int i = low+1; i <= high; i++){if(array[i]< array[min]){
min = i;}if(array[i]> array[max]){
max = i;}}swap(array,min,low);if(max == low){
max = min;}swap(array,max,high);
low++;
high--;}}publicstaticvoidswap(int[] array,int x,int y){int tmp = array[x];
array[x]= array[y];
array[y]= tmp;}publicstaticvoidmain(String[] args){int[] array ={9,5,2,7,3,6,8};selectSortOP(array);System.out.println(Arrays.toString(array));}}
堆排序
基本原理也是选择排序，只是不在使用遍历的方式查找无序区间的最大的数，而是通过堆来选择无序区间的最大的数。
注意： 排升序要建大堆；排降序要建小堆.
这个我就不讲，因为我在 堆/优先级中讲的很清楚！
有兴趣的，可以点击 链接关键字 ，跳转到该文章，该内容在 文章目录最后面。
这里我们就直接上代码。
代码
importjava.util.Arrays;publicclassHeapSort{publicstaticvoidmain(String[] args){int[] array ={12,8,5,4,10,15};creationHeap(array);// 建堆的时间复杂度：O(N)System.out.println(Arrays.toString(array));heapSort(array);// 堆排序的时间复杂度：O(N * log2 N)// 空间复杂度：O(1)System.out.println(Arrays.toString(array));}// 创建一个大根堆publicstaticvoidcreationHeap(int[] array){for(int parent =(array.length-1-1)/2; parent >=0; parent--){shiftDown(array,parent,array.length);}}publicstaticvoidheapSort(int[] array){/*
* 时间复杂度：O(N * log2 N)
* 空间复杂度：O(1)
* 稳定性：不稳定
* */int end = array.length -1;while(end>0){int tmp = array[end];
array[end]= array[0];
array[0]= tmp;shiftDown(array,0,end);
end--;}}// 向下调整publicstaticvoidshiftDown(int[] array,int parent,int len){int child = parent *2+1;// 做孩纸while(child < len){// 获取左右子树最大值的下标if(child+1< len &&(array[child]< array[child+1])){
child++;}if(array[child]> array[parent]){int tmp = array[child];
array[child]= array[parent];
array[parent]= tmp;
parent = child;
child = parent *2+1;}else{break;}}}}
冒泡排序
代码如下 - 未优化
importjava.util.Arrays;/*
* 时间复杂度：O(N^2) 【无论是最好情况，还是最坏情况，时间复杂度都不变】
* 空间复杂度：O(1)
* 稳定性：稳定【未发生跳跃式交换】
* */publicclassBubbleSort{publicstaticvoidbubbleSort(int[] array){// 比较的趟数 = 数组的长度 - 1 【 0 ~ 3 一共 4趟】for(int i =0; i < array.length-1; i++){// 比较完一趟后，可以比较的元素个数减一。【因为靠后的数据已经有序】// 内循环中，之所以要减一个 1，是因为防止 下面的if语句 发生 数组越界异常for(int j =0;j< array.length-1-i;j++){if(array[j]> array[j+1]){int tmp = array[j];
array[j]= array[j+1];
array[j+1]= tmp;}}}}publicstaticvoidmain(String[] args){int[] array ={12,6,10,3,5};bubbleSort(array);System.out.println(Arrays.toString(array));}}
代码优化思维
代码如下 - 优化
importjava.util.Arrays;publicclassBubbleSort{/*
* 时间复杂度：O(N^2)
* 最好情况【数组有序】可以达到 O(N)
* 空间复杂度：O(1)
* 稳定性：稳定【未发生跳跃式交换】
* */publicstaticvoidbubbleSort(int[] array){for(int i =0; i < array.length-1; i++){boolean flag =true;for(int j =0;j< array.length-1-i;j++){if(array[j]> array[j+1]){int tmp = array[j];
array[j]= array[j+1];
array[j+1]= tmp;
flag =false;// 表示这一趟比较，数组是无序的}}// flag == trueif(flag){break;}}}publicstaticvoidmain(String[] args){// 前半段无序，后半段有序int[] array ={2,3,1,4,5};bubbleSort(array);System.out.println(Arrays.toString(array));}}
未优化 和 优化代码 运行速度比较
publicclassBubbleSort{// 优化publicstaticvoidbubbleSort2(int[] array){for(int i =0; i < array.length-1; i++){boolean flag =true;for(int j =0;j< array.length-1-i;j++){if(array[j]> array[j+1]){int tmp = array[j];
array[j]= array[j+1];
array[j+1]= tmp;
flag =false;}}// flag == trueif(flag){break;}}}// 未优化publicstaticvoidbubbleSort1(int[] array){for(int i =0; i < array.length-1; i++){for(int j =0;j< array.length-1-i;j++){if(array[j]> array[j+1]){int tmp = array[j];
array[j]= array[j+1];
array[j+1]= tmp;}}}}publicstaticvoidmain(String[] args){int[] array =newint[10000];for(int i =0; i < array.length; i++){
array[i]= i;}long start =System.currentTimeMillis();bubbleSort2(array);// 优化long end =System.currentTimeMillis();System.out.println(end - start);// 输出排序所需时间
start =System.currentTimeMillis();bubbleSort1(array);// 未优化
end =System.currentTimeMillis();System.out.println(end - start);//输出排序所需时间}}
快速排序 - 重点
原理
1、从待排序区间选择一个数，作为基准值（pivot）
2、Partition（分割）：遍历整个待排序区间，将比基准值小的（可以包含相等的）放到基准值的左边，将比基准值大的（可以包含相等的）放到基准值的右边。
3、采用分治思想，对左右两个小区间按照同样的方式处理，直到小区间的长度 == 1.代表已经有序，或者小区间的长度 == 0，代表没有数据。
总结
快速排序，其实说白了 和 二叉树 很像，先根，再左，后右。利用递归去实现！
程序框架
publicclassQuickSort{publicstaticvoidquickSort(int[] array){quick(array,0, array.length);}publicstaticvoidquick(int[] array,int start,int end){if(start >= end){return;}int pivot =partiton(array,start,end);quick(array,start,pivot-1);// 递归左边quick(array,pivot+1,end);// 递归右边}// 分割 - 找基准privatestaticintpartiton(int[] array,int start,int end){}}
完善 partition 部分
// 分割 - 找基准privatestaticintpartiton(int[] array,int start,int end){int tmp = array[start];while(start < end){while(start < end && array[end]>= tmp){
end--;}// 此时 end 下标 元素的值 是 小于 tmp的。
array[start]= array[end];while(start<end && array[start]<= tmp){
start++;}//此时 start 下标元素的值 是 大于 tmp的。
array[end]= array[start];}// start 和 end 相遇了，将 tmp 赋予 它们相遇下标指向的空间
array[start]= tmp;return start;}
代码细节部分
总程序 - 未优化
importjava.util.Arrays;publicclassQuickSort{/*
* 时间复杂度：O(N^2) 【数据有序或者逆序的情况】
* 最好情况【每次可以均匀的分割待排序序列】：O(N * log2 N)
* 空间复杂度：O(N)[单分支的一棵树]
* 最好：log2 N
* 稳定性：不稳定
* */publicstaticvoidquickSort(int[] array){quick(array,0, array.length-1);}publicstaticvoidquick(int[] array,int start,int end){if(start >= end){return;}int pivot =partiton(array,start,end);quick(array,start,pivot-1);// 递归左边quick(array,pivot+1,end);// 递归右边}// 分割 - 找基准privatestaticintpartiton(int[] array,int start,int end){int tmp = array[start];while(start < end){while(start < end && array[end]>= tmp){
end--;}// 此时 end 下标 元素的值 是 小于 tmp的。
array[start]= array[end];while(start<end && array[start]<= tmp){
start++;}
array[end]= array[start];}
array[start]= tmp;return start;}publicstaticvoidmain(String[] args){int[] array ={6,1,2,7,9,3,4,5,10,8};quickSort(array);System.out.println(Arrays.toString(array));}}
快速排序 的 时间 与 空间复杂度分析
堆排序 与 快排 的区别
细心的朋友会发现 堆排序 和 快排 的 时间复杂度在最好情况下 都是N* log2 N。
那么，两者又有什么区别？
堆排序，无论最好还是最坏情况，时间复杂度都是N* log2 N。空间复杂度 O(1)
那么，又为什么快排 比 堆排序 要快？
其实再细一点说 ：在两个排序的时间复杂度都为 N* log2 N时，其实连着前面还有 一个 k【K * N* log2 N 】，只不过快排前面的K要小一点。所以快排要快一点。
在对空间复杂度没有要求的情况： 快排
对空间复杂度有要求的情况，或者说对数据的序列也要要求： 堆排
细节拓展
if语句中 比较大小的代码中 等号是不能省略的
当 下面框选的代码 没有等号时，会造成死循环。
我就改了一下，末尾元素的值。
那么，问题来了：为什么没有等号就死循环了？
所以，在 写快排的时候，比较大小的代码，记住一定要加上等号！！！！！
目前版本的 快排代码 不支持 大量数据进行排序 - 会导致栈溢出。
这是因为 我们递归的太深了，1百万数据，4百万字节。
1TB等于1024GB;1GB等于1024MB;1MB等于1024KB;1KB等于1024Byte(字节);1Byte等于8bit(位);
有的朋友会说：这才多大啊？栈怎么会被挤爆？
这是因为在递归的时候，开辟的栈帧【函数的信息，参数等等等…都有】，所以，每次开辟的栈帧不止 4byte。故栈被挤爆了。所以，我们要优化快排的 代码。【优化：数据有序的情况】
基准值的选择 - 优化前的知识补充
1、选择边上（左或者右） 【重点，上面使用的就是这种方法】
2、随机选择（针对 有序数据）【了解】
3、几数取中（常见的就是三数取中）：array[left]，array[mid] ，array[right]中 大小为 中间值的为基准值【优化的关键】
快速排序（几数取中法 优化）
importjava.util.Arrays;publicclassQuickSort{/*
* 时间复杂度：O(N^2) 【数据有序或者逆序的情况】
* 最好情况【每次可以均匀的分割待排序序列】：O(N * log2 N)
* 空间复杂度：O(N)[单分支情况]
* 最好：log2 N
* 稳定性：不稳定
* */publicstaticvoidquickSort(int[] array){quick(array,0, array.length-1);}publicstaticvoidquick(int[] array,int start,int end){if(start >= end){return;}// 在找基准之前，先确定 start 和 end 的 中间值。[三数取中法]int midValIndex =findMidValIndex(array,start,end);//将它 与 start 交换。这样后面的程序，就不用改动了。swap(array,start,midValIndex);int pivot =partiton(array,start,end);quick(array,start,pivot-1);// 递归左边quick(array,pivot+1,end);// 递归右边}// 确定基准值下标privatestaticintfindMidValIndex(int[] array,int start,int end){// 确定 start 和 end 的中间下标int mid = start +((end - start)>>>1);// == （start + end）/ 2// 确定 mid、start、end 三个下标，谁指向的元素是三个元素中的中间值if(array[end]> array[start]){if(array[start]> array[mid]){return start;}elseif(array[mid]> array[end]){return end;}else{return mid;}}else{// array[start] >= array[end]if(array[end]> array[mid]){return end;}elseif(array[mid]> array[start]){return start;}else{return mid;}}}// 交换两个下标元素privatestaticvoidswap(int[] array,int x,int y){int tmp = array[x];
array[x]= array[y];
array[y]= tmp;}// 分割 - 找基准privatestaticintpartiton(int[] array,int start,int end){int tmp = array[start];while(start < end){while(start < end && array[end]>= tmp){
end--;}// 此时 end 下标 元素的值 是 小于 tmp的。
array[start]= array[end];while(start<end && array[start]<= tmp){
start++;}
array[end]= array[start];}
array[start]= tmp;return start;}// 有序publicstaticvoidtest1(int capacity){int[] array =newint[capacity];for(int i =0; i < capacity; i++){
array[i]= i;}long start =System.currentTimeMillis();quickSort(array);long end =System.currentTimeMillis();System.out.println(end - start);}publicstaticvoidmain(String[] args){test1(100_0000);int[] array ={6,1,2,7,9,3,4,5,10,6};quickSort(array);System.out.println(Arrays.toString(array));}}
优化总结
1、选择基准值很重要，通常使用几数取中法
2、partition 过程中把和基准值相等的数也选择出来
3、待排序区间小于一个阈(yù)值【临界值】随着不断的划分基准，数组逐渐趋于有序，而区间随着递归也在减小。所以，利用 直接插入排序的特性【越有序越快】，来进一步优化 快排。
拓展 快速排序 - 非递归实现
非递归实现快速排序的思维
代码如下
importjava.util.Arrays;importjava.util.Stack;publicclassQuickSortNonRecursion{publicstaticvoidquickSort(int[] array){Stack<Integer> stack =newStack<>();int left =0;int right = array.length-1;int pivot =partiton(array,left,right);if(pivot > left+1){
stack.push(left);
stack.push(pivot-1);}if(pivot < right -1){
stack.push(pivot+1);
stack.push(right);}while(!stack.isEmpty()){
right = stack.pop();
left = stack.pop();
pivot =partiton(array,left,right);if(pivot>left+1){
stack.push(left);
stack.push(pivot-1);}if(pivot<right-1){
stack.push(pivot+1);
stack.push(right);}}}publicstaticintpartiton(int[] array,int start,int end){int tmp = array[start];while(start<end){while(start<end && array[end]>=tmp){
end--;}
array[start]= array[end];while(start<end && array[start]<= tmp){
start++;}
array[end]= array[start];}
array[start]= tmp;return start;}publicstaticvoidmain(String[] args){int[] array ={12,5,8,1,10,15};quickSort(array);System.out.println(Arrays.toString(array));}}
归并排序 - 重点
知识铺垫 ： 二路合并
将两个有序表合并成一个有序表，称为二路归并。【简单说就是 将两个有序数组合并为一个有序数组，称为二路合并】
二路合并的代码如下
importjava.util.Arrays;publicclassMergeSort{/*
* array1 已有序
* array2 已有序
* */publicstaticint[]mergeArrays(int[] array1,int[] array2){if(array1 ==null|| array2 ==null){return array1 ==null? array2: array1;}int[] arr =newint[array1.length + array2.length];int i =0;// arr 的 遍历变量int s1 =0;//array1 的 遍历变量int s2 =0;//array2 的 遍历变量while(s1 < array1.length && s2 < array2.length){if(array1[s1]> array2[s2]){
arr[i++]= array2[s2++];// s2++;// i++;}else{
arr[i++]= array1[s1++];// s1++;// i++;}}// 循环结束，有一个数组的元素已经全部存入// 接下来就是将另一个数组的元素放入 arr 中while(s1 < array1.length){
arr[i++]= array1[s1++];// i++;// s1++;}while(s2 < array2.length){
arr[i++]= array2[s2++];// i++;// s2++;}return arr;}publicstaticvoidmain(String[] args){int[] array1 ={1,6,7,10};int[] array2 ={2,3,4,9};int[] mergeArray =mergeArrays(array1,array2);System.out.println(Arrays.toString(mergeArray));}}
归并排序 - 原理
归并排序（MERGE - SORT）是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
难点1 - 如何将一个数组拆分成一个个单独数组【每个数组里只包含一个元素】。
难点2 - 合并
归并排序的程序框架
publicclassMergeSort{// 归并排序的调用“接口”publicstaticint[]mergeSort(int[] array){if(array ==null){return array;}mergeSortFunc(array,0,array.length-1);return array;}// 归并排序实现privatestaticvoidmergeSortFunc(int[] array,int low,int high){if(low >= high){return;}// 递归分解// int mid = (high + low) >>> 1int mid = low +((high - low)>>>1);mergeSortFunc(array,low,mid);// 左边mergeSortFunc(array,mid+1,high);// 右边// 合并merge(array,low,mid,high);}privatestaticvoidmerge(int[] array,int low,int mid,int high){}}
合并程序的完善
其实这个并不难，跟我前面做的知识铺垫的思路是一样的。
需要注意的是：
1、我们的参数中 只有一个数组
2、数组 arr ，只是一个临时数组，用来存储 合并之后的结果。
3、在将 arr 数组 存储的结果，转移到 原本数组的时候，注意赋值的位置！
privatestaticvoidmerge(int[] array,int low,int mid,int high){// 获取 区间之内的元素个数，加一 是因为 零下标元素也算一个元素。int[] arr =newint[high - low +1];// 左边 区间 【你可以理解为 有序数组 array1的起始与结束下标位置】int start1 = low;int end1 = mid;// 右边 区间【你可以理解为 有序数组 array2的起始与结束下标位置】int start2 = mid+1;int end2 = high;int i =0;while(start1 <= end1 && start2 <= end2){if(array[start1]> array[start2]){
arr[i++]= array[start2++];}else{
arr[i++]= array[start1++];}}while(start1 <= end1){
arr[i++]= array[start1++];}while(start2 <= end2){
arr[i++]= array[start2++];}// 将 arr 存储的 合并数据，转换到原本数组上。// 注意 array 数组中括号的下标的位置。for(int j =0; j < arr.length; j++){
array[low++]= arr[j];}}
附图
归并排序 - 总程序
importjava.util.Arrays;publicclassMergeSort{/*
* 时间复杂度：N * log2 N
* 空间复杂丢：O(N)
* 稳定性：稳定
* */publicstaticint[]mergeSort(int[] array){if(array ==null){return array;}mergeSortFunc(array,0,array.length-1);return array;}privatestaticvoidmergeSortFunc(int[] array,int low,int high){if(low >= high){return;}// int mid = (high + low) >>> 1int mid = low +((high - low)>>>1);mergeSortFunc(array,low,mid);// 左边mergeSortFunc(array,mid+1,high);// 右边merge(array,low,mid,high);}privatestaticvoidmerge(int[] array,int low,int mid,int high){int[] arr =newint[high - low +1];int start1 = low;int end1 = mid;int start2 = mid+1;int end2 = high;int i =0;while(start1 <= end1 && start2 <= end2){if(array[start1]> array[start2]){
arr[i++]= array[start2++];}else{
arr[i++]= array[start1++];}}while(start1 <= end1){
arr[i++]= array[start1++];}while(start2 <= end2){
arr[i++]= array[start2++];}for(int j =0; j < arr.length; j++){
array[low++]= arr[j];}}publicstaticvoidmain(String[] args){int[] array ={1,6,7,10,2,3,4,9};mergeSort(array);System.out.println(Arrays.toString(array));}}
归并排序 - 时间与空间复杂度分析、稳定性
归并排序 - 非递归实现
代码如下
importjava.util.Arrays;publicclassMergeSortNonRecursion{publicstaticvoidmergeSort(int[] array){//归并排序非递归实现int groupNum =1;// 每组的数据个数while(groupNum < array.length){// 无论数组含有几个元素， 数组每次都需要从下标 0位置，开始遍历。for(int i =0;i<array.length;i+= groupNum *2){int low = i;int mid = low + groupNum -1;// 防止越界【每组的元素个数，超过了数组的长度】if(mid >= array.length){
mid = array.length-1;}int high = mid + groupNum;// 防止越界【超过了数组的长度】if(high >= array.length){
high = array.length-1;}merge(array,low,mid,high);}
groupNum *=2;//每组的元素个数扩大到原先的两倍。}}publicstaticvoidmerge(int[] array,int low,int mid,int high){// high 与 mid 相遇，说明 此时数组分组只有一组，也就说没有另一组的数组与其合并// 即数组已经有序了，程序不用再往下走。if(high == mid){return;}int[] arr =newint[high -low +1];int start1 = low;int end1 = mid;int start2 = mid+1;int end2 = high;int i =0;while(start1 <= end1 && start2 <= end2){if(array[start1]>array[start2]){
arr[i++]= array[start2++];}else{
arr[i++]= array[start1++];}}while(start1 <= end1){
arr[i++]= array[start1++];}while(start2 <= end2){
arr[i++]= array[start2++];}for(int j =0; j < arr.length; j++){
array[low++]= arr[j];}}publicstaticvoidmain(String[] args){int[] array ={12,5,8,7,3,4,1,10};mergeSort(array);System.out.println(Arrays.toString(array));}}
海量数据的排序问题
外部排序：排序过程需要在磁盘等外部存储进行的排序
【内部排序：排序过程需要在 内存上进行排序】
前提：内存只有 1G，需要排序的数据有 100G
因为内存中无法把所有数据全部放下，所以需要外部排序，而归并排序是最常用的外部排序。
1、先把文件切分成 200 份，每个512M
2、分别对 512M 的数据量 进行排序，因为 内存已经被分割了，512M < 1G 内存放得下。所以任何排序方式都可以，
3、进行 200 路归并，同时对 200 份有序文件做归并过程，最终结果就有序了
小总结
目前，我们讲了八种排序：直接插入排序、希尔排序、直接选择排序，双向选择排序、冒泡排序，堆排序、快速排序，归并排序。
其中稳定的排序：插入排序，冒泡排序，归并排序，一共三种。另外，堆排序、归并排序、快速排序的时间复杂度都是 N * log2 N。
如果，你想速度快，就用快排。
如果，你想稳定，就用归并。
如果，你想空间复杂度低，就用堆排。
排序总结
排序方法最好（时间复杂度）平均（时间复杂度）最坏（时间复杂度）空间复杂度稳定性冒泡排序O(N)O(N^2)O(N^2)O(1)稳定插入排序O(N)O(N^2)O(N^2)O(1)稳定选择排序O(N^2)O(N^2)O(N^2)O(1)不稳定希尔排序O(N)O(N^1.3)O(N^2)O(1)不稳定堆排序O(N * log2 N)O(N * log2 N)O(N * log2 N)O(1)不稳定快速排序O(N * log2 N)O(N * log2 N)O(N ^ 2)O(N)不稳定归并排序O(N * log2 N)O(N * log2 N)O(N * log2 N)O(N)稳定
不常见的排序 - 不基于比较的排序（了解）
基数排序
它的思路：假设待排序的数据类型是 整形/十进制数，每个数据 分别按照 个，百，千，万的大小，放入拿出对应编号空间，其最终的结果就是有序的。
放入拿出的次数 取决于 这组数据中 最大值的位数。
代码如下
importjava.util.Arrays;publicclassRadixSort{// 基数排序功能 实际功能实现方法privatestaticvoidradixSortFunc(int[] array,int maxDigit){int mode =10;// 十进制int divide =1;// 将 数值上的每个数“分割”，方便获取数据的一个位上的值// 每个数据从个位到最大值的最高位，按照其位上的大小 放出 拿出for(int i =0; i < maxDigit; i++,mode *=10,divide *=10){// 考虑 负数的 情况，0~9 对应负数，10 ~ 19 对应正数// 行 对应的是编号， 列 对应的存储的数据int[][] counter =newint[mode*2][0];for(int j =0; j < array.length; j++){int number =((array[j]% mode)/divide)+ mode;/*获取 数据对应 空间的编号 */
counter[number]=arrayAppend(counter[number],array[j]);}int pos =0;for(int[] number:counter){for(int val:number){
array[pos++]= val;}}}}// 添加 元素privatestaticint[]arrayAppend(int[] arr,int value){
arr =Arrays.copyOf(arr,arr.length+1);
arr[arr.length-1]= value;return arr;}// 基数排序 功能调用方法“窗口”publicstaticvoidradixSort(int[] array){int maxNumLength =getNumLength(array);radixSortFunc(array,maxNumLength);}// 获取最大值的位数 - 功能“窗口”privatestaticintgetNumLength(int[] array){int maxVal =getMaxValue(array);returngetMaxDigit(maxVal);}//获取最大值privatestaticintgetMaxValue(int[] array){int maxValue= array[0];for(int value: array){if(value > maxValue){
maxValue = value;}}return maxValue;}// 获取最大值的位数 - 执行privatestaticintgetMaxDigit(int num){if(num ==0){return0;}int len =0;while(num >0){
len++;
num /=10;}return len;}// 程序入口publicstaticvoidmain(String[] args){int[] array ={124,366,170,52,200,78,468};radixSort(array);System.out.println(Arrays.toString(array));}}
捅排序
计数排序
在使用 计数排序时，需注意以下几点：
1、确定基数排序的大小
2、这个计数排序 适用的范围【假设数据中最小值 10000，最大 12000，那么，我们的计数数组容量只需要2001（0 下标也算入） 就够了。不需要创建 12000容量，避免空间浪费】
计数数组 计数也简单，用元素值减去 10000（最小值） 就行了
3、必须找到数据中的最大值 和 最小值，锁定计数数组的长度：max - min + 1
4、 拿出数据的时候，记得将减去的 最小值 加上，再进行对原始数组的覆写。
代码如下
importjava.util.Arrays;/*
* 时间复杂度：O(N)
* 空间复杂度: O(M) : M 表示 当前数据的范围
* 【空间 换 时间】
* 稳定性： 当前代码是不稳定，本质是稳定的。
* 在借助一个 数组来存储 每个元素排序后，最后出现的位置，
* 拿出来的时候，就能确定位置。致使该排序 稳定。 - 见附图
* */publicclassCountingSort{publicstaticvoidcountingSort(int[] array){int maxVal = array[0];int minVal = array[0];for(int i =0; i < array.length; i++){if(array[i]> maxVal){
maxVal = array[i];}if(array[i]< minVal){
minVal =array[i];}}// 当循环结束，获得了 数据的最大值 和 最小值// 可以确定计数数组的容量int[] count =newint[maxVal -minVal +1];for(int i =0; i < array.length; i++){// 提高空间利用率
count[ array[i]- minVal ]++;}// 此时，计数数组 已经把array数组当中，每个元素的出现次数统计好了// 接下来，只需要遍历计数数组，把 数据 覆写 到 array当中。int indexArray =0;// 用于遍历 array数组，标记 覆写的位置。for(int i =0; i < count.length; i++){while(count[i]>0){// 这里一定要加上减去minVal，因为 下标 i 不一定 在 array 数组中出现过。
array[indexArray++]= i + minVal;// 拿出来的时候，记得将减去的值加上// indexArray++;
count[i]--;}}}publicstaticvoidmain(String[] args){int[] array ={5,0,2,3,4,5,2};countingSort(array);System.out.println(Arrays.toString(array));}}
附图 - 是目前的计数排序稳定
本文结束
本文转载自: https://blog.csdn.net/DarkAndGrey/article/details/122792097
版权归原作者 Dark And Grey 所有， 如有侵权，请联系我们删除。
版权归原作者 Dark And Grey 所有， 如有侵权，请联系我们删除。