【数据结构与算法】【排序】快速排序的代码实现

妖狐艹你老母 2022-08-13 14:53 225阅读 0赞

快速排序是一种交换排序，它是排序算法的王者。

前提：数组元素a\[0\]用作哨兵或临时变量，a\[1\]~a\[n\]存放n个待排序的元素。

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

快速排序优化方法：

1、优化选取枢轴；

2、优化不必要的交换；

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

4、优化递归操作（采用尾递归方案）。

代码实现：

// Filename: quick_sort.c
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <stdbool.h>
    #include "public.h"
    
    // 选取枢轴，并将比枢轴小的记录排在枢轴左边，比枢轴记录大的记录排在枢轴右边
    int Partition(int a[], int low, int high)
    {
        int pivotkey;
    
        pivotkey = a[low];
        while (low < high)
        {
            while (low < high && a[high] >= pivotkey) high--;
            swap(&a[low], &a[high]);
            while (low < high && a[low] <= pivotkey) low++;
            swap(&a[low], &a[high]);
        }
        //printf("pivotkey: %d, low: %d.\n", pivotkey, low);
        return low;
    }
    
    // 快速排序（交换排序升级版）
    // n个元素序列的各元素下标：[1, 2, ..., n-1, n], a[0]作为临时变量
    // 入参low和high是待排序元素在数组中的下标
    void QuickSort(int a[], int low, int high)
    {
        int pivot;
        if (low < high)
        {
            pivot = Partition(a, low, high);
            QuickSort(a, low, pivot - 1);
            QuickSort(a, pivot + 1, high);
        }
        return;
    }
    
    // 快速排序优化算法：
    // 1、优化选取枢轴（如：三数取中、九数取中）
    // 2、优化不必要的交换
    int Partition1(int a[], int low, int high)
    {
        int pivotkey;
        int mid = (low + high) / 2;
    
        // 优化点1: 使用三数取中法确定枢轴a[low]
        if (a[low] > a[high]) swap(&a[low], &a[high]);
        if (a[mid] > a[high]) swap(&a[mid], &a[high]);
        if (a[mid] > a[low])  swap(&a[mid], &a[low]);
    
        pivotkey = a[low];
        while (low < high)
        {
            while (low < high && a[high] >= pivotkey) high--;
            a[low] = a[high];   // 优化点2: 优化不必要的交换
            while (low < high && a[low] <= pivotkey) low++;
            a[high] = a[low];
        }
        a[low] = pivotkey;
        return low;
    }
    
    // 快速排序优化算法：
    // 3、优化小数组时的排序方案
    // 4、优化递归操作：尾递归优化
    void InsertSort(int a[], int n);
    #define MAX_LENGTH_INSERT_SORT  7   // 数组长度阈值
    void QuickSort1(int a[], int low, int high)
    {
        int pivot;
        if (high - low > MAX_LENGTH_INSERT_SORT)
        {
            while (low < high)
            {
                pivot = Partition1(a, low, high);
                QuickSort1(a, low, pivot - 1);
                low = pivot + 1;
            }
        }
        else
        {
            InsertSort(&a[low - 1], high - low + 1);
        }
        return;
    }
    
    
    // 快速排序主函数
    int QuickSortMain()
    {
        int a1[12] = {0xFF, 3, 4, 5, 8, 9, 7, 6, 1, 0, 2, -1};
    
        printf("快速排序演示(a[0]未使用，不参与排序): \n");
    
        printf("排序前：\n");
        printf("a1: ");
        PrintArray(a1, sizeof(a1) / sizeof(int));
        printf("\n");
    
        // 将从a1[1]到a1[10]共10个元素进行排序
        //QuickSort(a1, 1, 10);
        QuickSort1(a1, 1, 10);
    
        printf("排序后：\n");
        printf("a1: ");
        PrintArray(a1, sizeof(a1) / sizeof(int));
        printf("\n");
    
        return 0;
    }