紫書_第八章_高效算法設計_8.2.2——快速排序

其分為三個步驟：

1.劃分問題：把數組的各個元素重排後分成左右兩部分，左邊始終小于key，右邊大于key。

2.遞歸求解：把左右兩部分分别排序。

3.合并問題：其不用合并，因為此時數組已經有序。

來看代碼：

/*************************************************************************
	> File Name: 1166.cpp
	> Author:chudongfang 
	> Mail:[email protected] 
	> Created Time: 2016年06月15日 星期三 16時43分32秒
 ************************************************************************/

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#define INF (1ll<<60)-1
using namespace std;
typedef long long ll;
void Q_sort(int a[],int n);
int main(int argc,char *argv[])
{
    int a[100];
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    
    Q_sort(a,n);

    for(int i=0;i<n;i++)  
        printf("%d ",a[i]);
    return 0;
}

void Q_sort(int a[],int n)
{
    int key=a[0];//利用key進行劃分
    int i=0,j=n-1;
    if(n<=1)   return ;
    else
    {
        while(i!=j)
        {
            for(;i<j;j--)   
                if(a[j]<key) 
                {
                    a[i]=a[j];
                    break;
                }
            for(;i<j;i++)
                if(a[i]>key)
                {
                    a[j]=a[i];
                    break;
                }
            if(i==j)   a[i]=key;
        }
        Q_sort(a,i);//遞歸求解     
        Q_sort(a+i+1,n-i-1);
        //由于其已經有序，就不用再進行合并。
    }
}