学习思路

排序是算法里面经常会考的题目，也是面试题里面会出的经典问题，虽然各种语言本身就内置了sort()排序函数，但是掌握其它的排序算法可以让我们在处理数据上显得游刃有余，同时一些排序算法里面的思想也与数据结构里面的算法思想不谋而合，所以排序算法是每个合格的程序员都必须掌握的。

排序算法练习题目

排序算法的分类：

1、冒泡排序:

#include <iostream>
using namespace std;
const int N = 1e8 + 10;
int a[N], n;
void bubble_sort()
{
    for (int i = n - 1; i >= 1; i--)
    {
        bool flag = true;
        for (int j = 1; j <= i; j++)
        {
            if (a[j - 1] > a[j])
            {
                swap(a[j - 1], a[j]); //交换两个数

                flag = false;
            }
        }

        if (flag)
        {
            return;
        }
    }
}
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
    {
        scanf("%d", &a[i]); //接收输入的数据
    }

    bubble_sort(); //调用函数排序

    for (int i = 0; i < n; ++i)
    {
        printf("%d ", a[i]); //输出
    }
    return 0;
}

2、选择排序:

#include <iostream>
using namespace std;
const int N = 1e8 + 10;
int a[N], n;
void select_sort()
{
    for (int i = 0; i < n; i++)
    {
        int k = i;
        for (int j = i + 1; j < n; j++)
        {
            if (a[j] < a[k])
            {
                k = j;
            }
        }
        swap(a[i], a[k]); //交换两个数
    }
}
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
    {
        scanf("%d", &a[i]); //接收输入的数据
    }

    select_sort(); //调用函数排序

    for (int i = 0; i < n; ++i)
    {
        printf("%d ", a[i]); //输出
    }
    return 0;
}

3、插入排序:

#include <iostream>
using namespace std;
const int N = 1e8 + 10;
int a[N], n;
void insert_sort()
{
    for (int i = 1; i < n; i++)
    {
        int x = a[i];
        int j = i - 1;

        while (j >= 0 && x < a[j])
        {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = x;
    }
}
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
    {
        scanf("%d", &a[i]); //接收输入的数据
    }

    insert_sort(); //调用函数排序

    for (int i = 0; i < n; ++i)
    {
        printf("%d ", a[i]); //输出
    }
    return 0;
}

4、希尔排序:

#include <iostream>
using namespace std;
const int N = 1e8 + 10;
int a[N], n;
void shell_sort()
{
    for (int gap = n >> 1; gap; gap >>= 1)
    {
        for (int i = gap; i < n; i++)
        {
            int x = a[i];
            int j;
            for (j = i; j >= gap && a[j - gap] > x; j -= gap)
            {
                a[j] = a[j - gap];
            }
            a[j] = x;
        }
    }
}
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
    {
        scanf("%d", &a[i]); //接收输入的数据
    }

    shell_sort(); //调用函数排序

    for (int i = 0; i < n; ++i)
    {
        printf("%d ", a[i]); //输出
    }
    return 0;
}

5、归并排序:

#include <iostream>
using namespace std;
const int N = 1e8 + 10;
int a[N], n;
int temp[N]; //开辟一个临时数组将原数组比较完的数储存
void merge_sort(int l, int r)
{
    if (l >= r)
    {
        return; //区间内只有一个数，返回
    }
    int mid = l + r >> 1;   //相当于(l + r) / 2
    merge_sort(l, mid);     //递归左半部分
    merge_sort(mid + 1, r); //递归右半部分
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r) //合并
    {
        if (a[i] < a[j])
        {
            temp[k++] = a[i++];
        }
        else
        {
            temp[k++] = a[j++];
        }
    }
    while (i <= mid)
    {
        temp[k++] = a[i++];
    }
    while (j <= r)
    {
        temp[k++] = a[j++];
    }

    for (int i = l, j = 0; i <= r; i++, j++)
    {
        a[i] = temp[j]; //将排序好的数转移回原数组
    }
}
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
    {
        scanf("%d", &a[i]); //接收输入的数据
    }

    merge_sort(0, n - 1); //调用函数排序

    for (int i = 0; i < n; ++i)
    {
        printf("%d ", a[i]); //输出
    }
    return 0;
}

6、快速排序（最快）:

#include <iostream>
using namespace std;
const int N = 1e8 + 10;
int a[N], n;
void quick_sort(int l, int r)
{
    if (l >= r)
    {
        return;
    }

    int x = a[l + r >> 1], i = l - 1, j = r + 1;
    while (i < j)
    {
        do
        {
            ++i;
        } while (a[i] < x);
        do
        {
            --j;
        } while (a[j] > x);

        if (i < j)
        {
            swap(a[i], a[j]); //交换两个数
        }
    }
    quick_sort(l, j);     //递归左半部分
    quick_sort(j + 1, r); //递归右半部分
}
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
    {
        scanf("%d", &a[i]); //接收输入的数据
    }

    quick_sort(0, n - 1); //调用函数排序

    for (int i = 0; i < n; ++i)
    {
        printf("%d ", a[i]); //输出
    }
    return 0;
}

7、堆排序（须知此排序使用了模拟堆，为了使最后一个非叶子节点的编号为n/2，数组编号从1开始）:

