数据结构快速排序（用C语言实现）

拼搏现实的明天。 2022-06-06 06:37 207阅读 0赞

## Ⅰ ）算法思想 ##

快速排序是一位英国的计算机学家Hoare在1962年提出， 其算法思想为：从待排序列中选取一个记录（通常选取第一个记录）为枢轴，其关键字设为K1，然后将其余关键字小于K1的记录移动K1前面，而将关键字大于K1的记录移动到后面，结果将待排序列分成两个子表，最后将关键字K1的记录插到其分界线的位置处。将这个过程称为一趟快速排序。通过一次划分后，就以关键字K1的记录为界，将待排序列分成了两个子表，且前面子表中所有记录的关键字均不大于K1，而后面子表中的所有记录的关键字均不小于K1。对于分割后的子表继续上述原则进行分割，直到所有子表的表长不超过1为止，此时待排序记录序列就变成了一个有序表。

## Ⅱ）源代码 ##

#include<stdio.h>
     
    typedef int KeyType;
    typedef struct
    {
        KeyType key;
    }RecordType;       
     
    int QKPass(RecordType r[], int left, int right) //一趟快速排序算法
    {
        int low = left;
        int high = right;
        r[0] = r[left];
        while (low < high)
        {
            while (low<high && r[high].key>r[0].key)       
            {
                high--;
            }
            if (low < high)
            {
                r[low] = r[high];
                low++;
            }
            while (low < high && r[low].key < r[0].key)
            {
                low++;
            }
            if (low < high)
            {
                r[high] = r[low];
                high--;
            }
        }
        r[low] = r[0];                     
        return low;               //返回基准记录的位置
    }
    void QKSort(RecordType r[], int low, int high)      //快速排序
    {
        if (low < high)
        {
            int pos = QKPass(r, low, high);         //调用一趟快速排序，以枢轴元素为界划分两个子区间
            QKSort(r, low, pos - 1);             //对左部子表进行快速排序
            QKSort(r, pos + 1, high);             //对右部子表进行快速排序
        }
    }
    void ShowResult(RecordType *r, int length)     //输出结果
    {
        for (int i = 1; i <= length; i++)
        {
            printf("%d\t", r[i]);
        }
        printf("\n");
    }
     
    int main(void)
    {
        RecordType r[] = {0, 4, 5, 1, 9, 6, 8, 0, 3, 7, 2 };
        int length = sizeof(r) / sizeof(r[0]) - 1;
        QKSort(r, 1, length);
        ShowResult(r, length);
        return 0;
    }

## Ⅲ）性能分析 ##

A)时间复杂度  
     最好情况（每次枢轴总是在中间）T(n)=O(nlog2n)  
     平均 T(n)=O(nlog2n)  
     最坏情况（数据已是递增或递减）T(n)=O(n²)

B)空间复杂度：需栈空间以实现递归  
    最坏情况：S(n)=O(n)  
    一般情况：S(n)=O(log2n)