题解 P1177 【【模板】快速排序】

Hardict · 2018-01-02 12:39:41 · 题解

我来搞事了 (=ﾟωﾟ)ﾉ

写了6种基本的排序，基本可以囊括所有排序思想了

• 快排与希尔(当然希尔还有种复杂版)是最好写的也是最好用的。快排可移植能力强，可以配合swap函数及自身完成转移下标等操作(不用struct的话)，另外快排是寻找第k大问题的好工具；希尔排序直接写在main函数中，短小精悍，但时间复杂度emmmm...

• 没写冒泡排序，个人认为其和插入排序结构差不多

• 选择排序有链表的思想，故在这提出

• 桶排序时间是极优的，但空间是个问题

• 归并排序是均衡了时间空间的排序，时间较快排好，但一般我不想写将其作为大轴子(￣▽￣")

• 堆排序未出现

优化

• 快排：可以两边同时进行

• 快排：可以设定排序长度（保证每个区间的最大值不大于下个区间的最小值），然后再用插入排序处理短序列

• 选择排序：也是2边同时进行，换为先排max和min，一趟循环就只用i/2（i=n,n-1,...,2,1)

• 别的优化欢迎补充

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <time.h>//我要搞事 (｀･ω･´)

#define max(A, B) ((A > B) ? A : B)
#define min(A, B) ((A < B) ? A : B)

void swap(int arr[], int i, int j);
void QuickSort(int arr[], int left, int right);
void ShellSort(int arr[], int left, int right);
void InsertSort(int arr[], int left, int right);
void BucketSort(int arr[], int left, int right);
void SelectSort(int arr[], int left, int right);
void Merge(int arr[], int left, int mid, int right);
void MergeSort(int arr[], int left, int right);

int main()
{
    int n;
    int *arr;
    int i;

    scanf("%d", &n);
    arr = (int*)malloc(sizeof(int) * (n + 1));
    for (i = 1; i <= n; i++)
        scanf("%d", arr + i);
    /*想测试人品吗？srand((unsigned)time(0));
    int temp = rand() % 6;   //骚一波 ≖‿≖✧ ps:拼人品，有可能过不了
    switch (temp) {
    case 0:
        QuickSort(arr, 1, n);
        break;
    case 1:
        ShellSort(arr, 1, n);
        break;
    case 2:
        InsertSort(arr, 1, n);
        break;
    case 3:
        BucketSort(arr, 1, n);
        break;
    case 4:
        SelectSort(arr, 1, n);
        break;
    case 5:
        MergeSort(arr, 1, n);
        break;
    default:
        printf("error: rand()? or mod Σ( ° △ °|||)︴\n");
        break;
    }*/
    MergeSort(arr, 1, n);
    for (i = 1; i <= n; i++)
        printf("%d ", arr[i]);
    return 0;
}

void swap(int arr[], int i, int j)
{
    int temp;

    temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

void QuickSort(int arr[], int left, int right)
{
    int i, pivot;

    if (left >= right)
        return;
    pivot = left;
    swap(arr, left, (left + right) / 2);
    for (i = left + 1; i <= right; i++) //单边搜索，可以该为双向搜索（据说快点( ° ▽、° )）
        if (arr[i] < arr[left])
            swap(arr, i, ++pivot);
    swap(arr, left, pivot);
    QuickSort(arr, left, pivot - 1);
    QuickSort(arr, pivot + 1, right);
}

void ShellSort(int arr[], int left, int right)
{
    int gap, i, j;

//ShellSort因为我只写过0——n-1的(最标准的)，可能有点小bug（不过应该没错吧 (*´Д｀*) )
    for (gap = (left + right) / 2; gap > 0; gap /= 2)
        for (i = gap; i <= right; i++)
            for (j = i - gap; j > 0 && arr[j] > arr[j + gap]; j -= gap)
                swap(arr, j, j + gap);
}

void InsertSort(int arr[], int left, int right)
{
    int i, v;

    for (i = left; i <= right; i++) {
        v = arr[i];
        int l = left, r = i;
        int j;
        while (l < r) {//在l与r之间插入排序，可以理解为解决子问题1→2→...→n
            int mid = (l + r) / 2;
            if (arr[mid] <= v)
                l = mid + 1;
            else
                r = mid;
        }
        for (j = i - 1; l <= j; j--)
            arr[j + 1] = arr[j];
        arr[l] = v;
    }
}

void BucketSort(int arr[], int left, int right)
{
    int i, v;
    static int cnt[123456] = { 0 };

    for (i = left, v = 0; i <= right; i++) {
        v = max(v, arr[i]);//部分优化：统计最大值，不用遍历所有桶，但空间仍是个问题╮(╯▽╰)╭
        cnt[arr[i]]++;
    }
    v++;
    while (v-- > 0)
        while (cnt[v]-- > 0)
            arr[--i] = v;
}

void SelectSort(int arr[], int left, int right)
{
    int i, j, k;

    for (i = left; i <= right; i++) {
        for (j = k = i; j <= right; j++) //可以理解为对k进行选择，将k的指向第i-left小的
            if (arr[j] < arr[k])
                k = j;
        if (i < k)
            swap(arr, i, k);
    }
}

void Merge(int arr[], int left, int mid, int right)
{
    //merge arr[L,M](sorted) and arr(M,R](sorted) into arr[L,R]
    static int p = 1, que[123456] = { 0 };
    int pl = left, pr = mid;
    int ql = mid + 1, qr = right;

    while (pl <= pr || ql <= qr) {
        if ((ql > qr) || (pl <= pr && arr[pl] <= arr[ql])) //有点麻烦的判断，要考虑arr已提取完的情况
            que[p++] = arr[pl++];
        else
            que[p++] = arr[ql++];
    }
    while (left <= right)
        arr[right--] = que[--p];
}

void MergeSort(int arr[], int left, int right)
{
    if (left >= right)
        return;
    int mid = (left + right) / 2;
    MergeSort(arr, left, mid);
    MergeSort(arr, mid + 1, right);
    Merge(arr, left, mid, right);//二分递归
}