目录
一、问题描述
二、解题思路
快排算法实现数组排序：快排的核心步骤是分区操作。
下面详细图解一次分区过程：
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++实现，属于伪代码，应试的话可以参考一下：
