快速排序

http://www.cnblogs.com/maybe2030/p/4715042.html

非递归快速排序

http://blog.jobbole.com/93806/

 归并排序

http://linusp.github.io/2014/01/11/merge-sort.html

6. 快速排序（Quick Sort）

　　基本思想：快速排序算法的基本思想为分治思想。

　　1）先从数列中取出一个数作为基准数；

　　2）根据基准数将数列进行分区，小于基准数的放左边，大于基准数的放右边；

　　3）重复分区操作，知道各区间只有一个数为止。

　　算法流程：（递归+挖坑填数）

　　1）i=L，j=R，将基准数挖出形成第一个坑a[i]；

　　2）j--由后向前找出比它小的数，找到后挖出此数a[j]填到前一个坑a[i]中；

　　3）i++从前向后找出比它大的数，找到后也挖出此数填到前一个坑a[j]中；

　　4）再重复2,3），直到i=j，将基准数填到a[i]。

　　时间复杂度：O(nlog(n))，但若初始数列基本有序时，快排序反而退化为冒泡排序。

　　快速排序的示例：

　　（a）一趟排序的过程：

　　（b）排序的全过程

//快速排序
void QuickSort(int a[], int L, int R)
{
    if(L<R)
    {
        int i=L, j=R, temp=a[i];
        while(i<j)
        {
            //从右向左找小于基准值a[i]的元素
            while(i<j && a[j]>=temp)
                j--;
            if(i<j)
                a[i++]=a[j];
            //从左向右找大于基准值a[i]的元素
            while(i<j && a[i]<temp)
                i++;
            if(i<j)
                a[j--]=a[i];
        }
        //将基准值填入最后的坑中
        a[i]=temp;
        //递归调用，分治法的思想
        QuickSort(a, L, i-1);
        QuickSort(a, i+1, R);
    }
}

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define MAX_TOP 10000 /*一个很大的栈*/
#define NUM 500L
 
/*有关栈的数据结构*/
struct Region {
    long left;
    long right;
};
 
struct Stack {
    struct Region reg[MAX_TOP+1];
    long top;
};
 
/*对栈进行操作的函数*/
void init_stack(struct Stack *s);
void push_stack(struct Stack *s, struct Region r);
struct Region pop_stack(struct Stack *s);
int is_stack_empty(struct Stack *s);
 
/*与排序有关的函数*/
 
long partition(double a[], long left, long right);    
/*划分区间*/
void nr_qsort(double a[], long left, long right);
 
int main(void)
{
    double a[NUM];    
/*待排序数据*/
    clock_t t_s, t_e;
    long i;
 
    srand(time(NULL));
    for (i = 0; i < NUM; ++i)
        a[i] = rand() % 1000000;
 
    
/*统计运行时间*/
    t_s = clock();
    nr_qsort(a, 0, NUM-1);
    t_e = clock();
    double t = (t_e - t_s) / (double) CLOCKS_PER_SEC;
    printf("Non Recursive quick sort %ld items used time: %f s
", NUM, t);
 
    return 0;
}
 
/*implementation*/
 
void init_stack(struct Stack *s)
{
    s->top = -1;
}
 
void push_stack(struct Stack *s, struct Region r)
{
    if (s->top == MAX_TOP) {
        fprintf(stderr, "Stack overflow!
");
        exit(0);
    }
    s->reg[++s->top] = r;
}
 
struct Region pop_stack(struct Stack *s)
{
    if (s->top == -1) {
        fprintf(stderr, "Stack underflow!
");
        exit(0);
    }
    return (s->reg[s->top--]);
}
 
int is_stack_empty(struct Stack *s)
{
    return (s->top == -1);
}
 
/*返回划分的区间*/
long partition(double a[], long left, long right)
{
    double base = a[left];    
/*以最左边的元素作为比较基准*/
 
    while (left < right) {
        while (left < right && a[right] > base)
            --right;
        a[left] = a[right];
        while (left <right && a[left] < base)
            ++left;
        a[right] = a[left];
    }
    a[left] = base;
    return    left; 
}
 
void nr_qsort(double a[], long left, long right)
{
    struct Stack s;
    struct Region region, regionlow, regionhi;
    long p; 
/*记录划分出的分界点*/
 
    init_stack(&s);
    region.left = left;
    region.right = right;
    push_stack(&s, region);
 
    while (!is_stack_empty(&s)) {
        region = pop_stack(&s);
        p = partition(a, region.left, region.right);
        if (p-1 > region.left) {
            regionlow.left = region.left;
            regionlow.right = p - 1;
            push_stack(&s, regionlow);
        }
        if (region.right > p + 1) {
            regionhi.left = p + 1;
            regionhi.right = region.right;
            push_stack(&s, regionhi);
        }
    }
 
}