数据结构-8.Java. 七大排序算法(下篇)

本篇博客给大家带来的是排序的知识点, 由于时间有限, 分两天来写, 下篇主要实现最后一种排序算法: 归并排序。同时把中篇剩下的快排非递归实现补上.
文章专栏: Java-数据结构
若有问题 评论区见
欢迎大家点赞 评论 收藏 分享
如果你不知道分享给谁,那就分享给薯条.
你们的支持是我不断创作的动力 .

1. 快速排序的非递归实现

拿到第一个基准值pivot之后, 如何进行左右子序列的快速排序呢?
可以利用栈保存左区间 和 右区间.

1.1 具体实现

1. 利用上篇文章的 partition算法拿到第一个基准值,用栈存储左区间 和 右区间,
2. 重复第一步,直到栈为空.

1.1.1 区间入栈细节

如下分析图:

1.2 代码如下:

//挖坑法,求基准值.
private static int partition2(int[] array,int left,int right) {int key = array[left];while(left < right) {while(left < right && array[right] >= key) {right--;}//从右边开始第一个比key小的元素覆盖[left]array[left] = array[right];while(left < right && array[left] <= key) {left++;}//从左边开始第一个比key大的元素覆盖空位.array[right] = array[left];}//key填补最终的空位,此时left=rightarray[left] = key;return left;}
//快速排序法的非递归实现.public static void quickSortNor(int[] array) {Stack<Integer> stack = new Stack<>();int left = 0;int right = array.length-1;//拿到第一个基准int pivot = partition2(array,left,right);//左序列区间端点入栈.if(pivot-1 > left) {stack.push(left);stack.push(pivot-1);}//右序列区间端点入栈.if (pivot+1 < right) {stack.push(pivot+1);stack.push(right);}while(!stack.isEmpty()) {right = stack.pop();left = stack.pop();pivot = partition2(array,left,right);if(pivot-1 > left) {stack.push(left);stack.push(pivot-1);}if (pivot+1 < right) {stack.push(pivot+1);stack.push(right);}}}

1.3 快速排序的特性总结:

1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2. 时间复杂度：O(N*logN)

3. 空间复杂度：O(logN)
4. 稳定性：不稳定

2. 归并排序

2.1 归并排序的基本思想

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

2.2 具体步骤

2.2.1 分解操作

定义left = 0, right = array.length-1; mid = (left + right)/2; 递归分解即可.[left,mid],[mid+1,right]; 注意递归的终止条件 left >= right.

/*** 归并排序* 时间复杂度: O(N*logN) 和快速排序类似,** 空间复杂度:O(N) - 临时数组和原数组长度一样.** 稳定性: 稳定.** @param array*/
public static void mergeSort(int[] array) {mergeSortFunc(array,0,array.length-1);}//先分解,再归并排序.private static void mergeSortFunc(int[] array,int left,int right) {if(left >= right) return;int mid = (left+right)/2;//分解左右mergeSortFunc(array,left,mid);mergeSortFunc(array,mid+1,right);//将小数组排序合并merge(array,left,mid,right);}

2.2.1 合并排序操作

1. 定义一个临时数组,用来存放有序的子序列,长度为 right - left + 1, k 指向数组起始位置; 令s1指向[left],s2指向[mid+1].
2. [s1] 与 [s2] 比较, 若[s1] > [s2], 则 [s2] 放到数组中, s2++, [s2] < [s1]…类推
3. 重复第二步 直到 s1 > mid && s2 > right.
4. s1 与 s2 中两边的元素总有一边先放完, 把剩下的那边元素放入临时数组即可.

5. 最后一步将有序的临时数组放回原数组.

//归并排序的核心private static void merge(int[] array,int left,int mid,int right) {int s1 = left;int s2 = mid+1;int k = 0;int[] tmpArr = new int[right-left+1];while(s1 <= mid && s2 <= right) {if(array[s2] <= array[s1]) { //等号不取便稳定.tmpArr[k++] = array[s2++];}else {tmpArr[k++] = array[s1++];}}//s1中所有元素都大于s2,s2放完了,s1还没放完.while(s1 <= mid) {tmpArr[k++] = array[s1++];}//s2中所有元素都大于s1,s1放完了,s2还没放完.while(s2 <= right) {tmpArr[k++] = array[s2++];}//tmpArr为有序数组.for (int i = 0; i < tmpArr.length; i++) {array[i+left] = tmpArr[i];//left不一定为0.}}

2.3 归并排序的非递归实现

在归并排序核心算法的基础上, 定义变量gap = 1, 循环for (int i = 0; i < array.length; i += gap*2)中, left = i; mid = left+gap-1; right = mid+gap; 这么定义可以将原数组分为若干个长度为2的小数组.
由于要不断分解, 故gap应当写一个循环.

处理细节:
当gap > array.length/2时, mid和right可能会越界, 所以 需要加上条件,防止越界.

代码如下:

 //归并排序的核心private static void merge(int[] array,int left,int mid,int right) {int s1 = left;int s2 = mid+1;int k = 0;int[] tmpArr = new int[right-left+1];while(s1 <= mid && s2 <= right) {if(array[s2] <= array[s1]) { //等号不取便稳定.tmpArr[k++] = array[s2++];}else {tmpArr[k++] = array[s1++];}}//s1中所有元素都大于s2,s2放完了,s1还没放完.while(s1 <= mid) {tmpArr[k++] = array[s1++];}//s2中所有元素都大于s1,s1放完了,s2还没放完.while(s2 <= right) {tmpArr[k++] = array[s2++];}//tmpArr为有序数组.for (int i = 0; i < tmpArr.length; i++) {array[i+left] = tmpArr[i];//left不一定为0.}}//归并排序的非递归实现.public static void mergeSortNor(int[] array) {int gap = 1;while(gap < array.length) {for (int i = 0; i < array.length; i += gap*2) {int left = i;int mid = left+gap-1;int right = mid+gap;//mid和right可能会越界if(mid >= array.length) {mid = array.length-1;}if(right >= array.length) {right = array.length-1;}merge(array,left,mid,right);}gap *= 2;}}

2.4 归并排序的特性总结:

1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
2. 时间复杂度：O(N*logN) -> 算法与快排类似.
3. 空间复杂度：O(N) -> 临时数组长度与原数组相同.
4. 稳定性：稳定

总的来说, 快排和归并排序还是需要花时间去想清楚每一步是怎么回事, 代码为什么要这么写??? 去解答心里有十万个为什么, 解答出自己问自己的所有的问题, 就说明掌握了这个知识点.
本篇博客到这里就结束啦, 感谢观看, 期待与你的下一次相遇!!!