由一个模板题引出的小总结-洛谷p1777快速排序

, ,

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

题目链接
快速排序是信息学竞赛的必备算法之一。对于快速排序不是很了解的同学可以自行上网查询相关资料，掌握后独立完成。（C++C++选手请不要试图使用STL，虽然你可以使用sort一遍过，但是你并没有掌握快速排序算法的精髓。）

输入输出格式
输入格式：
第1行为一个正整数N，第2行包含N个空格隔开的正整数ai ,为你需要进行排序的数，数据保证了Ai不超过1000000000.

输出格式：
将给定的N个数从小到大输出，数之间空格隔开，行末换行且无空格。

输入输出样例
输入样例#1：
5
4 2 4 5 1
输出样例#1：
1 2 4 4 5

说明:
对于20%的数据，有N≤1000；

对于100%的数据，有N≤100000。

题解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
int a[100010];
void quick_sort(int x,int y){
    int i=x,j=y,t;
    int k=a[x];//选取最左边一个书为基准数,这样数据量太大的时候就会超时
  
    if(i>=j)    return;
    while(i<j){
        while(i<j&&a[j]>=k) j--;
        t=a[i];
        a[i]=a[j];
        a[j]=t;
        while(i<j&&a[i]<k)  i++;
        t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
    quick_sort(x,i-1);
    quick_sort(i+1,y);
    return;
}
int main(){
    int n;
    scanf("%d",&n);//个数
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);//将输入的数据用数组存储起来
    }
    quick_sort(0,n-1);
    for(int i=0;i<n;i++){
        printf("%d ",a[i]);
    }
    return 0;
}

如果用上面的快速排序，有些测试数据此程序会运行超时，过不了。
基于此，我们可以对快速排序进行优化：

方法一：随机化
上面的快排中总是选择第一个元素作为基准数，在数字已经有序的情况下每次划分都将得到最坏的结果，时间复杂度退化为O(n^2)因为子序列比原序列只少一个元素，这样的话，递归深度就很大。快排的分治思想的优势一点都没有了。
所以，我们可以随机的选择一个元素作为基准数，然后让这个元素与第一个元素交换位置，这样就可以继续用原来的方法来处理。
如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void swap(int &a,int &b){//交换函数
	int temp=a;
	a=b;
	b=temp;
}
void quicksort(int left,int right){
	if(left>right)	return;
	int i=left,j=right;
	int ranw=rand()%(right-left+1)+left;//此处为随机化
	swap(a[left],a[ranw]);//此处为将随机取得元素与第一个元素互换位置
	while(i<j){
		while(j>i&&a[j]>=a[left])	j--;
		while(i<j&&a[i]<=a[left])	i++;
		swap(a[i],(i==j)?a[left]:a[j]);//如果i==j说明，i，j相遇，
//此时要将基准元素与此位置交换，即swap(a[i],a[left])或者swap(a[j],a[left])
//（因为这个时候i，j都指向同一个位置）
		//如果i不等j，说明还没有相遇，此时只要转换swap(a[i],a[j])
	}
	quicksort(a,left,i-1);//递归
	quicksort(a,j+1,right);
}

方法二：小区间使用插入排序
当递归到了一定程度之后，序列长度足够小了，我们就可以对其较小的序列改用插入排序，因为长度较好后，分治递归的处理速度比直接插入慢。
如下：

void insertsort(int left,int right){//直接插入排序
    for(int i=left+1;i<=right;i++){
        for(int j=i;j>0&&a[j]<a[j-1];j--)    swap(a[j],a[j-1]);
    }

void quicksort(int left,int right){
    if(left>=right)    return;
    if(right-left+1<10){  //这里就是如果长度小于10，就使用直接插入排序
        insertsort(left,right);
        return;
    }
    int ranw=rand()%(right-left+1)+left;//此处为随机化
    swap(a[left],a[ranw]);//此处为将随机取得元素与第一个元素互换位置
    while(i<j){
        while(j>i&&a[j]>=a[left])    j--;
        while(i<j&&a[i]<=a[left])    i++;
        swap(a[i],(i==j)?a[left]:a[j]);
    }
    quicksort(a,left,i-1);//递归
    quicksort(a,j+1,right);
}```
**方法三：聚拢重复元素**
待补充
===========================================我是可爱的分割线===========================================
除了上述三种对快速排序的优化，我们还可以使用堆排序。
**方法四：堆排序**

```c++
#include<cstdio>
#include<iostream>
using namespace std;
int num=0;
int n;
int a[1000100];
void up(int x){//上浮操作
    while(a[x/2]>a[x]&&x!=1){
        swap(a[x],a[x/2]);
        x/=2;
    }
}
void down(int x){//下沉操作
    while((a[x*2]<=a[x]&&x*2<=num)||(a[x*2+1]<=a[x]&&x*2+1<=num)){
        if(a[x*2]<=a[2*x+1]){
            swap(a[x],a[x*2]);
            x*=2;
        }else{
            swap(a[x],a[x*2+1]);
            x=x*2+1;
        }
    }
}

void insert(int x){//向堆中插入元素，建堆的核心操作所在   
    num++;
    a[num]=x;//数组a是从下标1开始存储数据
    up(num);
}

void work(){//建堆成功后，将堆顶元素和最后一个元素互换位置
//堆顶元素先输出，然后被最后一个元素覆盖，
//就相当于将堆顶元素删除了，（即不再参与排序）
    printf("%d ",a[1]);//打印堆顶元素
    a[1]=a[num--];//堆顶元素被覆盖
    //上面一句话可以这样写,更好理解
    //a[1]=a[num];
    //num--;
    //因为堆顶元素被覆盖了，自然的堆中元素的个数要减一，即num--
    down(1);//元素变化后，重新通过下沉，排序成一个新的堆
}

void build(){//输入数字，调用插入函数，建堆
    for(int i=1;i<=n;i++){
        int z;
        scanf("%d",&z);
        insert(z);
    }
}

void shuchu(){
    while(num!=1)   work();
    printf("%d",a[1]);
}


int main(){  
    scanf("%d",&n);
    build();
    shuchu();
    return 0;
}```