基本思想:与归并排序一样,快速排序也采用了分治法。将原问题分解成几个规模较小但类似于原问题的子问题,递归地求解这些子问题,然后再合并这些子问题的解来建立原问题的解。在快速排序中,因为子数组都是原址排序的,所以不需要合并操作。


----------

排序算法:快速排序
时    间:2018年1月14日
时间复杂度:最好情形O(nlgn),平均情形O(nlgn),最差情形O(n^2)
空间复杂度:O(lgn)
稳  定  性:不稳定
by Ingran
----------
#include<iostream>
#include<time.h>
#include<iomanip>

void Swap(int A[], int i, int j)
{
    int temp = A[i];
    A[i] = A[j];
    A[j] = temp;
}

int Partition(int A[], int p, int r)//对子数组进行原址重排
{
    int x = A[r]; //储存数组最后一个元素最为“主元”
    int i = p - 1;

    for (int j = p; j < r; j++)
    {
        if (A[j] <= x)
        {
            i = i + 1;
            Swap(A, i, j);//把小于主元的数值放在左边
        }
    }
    Swap(A, i + 1, r);//把r放在相对于(左边是比r小的,右边是比r大的)中间的位置
    return i + 1;//返回当前主元位置的下标
}


void Quick_Sort(int A[], int p, int r)//快速排序,参数为数组A,数组A的首元素下标和最后一个元素的下标
{
    int q = 0;
    if (p < r)
    {
        q = Partition(A, p, r);
        Quick_Sort(A, p, q - 1);
        Quick_Sort(A, q + 1, r);
    }
}


int main()
{
    int *p = nullptr;
    int n = 0;
    srand((unsigned)time(NULL));
    std::cout << "请输入随机数个数:" << std::endl;
    std::cin >> n;
    p = new int[n];

    std::cout << "排序前:" << std::endl;
    for (int i = 0; i < n; i++)
    {
        p[i] = rand() % 101;
        std::cout << std::setw(3) << p[i] << "  ";
        if (i % 10 == 9)
            std::cout << std::endl;
    }

    Quick_Sort(p, 0, n - 1);
    std::cout << std::endl << "排序后:" << std::endl;
    for (int i = 0; i < n; i++)
    {
        std::cout << std::setw(3) << p[i] << "  ";
        if (i % 10 == 9)
            std::cout << std::endl;
    }

    system("pause");
    return 0;
}