C++中的快速排序(使用vector和数组的不同)

1.快速排序是最最基本的排序算法之一,时间复杂度是O(nlog2(n))

基本思想:分治法+递归

假设key为该序列的第一个元素,从后往前遍历,找到第一个小于key值的元素,将该元素赋值给左边的起始值,再从前往后遍历,找到第一个大于key值的元素,将其赋值给刚才右边第一个小于key值的值,当low<high,则不断递归,知道有序为止.

在用数组int num[]和C++的vector传递地址时,vector需要传引用,否则,没法得到正确地址,因为vector本质上是一个类对象,因此传值会得不到正确结果,而数组会退化为指针,因此可以直接传值.

template<typename datatype>
void myquicksort(vector<datatype> &vec, int low, int high)//必须传引用,否则出错,因为vector是一个类对象
{
    if (low < high)
    {
        int l = low;
        int r = high;
        datatype key = vec[l];//记录key值

        while (l < r)
        {
            while (l < r&&key <= vec[r])//从右往左遍历,找到第一个小于key的元素
                --r;
            vec[l] = vec[r];
            while (l < r&&key >= vec[l])//从左往右遍历,找到第一个大于key值的元素
                ++l;
            vec[r] = vec[l];
        }
        vec[l] = key;//其实此时l=r

        myquicksort(vec, low, l-1);
        myquicksort(vec, r + 1, high);
    }
}
int main2()
{
    const int len = 30;//定义一个常量
    vector<int>data;//创建一个vector,存储int类型的元素
    for (int i = 0; i < len; i++)
    {
        data.push_back(rand() % 100);
        cout << (data.at(i)) << "\t";
        if ((i + 1) % 10 == 0)
            cout << endl;
    }

    clock_t start = clock();//使用clock函数需要包含头文件#include<ctime>
    myquicksort(data, 0, len - 1);
    clock_t end = clock();
    cout << "排序完成,总共用时:" << (end - start)*1.0 / CLOCKS_PER_SEC << endl;//#define CLOCKS_PER_SEC  1000
    for (int i = 0; i < len; i++)
    {
        cout << (data.at(i)) << "\t";
        if ((i + 1) % 10 == 0)
            cout << endl;
    }

    system("pause");
    return 0;
}

2.使用数组来传值:

void myquicksort2(int a[], int low, int high)//数组作为函数参数,没有副本机制,退化为指针
{
    if (low >= high)//递归终止条件
        return;
    else
    {
        int l = low, h = high;
        int key = a[l];
        while (l<h)
        {
            while (l < h&&a[h] >= key)
                --h;
            a[l] = a[h];
            while (l < h&&a[l] <= key)
                ++l;
            a[h] = a[l];
        }
        a[l] = key;
        myquicksort2(a, low, l - 1);
        myquicksort2(a, l + 1, high);
    }
}
int main()
{
    const int len = 30;
    int num[len];
    for (int i = 0; i < len; i++)
    {
        num[i] = rand() % 100;
        cout << num[i] << "\t";
        if ((i + 1) % 10 == 0)
            cout << endl;
    }
    clock_t t1 = clock();
    myquicksort2(num, 0, len - 1);
    clock_t t2 = clock();
    cout << "排序完成,总共用时:" << (t2 - t1)*1.0 / CLOCKS_PER_SEC << endl;
    for (int i = 0; i < len; i++)
    {
        cout << num[i] << "\t";
        if ((i + 1) % 10 == 0)
            cout << endl;
    }
    system("pause");
    return 0;
}