[数据结构与算法]考研-排序算法

六、排序

大纲

六、排序
　　(一)排序的基本概念 (二)插入排序
　　1.直接插入排序
　　2.折半插入排序 (三)气泡排序(bubble sort) (四)简单选择排序 (五)希尔排序(shell sort)
　　(六)快速排序 (七)堆排序
　　(八)二路归并排序(merge sort) (九)基数排序
　　(十)外部排序 (十一)排序算法的分析与应用

分类及稳定性分析

根据是否在内存中进行分类·分为 ： 内排序与外排序

内排序分为需要关键字比较的排序(插排、选择、交换、归并)和 不需要的(基数排序)

总体上分为(这里就按升序写了) ：

代码

【模板】快速排序

题目描述

利用快速排序算法将读入的 $N$ 个数从小到大排序后输出。

快速排序是信息学竞赛的必备算法之一。对于快速排序不是很了解的同学可以自行上网查询相关资料，掌握后独立完成。（C++ 选手请不要试图使用 STL，虽然你可以使用 sort 一遍过，但是你并没有掌握快速排序算法的精髓。）

输入格式

第 $1$ 行为一个正整数 $N$，第 $2$ 行包含 $N$ 个空格隔开的正整数 $a_i$，为你需要进行排序的数，数据保证了 $A_i$ 不超过 $10^9$。

输出格式

将给定的 $N$ 个数从小到大输出，数之间空格隔开，行末换行且无空格。

样例 #1

样例输入 #1

5
4 2 4 5 1

样例输出 #1

1 2 4 4 5

提示

对于 $20\%$ 的数据，有 $N\le 10^3$；

对于 $100\%$ 的数据，有 $N\le 10^5$。

这道题用快排需要对基准选择优化才能满分，这里就用了一个最简单的优化算了，80分，毕竟just练习各大排序的模板

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int arr[N];
int tt[N];//归并排序的辅助数组
int n;

void quickSort(int nums[], int l, int r){
    if(l > r) return;
    int ll = l, rr = r;
    if(r - l >= 10){
        int x = rand() % (r - l + 1) + l;
        // int mid = ll + rr >> 1;
        int mid = x;
        swap(nums[ll], nums[mid]);
    }
    int t = nums[ll];
    while(ll < rr){
        while(ll < rr && nums[rr] >= t) rr --;
        while(ll < rr && nums[ll] <= t) ll ++;
        if(ll < rr) swap(nums[ll], nums[rr]);
    }
    swap(nums[l], nums[ll]);
    quickSort(nums, l, ll - 1);
    quickSort(nums, ll + 1, r);
}

void mergeSort(int nn[], int l, int r){
    if(l >= r) return;
    int mid = l + r >> 1;
    mergeSort(nn, l, mid);
    mergeSort(nn, mid + 1, r);
    int l1 = l, l2 = mid + 1, ind = l;
    while(l1 <= mid && l2 <= r){
        if(n[l1] <= nn[l2])
            tt[ind ++] = nn[l1 ++];
        else
            tt[ind ++] = nn[l2 ++];
    }
    while(l1 <= mid) tt[ind ++] = nn[l1 ++];
    while(l2 <= r) tt[ind ++] = nn[l2 ++];
    for(int i = l; i <= r; i ++)
        nn[i] = tt[i];
}

void sift(int a[], int l, int r){
    int i = l, j = 2 * i + 1;
    while(j <= r){
        int big;
        if(j + 1 <= r) big = a[j] >= a[j + 1] ? j : j + 1;
        else big = j;
        if(a[i] < a[big]){
            swap(a[i], a[big]);
            i = big, j = 2 * i + 1;
        }else return;
    }
}

void heapSort(int a[], int l, int r){
	//初始化建堆
    for(int i = r / 2; i >= 0; i --)
        sift(a, i, r);  
    for(int i = r; i >= 1; ){
        swap(a[0], a[i --]);
        sift(a, 0, i);
    }
}

int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++)
        scanf("%d", arr + i);
    heapSort(arr, 0, n - 1);
    for(int i = 0; i < n; i ++)
        printf("%d ", arr[i]);
    puts("");
    return 0;
}

开发者涨薪指南

48位大咖的思考法则、工作方式、逻辑体系