超全经典排序大汇总

算法思想

在待排序表 a[0...n-1]中任取一个元素pivot作为枢轴（或基准，通常取首元素）,通过一趟排序将待排序表划分为独立的两个部分a[0...k-1]和a[k + 1 ...n-1]，使得a[0...k-1]中的所有元素均小于pivot,a[k + 1...n - 1]中所有元素均大于等于pivot,则pivot放在其最终的位置a[k]上,这一过程成为一次“划分”，然后分别递归地对两个子表重复上述过程，直到每一部分内只有一个元素或空为止，即所有元素放在了其最终的位置上。

时间复杂度

1. 最好 — $O（nlogn）$ 序列均匀分割
2. 最坏 — $O(n^2)$ 序列有序
3. 平均 — $O（nlogn）$

演示动画

空间复杂度

1. 最好 — $O（nlogn）$ 序列均匀分割
2. 最坏 — $O(n)$ 序列有序

稳定性

不稳定

适用性

仅适用于顺序表

算法特点

1. 当n较大时，在平均情况下快速排序是所有内部排序方法中速度最快的一种，所以其适合初始记录无序、n较大时的情况
2. 记录非顺次的移动导致排序方法是不稳定的
3. 排序过程中需要定位表的上界和下界，所以仅适合于顺序结构，很难适用于链式结构

核心代码

//划分函数,选取枢轴元素,且定位数轴元素下标 
int Partion(int a[], int low, int high){
    int pivot = a[low];//选取第一个元素作为枢轴,当然也可以选最后一个元素作为枢轴
    while(low < high){//在low和high之间搜索枢轴位置 
        while(low < high && pivot <= a[high]) high --;
        a[low] = a[high];//比枢轴小的移动到左端 
        while(low < high && a[low] <= pivot) low ++;
        a[high] = a[low];//比枢轴大的移动到右端 
    }
    a[low] = pivot;//将枢轴存放到最终位置 
    return low;//返回存放枢轴的最终的位置 
} 

//快速排序 
void QuickSort(int a[], int low, int high){
    if(low < high){//递归跳出条件 
        int pivotpos = Partion(a, low, high);//划分 
        QuickSort(a, low, pivotpos - 1);//划分左子表 
        QuickSort(a, pivotpos + 1, high);//划分右子表 
    }
}

精简代码

void quick_sort(int q[], int l, int r)
{
    if(l >= r)   return;
    int x = q[l + r >> 1], i = l - 1, j = r + 1;
    while(i < j)
    {
        do i++; while(q[i] < x);
        do j--; while(q[j] > x);
        if(i < j)   swap(q[i], q[j]);
    }
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

注：

此乃y总毕生锤炼之精华，全网最简，没有之一，哈哈....

完整代码

#include <iostream> 
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <fstream>

using namespace std;
const int N = 20;

int num;
int data[N],idx;

//划分函数,选取枢轴元素,且定位数轴元素下标 
int Partion(int a[], int low, int high){
    int pivot = a[low];//选取第一个元素作为枢轴 
    while(low < high){//在low和high之间搜索枢轴位置 
        while(low < high && pivot <= a[high]) high --;
        a[low] = a[high];//比枢轴小的移动到左端 
        while(low < high && a[low] <= pivot) low ++;
        a[high] = a[low];//比枢轴大的移动到右端 
    }
    a[low] = pivot;//将枢轴存放到最终位置 
    return low;//返回存放枢轴的最终的位置 
} 

//快速排序 
void QuickSort(int a[], int low, int high){
    if(low < high){//递归跳出条件 
        int pivotpos = Partion(a, low, high);//划分 
        QuickSort(a, low, pivotpos - 1);//划分左子表 
        QuickSort(a, pivotpos + 1, high);//划分右子表 
    }
}

int main(){
    //打开文件 
    ifstream infile;
    infile.open("D:\\学习\\数据结构\\第8章排序\\in.txt", ios::in);

    //写文件 
    ofstream outfile;
    outfile.open("D:\\学习\\数据结构\\第8章排序\\out.txt", ios::out);

    if(!infile.is_open()){//判断文件打开是否成功 
        cout << "file open failure!" << endl;
    }

    infile >> num;//读取元素个数 
    while(num --){//将文件中的元素复制到data[1...n] 数组中
        infile >> data[idx ++];
    }

    cout << "排序前元素序列：" << endl;
    for(int i = 0; i < idx; i ++) cout << data[i] << ' '; cout << endl;

    cout << "使用sort函数排序后序列: " << endl;
    sort(data, data + idx); 
    for(int i = 0; i < idx; i ++) cout << data[i] << ' '; cout << endl;

    QuickSort(data, 0, idx - 1);
    cout << "使用快速排序后序列为：" << endl;
    for(int i = 0; i < idx; i ++) cout << data[i] << ' '; cout << endl;

    num = idx, idx = 0, outfile << num << endl;//写入数据数num以及在行末写入\n 
    while(num --){
        outfile << data[++ idx] << ' ';//将排序后的数据写到文件中 
    }
    outfile << endl;//向文件末尾写入\n结束符 

    //关闭文件 
    infile.close();
    outfile.close();
    return 0;
}

输入数据(in.txt)

10
13 69 86 99 59 23 64 32 86 72

输出数据(out.txt)

10
13 23 32 59 64 69 72 86 86 99