当前位置：首页 > news >正文

排序-快排算法对数组进行排序

news 来源：原创 2024/7/3 3:39:15

一、问题描述

二、解题思路

1.初始化

2.将右侧小于基准元素移到左边

3.将左侧大于基准元素移到右边

4.重复执行上面的操作

5.对分好的左、右分区再次执行分区操作

6.最终排序结果

三、代码实现

四、刷题链接

一、问题描述

二、解题思路

快排算法实现数组排序：快排的核心步骤是分区操作。

下面详细图解一次分区过程：

1.初始化

2.将右侧小于基准元素移到左边

赋值后相当于下面的情形：

3.将左侧大于基准元素移到右边

然后开始比较arr[low]和pivot的大小：（和上图作对比）

赋值后的数组为：

4.重复执行上面的操作

再次修改high（左移--），移动元素，再次修改low（右移++），移动元素；当low==high时停止，完成一次分区操作：

5.对分好的左、右分区再次执行分区操作

分区返回的是中间元素位置，我们要对左、右两个子分区再次执行分区操作，每次分区都会确定一个中间位置（后序不会再变），当分区内元素都为1的时候，快排结束。

6.最终排序结果

三、代码实现

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** 将给定数组排序* @param arr int整型一维数组 待排序的数组* @return int整型一维数组*/public int[] MySort (int[] arr) {// 使用快排排序QuickSort(arr,0,arr.length-1);return arr;}public int partition(int[] arr,int low,int high){int pivot=arr[low];//分界元素//System.out.println("low:"+low+",high:"+high);while(low<high){while(arr[high]>=pivot){//右侧元素大于pivot不移动if(low==high){break;}high--;}arr[low]=arr[high];//现在的arr[high]已经没有元素了while(arr[low]<=pivot){//左侧元素小于等于pivot不移动if(low==high){break;}low++;}arr[high]=arr[low];}//此时low位置就是初始的分界元素应该在的位置arr[low]=pivot;return low;}public void QuickSort(int[] arr,int low,int high){int pivotIndex=partition(arr,low,high);if(low<pivotIndex-1){QuickSort(arr,low,pivotIndex-1);}if(high>pivotIndex+1){QuickSort(arr,pivotIndex+1,high);}}
}

快排算法里面要注意边界条件，这个好好思考一下。

如果考研的话可以写伪代码，边界条件可以考虑的少一点

排序算法相关代码-CSDN博客文章浏览阅读108次。【代码】排序算法相关代码。https://blog.csdn.net/hehe_soft_engineer/article/details/134235961下面是之前写的排序算法的C++实现，属于伪代码，应试的话可以参考一下：