#include <iostream>
using namespace std;
const int N = 1e8 + 10;
int h[N], n;
void down(int u)
{
    int t = u; // t记录最小值
    if (u << 1 <= n && h[u << 1] < h[t])
    {
        t = u << 1; // 左儿子
    }
    if ((u << 1 | 1) <= n && h[u << 1 | 1] < h[t])
    {
        t = u << 1 | 1; // 右儿子
    }
    if (u != t) //需要调整
    {
        swap(h[u], h[t]); //交换两个数
        down(t);          //递归
    }
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &h[i]); //接收输入的数据
    }
    for (int i = n / 2; i; i--)
    {
        down(i); //初始化堆
    }
    while (true)
    {
        if (!n)
        {
            break;
        }
        printf("%d ", h[1]); //输出
        h[1] = h[n];
        n--;
        down(1);
    }
    return 0;
}

堆排序2.0（利用C++内置STL函数优先队列实现）:

//感慨万千：STL太好用了！
#include <iostream>
#include <queue>
using namespace std;
const int MAXN = 1e8 + 10;
int n;
priority_queue<int, vector<int>, greater<int>> q; //小根堆
int main()
{
    scanf("%d", &n);
    int x;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &x); //接收输入的数据
        q.push(x);       //入队
    }
    while (!q.empty()) //判断队列是否为空
    {
        printf("%d ", q.top()); //输出队顶的最小值
        q.pop();                //出队
    }
    return 0;
}

8、计数排序:

#include <iostream>
using namespace std;
const int N = 1e8 + 10;
long long n, cnt[N];
int main()
{
    scanf("%lld", &n);
    int x = 0, Max = -0x3f3f3f, Min = 0x3f3f3f; //初始化最大值和最小值
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &x);
        cnt[x]++; //统计
        Max = max(Max, x);
        Min = min(Min, x); //更新最大值和最小值
    }
    for (int i = Min; i <= Max; i++)
    {
        while (cnt[i])
        {
            cnt[i]--;
            printf("%d ", i); //输出
        }
    }
    return 0;
}

9、桶排序:

#include <iostream>
#include <vector>
using namespace std;
const int N = 1e8 + 10;
int n, Min = N, Max = 0, sum[N];
bool f[45];
vector<int> bucket[45]; //定义桶，这里定义40个桶
void insertsort(int s)
{
    for (int i = 0; i < bucket[s].size(); i++)
    {
        for (int j = i; j >= 1; j--)
        {
            if (bucket[s][j - 1] > bucket[s][j])
            {
                swap(bucket[s][j], bucket[s][j - 1]); //这里是从小到大排序
            }
        }
    }
    for (int i = 0; i < bucket[s].size(); i++)
    {
        printf("%d ", bucket[s][i]); //由于每个桶都是有序的，所以可以输出这个桶，节省了一次遍历的时间
    }
}
void bucketsort()
{
    for (int i = 1; i <= n; i++)
    {
        bucket[int((sum[i] - Min) / ((Max - Min + 1) / 40.0))].push_back(sum[i]);
        f[int((sum[i] - Min) / ((Max - Min + 1) / 40.0))] = 1; //运用最大最小值来合理分配桶
    }
    for (int i = 0; i <= 40; i++)
    {
        if (f[i])
        {
            insertsort(i); //如果当前桶有数值，则对桶内的数进行排序（这里用选择排序）
        }
    }
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &sum[i]);
        Min = min(Min, sum[i]);
        Max = max(Max, sum[i]); //为了能够合理利用空间，确保第一个桶和最后一个桶都有数，所以存储最大最小值
    }
    bucketsort();
    return 0;
}

10、基数排序（基数排序是桶排序的特例，优势是可以处理浮点数和负数，劣势是还要配合别的排序函数）:

#include <iostream>
using namespace std;
const int N = 1e8 + 10;
int a[N], count[N], temp[N], n;
int maxbit()
{
    int maxv = a[0]; // maxv保存最大的位数
    for (int i = 1; i < n; i++)
    {
        if (maxv < a[i])
        {
            maxv = a[i];
        }
    }
    int cnt = 1;
    while (maxv >= 10)
    {
        maxv /= 10;
        cnt++;
    }

    return cnt;
}
void radixsort() //基数排序
{
    int t = maxbit();
    int radix = 1;

    for (int i = 1; i <= t; i++) //进行t次排序
    {
        for (int j = 0; j < 10; j++)
        {
            count[j] = 0; //清空计数器
        }
        for (int j = 0; j < n; j++)
        {
            int k = (a[j] / radix) % 10;
            count[k]++;
        }
        for (int j = 1; j < 10; j++)
        {
            count[j] += count[j - 1];
        }
        for (int j = n - 1; j >= 0; j--)
        {
            int k = (a[j] / radix) % 10;
            temp[count[k] - 1] = a[j];
            count[k]--;
        }
        for (int j = 0; j < n; j++)
        {
            a[j] = temp[j];
        }
        radix *= 10;
    }
}
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
    {
        scanf("%d", &a[i]); //接收输入的数据
    }

    radixsort(); //调用函数排序

    for (int i = 0; i < n; ++i)
    {
        printf("%d ", a[i]); //输出
    }
    return 0;
}