数据结构-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=right
array[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. 稳定性：稳定
总的来说, 快排和归并排序还是需要花时间去想清楚每一步是怎么回事, 代码为什么要这么写??? 去解答心里有十万个为什么, 解答出自己问自己的所有的问题, 就说明掌握了这个知识点.
本篇博客到这里就结束啦, 感谢观看, 期待与你的下一次相遇!!!
原文地址：https://blog.csdn.net/2302_81886858/article/details/143957164
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！