C/C++实现快速排序(两种方式)图文详解

什么是快速排序

快速排序是一种基于分治策略的排序算法，由C.A.R.Hoare在1962年发明。快速排序的基本思路是：在待排序序列中选择一个元素作为“基准”（pivot），将序列分成两个部分，所有比“基准”小的元素放在一边，所有比“基准”大的元素放在另一边。如此递归下去直到序列有序。

算法流程

快速排序的流程可以简要描述为：

1. 从待排序数组中选择一个基准元素（通常选择第一个元素）。

2. 将所有小于基准元素的元素放在左边，所有大于基准元素的元素放在右边。

3. 对于左右两个子数组递归执行步骤1、2，直到所有子数组有序。

代码实现

实现思路

快速排序的实现思路主要有以下两种：

• 首先采用简单的实现方法，对基准元素左右两边的序列应用递归完成排序。针对这种实现方法，我们采用C++编程语言实现。其代码如下：

    void quicksort(int arr[], int left, int right)
    {
        if(left > right)
            return;
        int i = left, j = right, pivot = arr[left];
        while(i < j)
        {
            while(i < j && arr[j] >= pivot)
                j--;
            if(i < j)
                arr[i++] = arr[j];
            while(i < j && arr[i] < pivot)
                i++;
            if(i < j)
                arr[j--] = arr[i];
        }
        arr[i] = pivot;
        quicksort(arr, left, i - 1);
        quicksort(arr, i + 1, right);
    }

• 另外一种方法是采用C语言的实现方式。该实现方式相对于第一种方法非常基础并且难点也不大。其代码如下：

    void QuickSort(int *a, int left, int right)
    {
        if (left >= right) return;
        int i = left, j = right, pivot = a[left];
        while (i < j) {
            while (i < j && a[j] >= pivot) --j; 
            a[i] = a[j];
            while (i < j && a[i] <= pivot) ++i;
            a[j] = a[i];
        }
        a[i] = pivot;
        QuickSort(a, left, i - 1);
        QuickSort(a, i + 1, right);
    }

示例说明

我们来看下两组基础的使用示例。

示例一：

    int main()
    {
        int arr[] = {10, 7, 8, 9, 1, 5};
        int n = sizeof(arr)/sizeof(arr[0]);
        quicksort(arr, 0, n - 1);
        for(int i = 0; i < n; i++)
            cout << arr[i] << " ";
        return 0; 
    }

运行结果：

1 5 7 8 9 10

示例二（采用第二种代码实现方式）：

    #include <stdio.h>
    int main()
    {
        int arr[] = {10, 7, 8, 9, 1, 5};
        int n = sizeof(arr)/sizeof(arr[0]);
        QuickSort(arr, 0, n - 1);
        for(int i = 0; i < n; i++)
            printf("%d ", arr[i]);
        return 0; 
    }

运行结果：

1 5 7 8 9 10

总结

快速排序是一种非常高效、经典的排序算法，并且有着广泛的应用场景。快速排序算法核心思路非常简单，代码实现也相对较为简单。当然在实践过程中还涉及到很多的优化技巧，例如三数取中等，都可以很大程度上提升算法效率，欢迎大家自行实践。