内部排序之快速排序

         快速排序以前都写过N遍了，但现在再次写该排序时，也不知道该如何下手。
或许是算法很容易忘记，或许是当初根本就没有理解。但该算法整体的思想还是
清楚的。

个人感觉算法可以分几个层次去理解。仅仅是个人的感觉而已。
1，算法的本身。
     算法的本身不依赖具体的计算机语言，在逻辑上能够走通即可。
     可以用伪代码表达，也可以用自然语言表达。算法本身的提出
     就是一些搞研究的人弄的东西，比如说Knuth.这些人才是牛人。 
2，算法的实现。
     算法的实现就是根据人家提出的算法理论使用计算机语言运行
     成功。可以是C语言实现，可以是C++语言实现，也可以是JAVA
     语言。这些都是学生干的事。或者说是编写教材的人干的事。
3，算法的应用。
     这就是一些软件工程师干的事，根据软件的具体环境，还有人家
     提出算法理论写出解决某个问题的算法实现。这要求也挺高的，
     既要深刻地懂得算法的理论，还会写出高质量的代码。

所以我们写的toy program都是停留在第二个层次。我看了linux kernel里面
的排序，用的是堆排序，glibc中的快速排序源代码，人家写的快排和堆排和
我们写的快排和堆排有天然之别。但思想还是一样的。

而有些算法学习目前只能停留在第一个层次，比如说一些海量数据处理。什么桶排序
计数排序，还有一些别的算法思想。我们用我们的toy program很难将其算法思想实现。
-------------------------------------------------------------------------------------------------
一，快速排序的算法思想。（第一个层次）
 <1>，将数组根据区轴（一般是第一个元素）分为两部分。前部分小于区轴，后部分大于区轴。
 <2>，将数组前部分进行<1>，当数组前部分只剩下一个元素时算法结束。
 <3>，将数组后部分进行<1>，当数组后部分只剩下一个元素时算法结束。

算法步骤：
假设待排序的数组为r[left],f[left+1],r[left+2],...r[right]
现在设置两个指针i和j分别指向r[left]和f[right]。并设置区轴
x = a[left]。
(1)j从右向左扫描，如果r[j].key > x.key,则通过，直到遇到r[j] <= x.key后停止。
     然后，将a[j]赋值给a[i]。
(2)i从左向右扫描，如果r[i].key< x.key,则通过，知道遇到r[i] >= x.key后停止。
     然后，将a[i]赋值给a[j]。
(3)继续执行(1)(2)，知道i和j相遇为止。然后将a[i] = x。这样就可以保证，x前面
    的元素都小于x,x后面的元素都大于x.
(4)接着对数组r[left],r[left+1]...r[x-1]和数组r[x+1]...r[right]进行(1),(2),(3)，
     如果数组的个数为1的时候，算法结束。
------------------------------------------------------------------------------------------------
二，快速排序的实现。（第二个层次）
     将上面的快速排序“翻译”为C语言代码。

void my_qsort(int a[],int left,int right)
{
        int i = left;
        int j = right;
        int tmp = a[left];

        while (i < j) {
            while (i < j && a[j] >= tmp) j--;
            a[i] = a[j];
            while (i < j && a[i] < tmp) i++;
            a[j] = a[i];
        }
        a[i] = tmp;

        if (i-1 > left) my_qsort(a,left,i-1);
        if (i+1 < right) my_qsort(a,i+1,right);
        return ;
}

----------------------------------------------------------------------------------------------------------------
三，将该快速排序测试下。（黑盒法）
使用随机数生成的方法测试。测试了100个随机数生成的测试用例。均成功。

int main(void)
{
        int a[10] = {0};
        int n = 100,i;

     while (n--) {
        printf("\nbefore qsort:\n");
        for (i=0;i<10;i++) {
                a[i] = random() % 100;
                printf("%d ",a[i]);
        }
        putchar('\n');

        my_qsort(a,0,9);

        printf("after qsort:\n");
        for (i=0;i<10;i++) {
                printf("%d ",a[i]);
        }
        putchar('\n');
        }
    return 0;
}

------------------------------------------------------------------------------------------------
四，快速排序的性能分析。
       时间复杂度是O(nlog(n)).

-------------------------------------------------------------------------------------------------