[AcWing]Java——快速排序
发布日期:2022-03-09 00:49:09 浏览次数:32 分类:技术文章

本文共 2307 字,大约阅读时间需要 7 分钟。

                              

思想:1、确定分界点 :x=q[ l ] 、q[ r ] 、q[ (l+r) / 2] 、随机

           2、调整区间,让第一个区间内所有的数<=x,第二个区间内的所有数>=x 。

           3、递归处理左右两端,分别给左边右边排序

步骤:用两个指针,分别指在数组的两端,两个指针分别往中间走。 i指针指向的数小于x,则这个数最终在左边,i往后移动一位,重复以上步骤,直到i指针指向的数>=x,停下来。然后看j指针,j指针一直往中间走(同上),直到某次<=,此时两个数错位了,将两个数交换,此时两个数的指向正确了,继续重复步骤,直到相遇为止。

注意:边界问题

两个指针最开始放到左右边界两侧,外侧,然后再往进扩。

例题:利用快速排序算法将读入的 N 个数从小到大排序后输出。

import java.io.*;class Main{
static int N=100010;
static int[] a=new int[N]; //创建数组////模板
static void quickSort(int l,int r){
if(l==r) return;
 int key=a[l+r>>1];  //选中间值
int i=l-1;
  int j=r+1;  //两个指针往中间移动
while(i =j
do{i++;}while(a[i]
do{j--;}while(a[j]>key);
//while循环结束后,q[l..j]<=x, q[j+1..r]>=x
   if(i
int item=a[i];
a[i]=a[j];
a[j]=item;
}
}
quickSort(l,j);
quickSort(j+1,r);//递归
}////
public static void main(String[]args) throws IOException{
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(in.readLine());
String[]arr=in.readLine().split(" ");
for(int i=0; i
quickSort(0,n-1);
for(int i=0; i
}}//(q, l, i - 1) (q, i, r) 配套x=q[(l + r >> 1) + 1]//(q, l, j) (q, j + 1, r)配套x=q[l + r >> 1]

例题:给定一个长度为 n 的整数数列,以及一个整数 k,请用快速选择算法求出数列从小到大排序后的第 k个数

import java.io.*;import java.util.*;public class Main{
public static void main(String[] args) throws IOException{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String[] strs = reader.readLine().split(" ");
int n = Integer.parseInt(strs[0]);
int k = Integer.parseInt(strs[1]);
int[] arr = new int[n];
strs = reader.readLine().split(" ");
for(int i = 0; i < n; i++){
arr[i] = Integer.parseInt(strs[i]);
}
int res = quickSort(arr, 0 , arr.length - 1, k);
System.out.println(res);
reader.close();
}
public static int quickSort(int[] arr, int start, int end, int k){
if(start >= end) return arr[start];
int stard = arr[start];
int low = start, high = end;
while(low < high){
while(low < high && stard <= arr[high]) high--;
arr[low] = arr[high];
while(low < high && stard >= arr[low]) low++;
arr[high] = arr[low];
}
arr[low] = stard;
//统计sl的个数
int sl = high - start + 1;
if(k <= sl) return quickSort(arr, start, high, k);
return quickSort(arr, high + 1, end, k - sl);
}}

转载地址:https://blog.csdn.net/m0_56632342/article/details/122683244 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:JS bug 浮点数精度问题 day02-4
下一篇:机器学习入门之分类、决策树、随机森林、KNN、SVM、分类、AUC、准确率、平均准确率、召回率、F1

发表评论

最新留言

网站不错 人气很旺了 加油
[***.192.178.218]2023年01月18日 12时35分48秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

最新文章