数据结构与算法-快速排序

ゝ一纸荒年。 2022-05-29 09:46 212阅读 0赞

设要排序的数组是A\[0\]……A\[N-1\]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。

在c++中可以用函数qsort（）可以直接为数组进行排序。  
用 法:  
void qsort(void *base, int nelem, int width, int (\*fcmp)(const void* ,const void \*));  
参数：  
　　1 待排序数组首地址  
　　2 数组中待排序元素数量  
　　3 各元素的占用空间大小  
　　4 指向函数的指针，用于确定排序的顺序

C++语言实现：

void Qsort(int a[], int low, int high)
    {
        if(low >= high)
        {
            return;
        }
        int first = low;
        int last = high;
        int key = a[first]; /*用字表的第一个记录作为枢轴*/
        while(first < last){
            while(first < last && a[last] >= key){
                --last;
            }
            a[first] = a[last]; /*将比第一个小的移到低端*/
            while(first < last && a[first] <= key){
                ++first;
            }
            a[last] = a[first]; /*将比第一个大的移到高端*/
        }
        a[first] = key; /*枢轴记录到位*/
        Qsort(a, low, first-1);
        Qsort(a, first+1, high);
    }

全部程序：

#include <iostream>
    using namespace std;
    void Qsort(int a[], int low, int high)
    {
        if(low >= high)
        {
            return;
        }
        int first = low;
        int last = high;
        int key = a[first]; /*用字表的第一个记录作为枢轴*/
        while(first < last){
            while(first < last && a[last] >= key){
                --last;
            }
            a[first] = a[last]; /*将比第一个小的移到低端*/
            while(first < last && a[first] <= key){
                ++first;
            }
            a[last] = a[first]; /*将比第一个大的移到高端*/
        }
        a[first] = key; /*枢轴记录到位*/
        Qsort(a, low, first-1);
        Qsort(a, first+1, high);
    }
    
    int main()
    {
        int a[] = {
       57, 68, 59, 52, 72, 28, 96, 33, 24};
        Qsort(a, 0, sizeof(a) / sizeof(a[0]) - 1);/*这里原文第三个参数要减1否则内存越界*/
        for(int i = 0; i < sizeof(a) / sizeof(a[0]); i++){
            cout << a[i] << " ";
        }
        cout<< endl;
        return 0;
    }/*参考数据结构p274(清华大学出版社，严蔚敏)*/