排序---快速排序及其切分函数Partition应用
2024-08-29 22:49:32
快速排序
快速排序通过一个切分元素将数组分成两个子数组,左子数组小于等于切分元素,右子数组大于切分元素,将这两个子数组排序,也就是将整个数组排序了。
代码如下:
public class Sort{
public static void quickSort(int []arr){
if(arr=null||arr.length<2)
return;
quickSort(arr,0,arr.length-1);
}
public static void quickSort(int[]arr,int l,int r){
if(l<r){
swap(arr, l + (int) (Math.random() * (r - l + 1)), r); //随机选取切分值,然后交换到数组最后一位
int []p=partition(arr,l,r);//返回于切分值相等的左右界
quickSort(arr,l,p[0]-1);
quickSort(arr,p[1]+1,r);
}
}
public static int[]partition(int[]arr,int l,int r){
int less=l-1; //小于区域的右边界
int more=r; //大于区域的左边界,初始包含最右端元素,即切分值。
while(l<more){
if(arr[l]<arr[r]){ //arr[r]作为切分值
swap(arr,++less,l++); //如果当前元素小于切分值,那么将当前元素和小于区域的右边第一个元素和当前元素交换,小于区域向右扩大一位,访问下一个元素,继续进行比较。
}else if(arr[l]>arr[r]){
swap(arr,--more,l);//如果当前元素大于切分值,那么将当前元素和大于区域的左边第一个元素和当前元素交换,大于区域向左扩大一位,继续访问当前元素,进行比较。
}else{ //和切分值相等
l++;
}
}
swap(arr,more,r); //将切分值换到中间
return new int[]{less+1,more}; //与切分值相等的区间
}
public static void swap(int[]arr,int more,int r){
arr[more]=arr[more]^arr[r];
arr[r]=arr[more]^arr[r];
arr[more]=arr[more]^arr[r];
}
}
快速排序是原地排序,不需要辅助数组,但是递归调用需要辅助栈。快速排序最好的情况下是每次都正好将数组对半分,这样递归调用次数才是最小的。这种情况下比较次数为Cn=2Cn/2+n,复杂度为O(NlogN)。
最坏的情况是,第一次从最大的元素或最小的元素切分,第二次从第二大或者第二小的元素切分,如此这般,最坏情况下的比较次数为N * N /2。为了防止数组一开始就是有序的,我们在选择切分值是,进行随机选取。
切分函数partition的应用,荷兰国旗问题,将数组分成三部分,分别对应于小于,等于,大于 切分元素。时间复杂度为O(n)。
public int[]partition(int []arr,int l,int r){
int less=l-1; //小于区域的右边界
int more=r; //大于区域的左边界,初始包含最右端元素,即切分值。
while(l<more){
if(arr[l]<arr[r]){ //arr[r]作为切分值
swap(arr,++less,l++); //如果当前元素小于切分值,那么将当前元素和小于区域的右边第一个元素和当前元素交换,小于区域向右扩大一位,访问下一个元素,继续进行比较。
}else if(arr[l]>arr[r]){
swap(arr,--more,l);//如果当前元素大于切分值,那么将当前元素和大于区域的左边第一个元素和当前元素交换,大于区域向左扩大一位,继续访问当前元素,进行比较。
}else{ //和切分值相等
l++;
}
}
swap(arr,more,r); //将切分值换到中间
return new int[]{less+1,more}; //与切分值相等的区间
}
最新文章
- ABAP 读取销售订单抬头文本自建函数
- mysql A表部分记录复制到B表
- oracle数据库开启的时候 是先开监听还是先开主服务,关数据库的时候呢???
- Nao 类人机器人 相关资料
- 【转】MYSQL入门学习之九:索引的简单操作
- MySQL 5.7.13解压版安装记录 mysql无法启动教程
- 2015 CCC - 01 统计数对
- 解决ie6 闪动的问题
- SpringBoot整合Redis、ApachSolr和SpringSession
- js跨域解决方案
- python爬虫(4)——正则表达式(一)
- 用类模拟C风格的赋值+返回值
- 利用Python制作简单的小程序:IP查看器
- luogu5021 [NOIp2018]赛道修建 (二分答案+dp(贪心?))
- Excel技巧--分隔工资条
- Android开发属性动画
- Java IO流杂谈
- <;A Decomposable Attention Model for Natural Language Inference>;(自然语言推理)
- 拒绝“高冷”词汇!初学C#中实用的泛型!
- 啰哩吧嗦式讲解在windows 家庭版安装docker