洛谷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%的数据无压力。笔者采用的就是随机快排。

下面附上代码。

代码

var    n,i:longint;    a:array[1..100000] of longint;  procedure qsort(head,tail:longint);    var      i,j,x,t:longint;    begin      i:=head;      j:=tail;      x:=a[random(tail-head+1)+head];      while i<j do        begin          while a[i]<x do inc(i);          while x<a[j] do dec(j);          if i<=j then            begin              t:=a[i];              a[i]:=a[j];              a[j]:=t;              inc(i);              dec(j);            end;        end;      if head<j then qsort(head,j);      if i<tail then qsort(i,tail);    end;  begin    readln(n);    randomize;    for i:=1 to n do      read(a[i]);    qsort(1,n);    for i:=1 to n do      write(a[i],' ');    writeln;  end.  

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

转载于:https://www.cnblogs.com/yzm10/p/4748802.html

相关资源：数据结构 冒泡排序 输出每一趟结果