分治思想，快排的最原始版本,hoare-quick-sort


#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define max 1000000
int hoare_partition(int* A , int p , int r)
{
    int x = A[p];
    int i = p - 1;
    int j = r + 1;
    do
    {
        do
        {
            j --;
        }while( A[j] > x );
        do
        {
             i ++ ;
        }while( A[i] < x );
        if( i < j )
        {
            int k = A[j];
            A[j] = A[i];
            A[i] = k;
        }
        else return j ;
    }while(1);
}
void quick_sort( int * A , int p , int r )
{
    if( p < r )
    {
        int q = hoare_partition(A , p , r);
        quick_sort(A , p , q);
        quick_sort(A , q + 1 , r); 
    }
}
int main()
{
    int A[max];
    int i;
    double start , end;
    srand(time(0));
    for( i = 0; i < max; i ++ )
    {
        A[i] = rand() % max;
    }
    start = (double) clock();
    quick_sort(A , 0 ,max);
    end = (double) clock();
    /*
    for( i = 0; i < max; i ++ )
    {
        printf("%d  " , A[i]);
    }
    putchar(
);
    */
    printf("%.4fs
", (end - start)/CLOCKS_PER_SEC);
    return 0;
}
从历史来看，快排是由hoare最开始发明的，当时他的partition算法并不是上一个文章中提到的那种算法。其实在实现中，可以很明显的看出这两个partition算法的区别。第一个算法只用了一个指针，指向第一个比x大的元素的位置，最有再将最后一个元素与该位置交换，这样，选出的元素其实就将一个数组分成了两个部分，而且这两个部分是由该元素进行分割开来的。而这个算法则用了两个指针，一个指向前面以保证该指针前面的元素都小于选定元素，后一个指针功能一样。这样分割之后并没有用一个元素进行分割，而是保证了返回点之前的元素小于等于返回点后面的元素。所以相应的需要在后面的排序算法中进行改进。当然这里的元素选定也可以采用一个随机算法，只需要相应的改进就行了

补充：综合编程 , 其他综合 ,