使用算法在C ++中快速排序，示例

它是Tony Hoare爵士于1959年发明的。

在快速排序中，我们将数组分为两部分，对于这两个部分的所有可能索引，一个部分的所有元素都小于或等于另一部分的元素，如果我们重复对这些行进行排序，则整个数组将被排序。这些被称为分而治之的方法。

快速排序的描述

从一个分区a中选择一个随机的枢轴元素pi，使其小于pi的元素集合，等于pi的元素集合以及大于pi的元素集合，最后，对该分区中的第一和第三集合进行递归排序。

算法：

quickSort(array<T>& a)
{
    quickSort(a, 0, a.length);
    quickSort(array<T> & a, int i, int n)
    {
        if (n <= 1)
            return;
        T pi = a[i + rand() % n];
        int p = i - 1, j = i, q = i + n;
        while (j < q) {
            int comp = compare(a[j], pi);
            if (comp < 0) {
                a.swap(j++, ++p); //移到数组的开头
            }
            else if (comp > 0) {
                a.swap(j, --q); //移到数组末尾
            }
            else {
                j++; //保持在中间
            }
        }
    }
}
// a[i..p]<pi, a[p+1..q-1]=pi, a[q..i+n-1]>pi
quickSort(a, i, p - i + 1);
quickSort(a, q, n - (q - i));

考虑快速排序工作流程：

#include <iostream>使用命名空间std; void quicksort(int,int,int); int分区(int,int,int); int partition（int * a，int s，int e）{int piviot = a [e]; int pind = s; 诠释 for（i = s; i <e; i ++）{如果（a [i] <= piviot）{t = a [i]; a [i] = a [pind]; a [固定] = t; pind ++; t = a [e]; a [e] = a [pind]; a [固定] = t; 返回固定 } void quicksort（int * a，int s，int e）{如果（s <e）{int pind = partition(a,s,e); quicksort（a，s，固定-1）; quicksort（a，pind + 1，e）; }} intmain(){int n; cout <<“输入元素数量：”; cin >> n; int a [n]; cout <<“输入数组：”; for（int i = 0; i <n; i ++）{cin >> a [i]; } quicksort(a,0,n-1); cout <<“排序数组为：”; for（int i = 0; i <n; i ++）{cout << a [i] <<“”; }返回0; }

输出结果

RUN 1:
//输入元素数量： 5
//输入数组： 10 20 5 15 10
//排序数组是： 5 10 10 15 20

RUN 2:
//输入元素数量： 10
//输入数组： 40 30 20 50 60 70 80 90 10 11
//排序数组是： 10 11 20 30 40 50 60 70 80 90