洛谷1177 快速排序 解题报告

洛谷1177 快速排序

本题地址： http://www.luogu.org/problem/show?pid=1177

题目描述

利用快速排序算法将读入的N个数从小到大排序后输出。
快速排序是信息学竞赛的必备算法之一。对于快速排序不是很了解的同学可以自行上网查询相关资料，掌握后独立完成。（C++选手请不要试图使用STL）

输入输出格式

输入格式：

输入文件sort.in的第1行为一个正整数N，第2行包含N个空格隔开的正整数a[i]，为你需要进行排序的数，数据保证了A[i]不超过1000000000。

输出格式：

输出文件sort.out将给定的N个数从小到大输出，数之间空格隔开，行末换行且无空格。

输入输出样例

输入样例#1：

5
4 2 4 5 1

输出样例#1：

1 2 4 4 5

说明

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

题解

排序+分治

纯排序题。但要注意n的数据范围，很显然O(n^2)的简单排序只能过20%的数据，而且题目也告诉我们要用快排。

快速排序是一种基于分治策略的排序方法。其基本思想是：从待排序列中选取一个元素作为基准元素，然后从两端向中间依次进行比较和交换。

根据基准元素的选取我们可以把它分为取首快排、取中快排、随机快排。

快排的时间复杂度为O(nlogn)，然而在待排序列基本有序的情况下，快排的时间复杂度会退化为O(n^2)，本题也有类似的数据卡时间。

如果使用随机快排可以大大降低退化的概率，所以说随机快排应该是一个不错的选择，对于100%的数据无压力。笔者采用的就是随机快排。

下面附上代码。

代码

1. var  
2.   n,i:longint;  
3.   a:array[1..100000] of longint;  
4. procedure qsort(head,tail:longint);  
5.   var  
6.     i,j,x,t:longint;  
7.   begin  
8.     i:=head;  
9.     j:=tail;  
10.     x:=a[random(tail-head+1)+head];  
11.     while i<j do  
12.       begin  
13.         while a[i]<x do inc(i);  
14.         while x<a[j] do dec(j);  
15.         if i<=j then  
16.           begin  
17.             t:=a[i];  
18.             a[i]:=a[j];  
19.             a[j]:=t;  
20.             inc(i);  
21.             dec(j);  
22.           end;  
23.       end;  
24.     if head<j then qsort(head,j);  
25.     if i<tail then qsort(i,tail);  
26.   end;  
27. begin  
28.   readln(n);  
29.   randomize;  
30.   for i:=1 to n do  
31.     read(a[i]);  
32.   qsort(1,n);  
33.   for i:=1 to n do  
34.     write(a[i],' ');  
35.   writeln;  
36. end.  

（本文系笔者原创，未经允许不得转载）