【大话数据结构C语言】70 快速排序

迈不过友情╰ 2022-10-15 05:00 154阅读 0赞

**目录**

背景

快速排序

复杂度

快速排序的优化

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

### **背景** ###

快速排序是图灵奖获得者 Tony Hoare设计提出的

快速排序被誉为20世纪十大算法之一

希尔排序是直接插入排序的升级，属于插入排序

堆排序是简单选择排序的升级，属于选择排序类

快速排序是冒泡排序的升级，属于交换排序类

快速排序是增加了记录的比较和移动的距离，将关键字较大的记录从前面直接移到后面，关键字较小的记录从后边直接移到前面，从而减少了比较次数和移动交换的次数

### **快速排序** ###

快排的基本思想是，通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分关键字小，则可以对这两部分记录继续进行排序，以达到整个序列有序的目的

![a18f73eddfeff75c242c63ea8ce55a0e.png][]

### **复杂度** ###

快排的时间复杂度：

在最优的情况下为nlogn

最坏的情况下为n方

平均情况：nlogn

空间复杂度：logn

**由于关键字的比较和交换是交换式的，因此，快排是一种不稳定的排序方法**

#include <stdio.h>
    
    void swap(int k[], int low, int high)
    {
        int temp;
    
        temp = k[low];
        k[low] = k[high];
        k[high] = temp;
    }
    
    int Partition(int k[], int low, int high)
    {
        int point;
    
        point = k[low];
    
        while( low < high )
        {
            while( low < high && k[high] >= point )
            {
                high--;
            }
            swap(k, low, high);
            
            while( low < high && k[low] <= point )
            {
                low++;
            }
            swap(k, low, high);
        }
    
        return low;
    }
    
    void QSort(int k[], int low, int high)
    {
        int point;
    
        if( low < high )
        {
            point = Partition(k, low, high);
    
            QSort(k, low, point-1);
    
            QSort(k, point+1, high);
        }
    }
    
    void QuickSort(int k[], int n)
    {
        QSort(k, 0, n-1);
    }
    
    int main()
    {
        int i, a[10] = {4, 2, 5, 0, 3, 9, 1, 7, 6, 8};
    
        QuickSort(a, 10);
    
        printf("排序后的结果是：");
        for( i=0; i < 10; i++ )
        {
            printf("%d", a[i]);
        }
        printf("\n\n");
    
        return 0;
    }

### **快速排序的优化** ###

1.优化选取基准点

2.优化不必要的交换

3.优化小数组时的排序方案

4.优化递归操作

[a18f73eddfeff75c242c63ea8ce55a0e.png]: /images/20221014/0870d39a3a514398bfee5a4bbd3cfa93.png