快速排序

算法目的

    
    对包含n个数的无序数组进行排序。

编码软件
     Dev-C++ 5.11
算法思想
    快速排序采用了分治思想，对数组a[p…r]进行三步分治过程实现排序功能。
    分解：数组a[p…r]被划分成两个（可能为空）子数组a[p…q-1]和a[q+1…r]，使得a[p…q-1]中的每个元素都小于等于a[q]，而a[q]也小于等于a[q+1…r]中的每一个元素。
    解决：通过递归调用快速排序，对子数组a[p…q-1]和a[q+1…r]进行排序。
    合并：因为子数组是原址排序，所以不需要合并操作：数组a[p…r]已经有序。
    Algoritms quickSort(a[],p,r)
        if p<r
            q = patition(a,p,r)
            quickSort(a,p,q-1)
            quicksort(a,q+1,r)
    patition(a[],p,r)
        x=a[r]
        i=p-1
        for j=p to r-1
            if a[j]<=x
            i=i+1
            if I != j
                exchange a[i] with a[j]
                exchange a[i+1] with a[r]
        return i+1
初始调用
quickSort(a,0,a.length-1)
patition(a,0,a.length-1)
    p=0，r=a.length-1，x=a[r] //选择a数组中最后一个元素作为主元
    i=p-1
    for j=p to r-1 //从数组左边开始搜索
        if a[j]<=x //若小于等于主元
          i=i+1
         if i != j
            exchange a[i] with a[j] //当下标不同时交换数组元素才有意义
      //循环结束后小于等于主元x的元素位于a[0…i]
    exchange a[i+1] with a[r] //此句执行后大于主元x的元素位于a[i+2…r]
    return i+1
  //此时a[0…i]中的元素小于等于a[i+1]，a[i+2…r]中的元素大于a[i+1]
  //若a[r]是最大的元素，则i+1 =r
  //若a[r]是最小的元素，则exchange a[p] with a[r]，i+1 = p
再递归调用quickSort(a,0,i)
         quickSort(a,i+2,r)

c语言描述：

#include <stdio.h>
#include<time.h>
#include<stdlib.h>

int patition(int input[],int left,int right){    //分解实现 
    int x=input[right];
    int i=left-1;
    int j,temp;
    
    for(j=left;j<right;j++){    //input[left...i]小于等于x 
        if(input[j]<=x){
            i++;
            if(i!=j){                
                temp=input[j];
                input[j]=input[i];
                input[i]=temp;    
            }
        }
    }
    
    temp=input[i+1];    //input[i+2...right]大于x 
    input[i+1]=input[right];
    input[right]=temp;
    
    return i+1;
}

 void quickSort(int input[],int left,int right){
     int q;
    if (left<right){
        
         q=patition(input,left,right);
         
         quickSort(input,left,q-1);    //解决子数组实现 
         quickSort(input,q+1,right);
         
     }
 } 
 
 int main(){
     int i;
     int simple[10];
     
     //产生随机数
     srand((unsigned)time(NULL));
         
         for(i=0;i<=9;i++){
             simple[i] = rand()%100;
         }
      
      quickSort(simple,0,9);    //首次调用 
      
      for(i=0;i<=9;i++){
          printf("%3d",simple[i]);
      }
      
     return 0;
 }

时间复杂性
    最坏情况：每次划分产生的子数组分别包含n-1个元素和1个元素，此时得到的递归式为T(n)=T(n-1)+O(n)，时间复杂度为O(n2)
    最好情况：每次划分产生的子数组分别包含n/2个元素，此时得到的递归式为T(n)=2T(n/2)+O(n)，时间复杂度为O(nlogn)。
    平均情况：更接近于其最好情况，所以快速排序的运行时间为O(nlogn)。

快速排序

原文：http://www.cnblogs.com/sillypasserby/p/5090380.html