排序之快速排序

一、数据结构
        约定排序均为升序排序，要排序的记录存储在线性表中，线性表由排序关键字和其它域组成，其定义如下：
        #define MAXITEM 100
        struct rec
        {
            KeyType key;        // 关键字域
            ElemType data;     // 其它数据域
        };
        struct rec sqlist[MAXITEM];
        这里的KeyType和ElemType可以是任何相应的数据类型，比如int，float或char等，在算法中，约定其为int类型。

二、算法思想
        快速排序是由冒泡排序改进而得的，它的基本思想是：在待排序的n个记录中任取一个记录（通常取第一个记录），把该记录放入最终位置后，数据序列被此记录分割成两部分。所有关键字比该记录关键字小的放置在前一部分，所有比它大的放置在后一部分，并把该记录排在这两部分的中间，这个过程称作一趟快速排序。之后对所有的两部分分别重复上述过程，直至每部分内只有一个记录为止。简而言之，每趟使表的第一个元素入终位，将表一分为二，对子表按递归方式继续这种划分，直至划分的子表长为1。
        一趟快速排序采用从两头向中间扫描的办法，同时交换与基准记录逆序的记录。具体作法是：设两个指示器i和j，它们的初值分别为指向无序区中第一个和最后一个记录。假设无序区中记录为r[s], r[s+1], ..., r[t]，则i的初值为s，j的初值为t，首先将r[s]移至变量r[0]中作为基准，令j自t起向左扫描直至r[j].key < r[0].key时，将r[j]移至i所指的位置上，然后令i自i+1起向右扫描直至r[i].key > r[0].key时，将r[i]移至j所指的位置上，依次重复直至i==j，此时所有r[k](k=s, s+1, ..., j-1)的关键字都小于r[0].key而所有r[k](k=j+1, j+2, ..., t)的关键字必大于r[0].key，则可将r[0]中的记录移至i所指位置r[i]，它将无序中记录分割成r[s, j-1]和r[j+1, t]，以便分别进行排序。

三、程序实现
        实现快速排序的函数如下：
        void fastsort(sqlist r, int s, int t)        // 把r[s]至r[t]的元素进行快速排序
        {
            int i=s, j=t;
            if (s < t)
            {
                r[0] = r[s];
                do
                {
                    while (j>i  && r[j].key>=r[0].key)   
                    {
                         j--;
                    }
                    if (i < j)
                    {
                         r[i] = r[j];
                         i++;
                    }
                    while (i                     {    
                         i++;
                    }
                    if (i < j)
                    {                               
                        r[j] = r[i];
                        j--;
                    }
                } while (i < j);
                r[i] = r[0];
                quicksort(r, s, j-1);
                quicksort(r, j+1, t);
            }
        }
        快速排序算法的时间复杂度是O(nlog₂n)，它是一种不稳定的排序方法。