题目描述
给定你一个长度为n的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行,第一行包含整数 n。
第二行包含 n 个整数(所有整数均在1~109范围内),表示整个数列。
输出格式
输出共一行,包含 n 个整数,表示排好序的数列。
数据范围
1≤n≤100000
样例
输入样例:
5
3 1 2 4 5
输出样例:
1 2 3 4 5
算法1
快速排序的思想(基于分治):
(1)确定分界点,以arr[l]或arr[r]或arr[(l+r)/2]作为边界点都可以
(2)调整数组中数的位置,将整个数组分割成两段
(3)递归处理两段的数据
时间复杂度
O(n * log(n))
Java 代码
import java.util.Scanner;
/**
* 快速排序的思想:
* (1)确定分界点,以arr[l]或arr[r]或arr[(l+r)/2]作为边界点都可以
* (2)调整数组中数的位置,将整个数组分割成两段
* (3)递归处理两段的数据
**/
public class Main{
static void swap(int[] arr,int a,int b){
int tmp = arr[a];
arr[a]=arr[b];
arr[b]=tmp;
}
static void quick_sort(int[] arr,int L,int R){
if(L >= R) return;
//确定分界点
int x = arr[L],l=L-1,r=R+1;
//调整位置
while(l < r){
do l++;while(arr[l]<x);
do r--;while(arr[r]>x);
if(l < r) swap(arr,l,r);
}
//进行递归
quick_sort(arr,L,r);
quick_sort(arr,r+1,R);
}
public static void main(String[] args){
Scanner input = new Scanner(System.in);
int n = input.nextInt();
int[] arr = new int[n];
for(int i=0;i<n;i++){
arr[i]=input.nextInt();
}
quick_sort(arr,0,n-1);
for(int num : arr){
System.out.print(String.valueOf(num)+' ');
}
}
}
算法2
(分治思想)
这种算法是对上一种算法的优化
时间复杂度
O(n * log(n))
Java 代码
#include <iostream>
using namespace std;
const int N=100010;
int a[N];
//arr进行patition的数组,patiton时的左边界L,patiton时的右边界R
pair<int,int> patition(int arr[],int L,int R){
//l为数组中左半边小于分界点的数的下标最大值,r为数组中右半边大于分界点的数的下标最小值,p为遍历的指针
int l=L-1,r=R,p=L;
//默认令arr[R]为分界点
while(p < r){
//当p所在的数子小于分界点的值,将左边界+1,然后和当前数字互换,再将指针后移
if(arr[p] < arr[R]) swap(arr[++l],arr[p++]);
//当p所在的数子大于分界点的值,将右边界-1,然后和当前数字互换,指针不后移
else if(arr[p] > arr[R]) swap(arr[--r],arr[p]);
//当p所在的数子等于分界点的值,p++
else p++;
}
//因为开始时,有边界为R,所以arr[R]等于分解值,所以交换
swap(arr[r],arr[R]);
return make_pair(l+1,r);
}
void quick_sort(int arr[],int L,int R){
if(L < R){
pair<int,int> p=patition(arr,L,R);
quick_sort(arr,L,p.first-1);
quick_sort(arr,p.second+1,R);
}
}
int main(){
ios::sync_with_stdio(false);
int n;
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
quick_sort(a,0,n-1);
for(int i=0;i<n;i++) cout<<a[i]<<" ";
return 0;
}
问题:使用快排模板
void quick_sort(int q[], int l, int r)
{
if (l >= r) return;
int i = l - 1, j = r + 1, x = q[l + r >> 1];
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}
quick_sort(q, l, j);
quick_sort(q, j + 1, r);
}
- 情形一:
x=q[l];quick_sort(q,l,i);quick_sort(q,i+1,r)
;
此时一些用例会报:[HTML_REMOVED]Wrong Answer[HTML_REMOVED]
因为q[i]肯定是大于等于x的,所以会报错,即在区间l~i
之间会可能会有大于x的值。
- 情形二:
x=q[l];quick_sort(q,l,j);quick_sort(q,j+1,r)
;
这种情况是正确的。
- 情形三:
x=q[r];quick_sort(q,l,i);quick_sort(q,i+1,r);
此时一些用例会报:[HTML_REMOVED]Memory Limit Exceeded [HTML_REMOVED]
此时会出现无限递归,因为i是可以取到边界的,比如[1,2],此时i=1,j=1。
- 情形四:
x=q[r];quick_sort(q,l,j);quick_sort(q,j+1,r);
此时也会出现无限递归,比如[1,2]。