快速排序
推荐去看个视频:数据结构与算法基础--第14周06--第8章排序6--8.3交换排序2--快速排序1_哔哩哔哩_bilibili
虽然java和c++有现成的sort函数,java用Arrays.sort,C++用sort,但是,我们也要了解其原理,要能熟练的写出模板。
快排和归并排序一样都是分治法思想。
快速排序的主要思想:
从序列中取一个基准值,然后将序列分为左右两部分, 使得左边的数都比基准值小,右边的数都比基准值大。递归这个过程,直到不能再分。
那么如何将序列分为左右两部分,以及基准值怎么选取是快排的核心。
快速排序的几种实现方式:
第一种, 左右交叉交换。(相当于是空瓶交换法)
基准值取法为 区间i-j的任意值(其实一般来说,只要选取中间值就好了)
选取基准值之后,开始考虑交换元素,目的是将右边比它大的都移到左边,将左边比它小的都移到右边。
平常交换两个元素的时候,我们需要一个额外的变量,比如 int t = a, a = b, b = t;
在这里我们也需要一个额外的变量。
第一步:
第二步:
第三步:交换
第四步: 递归查找9的左边所有元素,不包括9, 递归查找9的右边所有元素,不包括9。
算法的大致思路就是这样了,看一下怎么具体实现吧 代码C++和java的都有。
C++:
给定n个数,对n个数排序。
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string>
using namespace std;
int arr[1000005];
int n;
void q_sort(int i, int j){
if(i>=j) return;
int x =i+rand()%(j-i+1); // 随机取一个基准值
int piovt = arr[x]; // 将 arr[x]存起来
arr[x] = arr[i]; // arr[x]此时空了,所以将arr[i]先存到arr[x],此时arr[i]就空了。
int low = i;
int high = j;
while(low<high){
while(low<high&&arr[high]>=piovt) --high;
arr[low] = arr[high]; // 将小于piove的存到arr[low]中
while(low<high&&arr[low]<=piovt) ++low;
arr[high] = arr[low]; //将大于piove的存到arr[high]中
}
// 当low == high时, 说明piovt左边的元素都比他小,右边的元素都比他大,所以low的位置就是piovt
arr[low] = piovt; // 然后将piovt存在arr[low]中
q_sort(i,low-1); // 已经确定了一个元素的位置,然后确定(i, low-1)和(low+1,j);
q_sort(low+1,j);
};
int main(){
scanf("%d",&n);
for(int i = 0; i < n; i++){
scanf("%d",&arr[i]);
}
q_sort(0,n-1);
for(int i = 0; i < n; i++){
i ? printf(" %d",arr[i]) : printf("%d",arr[i]);
}
return 0;
}
JAVA:
import java.io.*;
import java.util.*;
public class 快速排序{
static int[] arr = new int[100010];
public static void q_sort(int l,int r){
if(l>=r)return;
int i = l;
int j = r;
int mid = l + r >> 1; // 相当于(l + r) / 2
int p = arr[mid];
arr[mid] = arr[i];
while(i < j){
while(i < j && arr[j] >= p) j--;
arr[i] = arr[j];
while(i < j && arr[i] <= p) i++;
arr[j] = arr[i];
}
arr[i] = p;
q_sort(l,i-1);
q_sort(i+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 s[] = in.readLine().split(" ");
for(int i = 0; i < s.length; i++){
arr[i] = Integer.parseInt(s[i]);
}
q_sort(0, n-1);
for(int i = 0; i < n; i++){
System.out.print(arr[i]+" ");
}
}
}
第二种:
左右交换
从左边找到一个大于等于基准值的数,从右边找到一个小于等于基准值的数,然后直接交换两个数的位置。
C++:
#include <iostream>
using namespace std;
int arr[1000005];
int n;
void q_sort(int i, int j){
if(i >= j) return;
int piovt = arr[(i+j)/2];
int low = i - 1;
int high = j + 1;
while(low<high){
do --high; while(arr[high]>piovt);
do ++low; while(arr[low]<piovt);
if(low<high){
swap(arr[high],arr[low]);
}
}
q_sort(i,high);
q_sort(high+1,j);
}
int main(){
scanf("%d",&n);
for(int i = 0; i < n; i++){
scanf("%d",&arr[i]);
}
q_sort(0,n-1);
for(int i = 0; i < n; i++){
printf("%d ",arr[i]);
}
return 0;
}
JAVA:
import java.io.*;
import java.util.*;
public class 快速排序{
static int[] arr = new int[100010];
public static void q_sort(int l,int r){
if(l>=r)return;
int i = l - 1;
int j = r + 1;
int x = arr[l + r >> 1];
while(i < j){
do i++;while(arr[i] < x);
do j--;while(arr[j] > x);
if(i<j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
q_sort(l,j);
q_sort(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 s[] = in.readLine().split(" ");
for(int i = 0; i < s.length; i++){
arr[i] = Integer.parseInt(s[i]);
}
q_sort(0, n-1);
for(int i = 0; i < n; i++){
System.out.print(arr[i]+" ");
}
}
}
推荐背下第二种模板,效率远大于第一种。