快速排序

介绍

   快速排序是基于分治思想的一种排序算法。
   是一种内部排序,也就是说排序的对象是已经读入内存的数据.并且快速排序是基于比较的.
  快速速排序的效率取决于选取为排序标准的键值能否尽可能将数据均分。
   所以我们经常会使用随机化取中点和三者取中的策略.

基本思想

快速排序的思想是:先从数据序列中选一个元素,并将序列中所有比该元素小的元素都放到它的右边或左边,再对左右两边分别用同样的方法处之直到每一个待处理的序列的长度为1, 处理结束.

1. 分：选择一个基准键值A[i]，把所有元素按照大小分成两部分；（这样能确定一个元素的最后位置）
2. 治：把两个子序列分别进行快排直到只剩下一个元素。

分析

最坏情况下θ(n^2) 平均情况下为θ(nlgn)

代码

PASCAL

C++

算法实例

例:输入一组数据小到大排序。

程序1

program kspv;
const n=7;
type
arr=array[1..n] of integer;
var
a:arr;
i:integer;
procedure quicksort(var b:arr; s,t:integer);
var i,j,x,t1:integer;
  begin
  i:=s;j:=t;x:=b[i];
  repeat
   while (b[j]>=x) and (j>i) do j:=j-1;
   if j>i then begin t1:=b[i]; b[i]:=b[j];b[j]:=t1;end;
   while (b[i]<=x) and (i<j) do i:=i+1;
   if i<j then begin t1:=b[j];b[j]:=b[i];b[i]:=t1; end
  until i=j;
  b[i]:=x;
  i:=i+1;j:=j-1;
  if s<j then quicksort(b,s,j);
  if i<t then quicksort(b,i,t);
  end;
begin
write('input data:');
for i:=1 to n do read(a[i]);
writeln;
quicksort(a,1,n);
write('output data:');
for i:=1 to n do write(a[i]:6);
writeln;
end.

程序2

program kspv;
const n=7;
type
arr=array[1..n] of integer;
var
a:arr;
i:integer;
procedure quicksort(var b:arr; s,t:integer);
var i,j,x:integer;
  begin
  i:=s;j:=t;x:=b[i];
  repeat
   while (b[j]>=x) and (j>i) do j:=j-1;
   if j>i then begin  b[i]:=b[j];i:=i+1;end;
   while (b[i]<=x) and (i<j) do i:=i+1;
   if i<j then begin b[j]:=b[i];j:=j-1; end
  until i=j;
  b[i]:=x;
  i:=i+1;j:=j-1;
  if s<j then quicksort(b,s,j);
  if i<t then quicksort(b,i,t);
  end;
begin
  write('input data:');
  for i:=1 to n do read(a[i]);
  writeln;
  quicksort(a,1,n);
  write('output data:');
  for i:=1 to n do write(a[i]:6);
  writeln;
end.

一个与C++库函数不相上下的QuickSort

（言过其实了，C++ STL的Sort实现用的是Introsort，是快速排序的变种，主要是递归过深的时候自动转换为堆排或插入排序（是堆排还是插入排序还要视具体实现而定），可以保证最坏情况下还是O(nlogn)，并且充分使用了尾递归优化（快排最后不是两个递归吗？最后一个递归可以不必真的递归，可以像gcd算法一样通过迭代参数来改善运行速度），STL快排可以经受任何实践的考验，而这段代码在最坏情况下还是O(n^2)) -- by 某奋战的OIer

此代码经过了一个多月的极致优化，测试。近乎完美。

本人觉得直接将template T直接换成int,long之类爽快些！

<template T> //
void sort(T a[],T st,T ed)
{ if(st<ed)   //先设一个开关优化，会更快一些
  { T tmp=a[st],i=st,j=ed;
    while(i<j)
    { while(a[j]>tmp&&i<j) --j;  //C++在判断时，会打开编译开关，把a[j]与tmp放在前比较，这样会更快一些~~
      if(i<j) a[i++]=a[j]; //ps:j-- ,i++(下行）比不了--j,++i快
      while(a[i]<tmp&&i<j) ++i;//注意：这里用的不是">="或"<="而是">""<，事实证明，前者会增加交换的次数，做无用功~~~
      if(i<j) a[j--]=a[i];     //ls,你活在梦里吗？哪个会增加交换次数？？？？？？？？？？也别奋战oi了，该干嘛干嘛去吧。
    }  //while
      a[i]=tmp;
      sort(a,st,i-1);
      sort(a,i+1,ed);
   }  //if
   //这里不用return语句，会快一些
}  
 //由于以上的种种，程序在大的排序中（N>=10e6)优势越来越大--By LinuxKernel

java ver

import java.util.Random;
 
public class Quick{
	public static void quick_sort(int[] arr, int left, int right){
		if(right < left)return;
 
		int pivote = arr[left];
		int rp = right;
		int lp = left;
 
		while(rp > lp){
			while((arr[rp] >= pivote) && (rp > lp))rp--;
			arr[lp] = arr[rp];
 
			while((arr[lp] < pivote) && (rp > lp))lp++;
			arr[rp] = arr[lp];
		}
 
		arr[lp] = pivote;
		quick_sort(arr,left,lp-1);
		quick_sort(arr,lp+1,right);
	}
 
 
	public static void main(String[] args){
 
		int SIZE = 20;
		int[] arr = new int[SIZE];
		Random rd = new Random();
 
 
		System.out.print("ori:");
		for(int i=0; i<arr.length; i++){
			arr[i] = rd.nextInt(100);
			System.out.print(arr[i] + " ");
		}
		System.out.println("");
		quick_sort(arr,0, arr.length - 1);
		System.out.print("des:");
		for(int i=0; i<arr.length; i++){
			System.out.print(arr[i] + " ");
		}
		System.out.println("");	
	}
 
}

python ver

def quick(lst, left, right):
	if left >= right:return
	rp = right
	lp = left
	pivote = lst[lp]
	#屁vote?这网站上都是些什么玩意？
	while(rp > lp):
		while (rp > lp) and (lst[rp] >= pivote):
			rp -= 1
		lst[lp] = lst[rp]
 
		while (rp > lp) and (lst[lp] < pivote):
			lp += 1
		lst[rp] = lst[lp]
	lst[rp] = pivote
	quick(lst,left, lp-1)
	quick(lst,lp+1,right)
 
 
def _test():
	lst = [ random.randint(1,100) for i in xrange(20) ]
	print( 'source:%s' % lst )
 
	quick( lst, 0, len(lst) - 1 )
	print( 'dest  :%s\n' % lst )
 
if __name__ == '__main__':
	_test()

快速排序是一个小作品，欢迎帮助扩充这个条目。