排序算法汇总（C++实现）

排序算法汇总（C++实现）

• 复杂度比较
• 1）冒泡排序
• 2）插入排序
• 3）选择排序
• 4）希尔排序
• 5）堆排序
• 6）归并排序
• 7）快速排序
• 8）基数排序

复杂度比较

算法	平均时间复杂度	最好情况	最坏情况	空间复杂度	稳定性
冒泡排序	O(N^2)	O(N^2)	O(N^2)	O(1)	稳定
插入排序	O(N^2)	O(N)	O(N^2)	O(1)	稳定
选择排序	O(N^2)	O(N^2)	O(N^2)	O(1)	不稳定
希尔排序			O(N^2)	O(1)	不稳定
堆排序	O(NlogN)	O(NlogN)	O(NlogN)	O(1)	不稳定
归并排序	O(NlogN)	O(NlogN)	O(NlogN)	O(N)	稳定
快速排序	O(NlogN)	O(NlogN)	O(N^2)	O(logN)	不稳定

稳定性：两个相同的元素排序前后的相对位置关系不会发生改变。
希尔排序：时间复杂度在O(Nlog2N)和O(N^2)之间，大致为O(N^1.3)。

---

1）冒泡排序

排序思想：
① 将第一个元素与第二个元素比较大小，如果第一个元素大于第二个元素则调换他们两的位置；
② 比较第二个元素和第三个元素的大小，如果第二个元素大于第三个元素则调换他们两的位置；
③ 依次类推，进行两两元素的比较和交换，最终最大的元素排在了最后面；
重复1到3过程，直到所有元素都排序。

动图演示：

效率分析：
从冒泡排序的算法可以看出，若待排序的元素为正序，则只需进行一趟排序，比较次数为（n-1）次，移动元素次数为0；若待排序的元素为逆序，则需进行n、1趟排序，比较次数为(n^2-n)/2，移动次数为3(n^2-n)/2.因此冒泡排序算法的时间复杂度为O(n^2)。是一种稳定的算法。

代码实现：

#include 
#include

using namespace std;

//冒泡排序
void bubblesort(vector<int>& a)
{
    int n = a.size();
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n - 1 - i; j++)
        {
            if (a[j] > a[j+1])
                swap(a[j], a[j+1]);
        }
    }
}


//冒泡排序优化
//用一个变量记录下最后一个发生交换的位置，后面没有发生交换的已经有序
//所以可以用这个值来作为下一次比较结束的位置
void bubblesort2(vector<int>& a)
{
    int n = a.size();
    int flag = n;
    int stop_pos;
    for (int i = 0; i < n; i++)
    {
        stop_pos = flag - 1;
        flag = 0;
        for (int j = 0; j < stop_pos; j++)
        {
            if (a[j] > a[j+1])
            {
                swap(a[j], a[j+1]);
                flag = j + 1;
            }
        }
    }
}

---

2）插入排序

排序思想：

① 对于第K个元素，将该元素的值存储在零时变量中，比较前一个元素与该元素的大小，如果大于该元素就将前一个元素往后移动一步；
② 比较前面第二个元素与该元素的大小，如果大于该元素就将前第二个元素往后移动一步；
③ 重复上述过程直到找到小于等于原来第K个元素（保存在零时变量中）的位置，并将第K个元素插入到这个元素的后面。或者找不到小于等于第K个元素的位置，就将原来第K个元素插入到数组的首地址。

动图演示：

效率分析：
首先从空间来看，它只需要一个元素的辅助空间，用于元素的交换。
从时间分析，首先外层循环要进行n-1次插入，每次插入最少比较一次(正序),移动0次；最多比较i次，移动i+1(逆序)。因此，直接插入排序的时间复杂度为O(n^2)。

代码实现：

#include 
#include

using namespace std;

void insertsort(vector<int>& a)
{
    int n = a.size();
    for (int i = 1; i < n; i++)
    {
        int insert_num = a[i], j;
        for (j = i - 1; j >= 0; j--)
        {
            if (a[j] > insert_num)
                a[j + 1] = a[j];
            else
                break;
        }
        a[j + 1] = insert_num;
    }
}

---

3）选择排序

排序思想：
从0开始，每次确定一个位置的元素。假设当前需要确定的位置下标为i，则将i处的元素与后面的元素逐个比较，并将每次比较结果中较小的元素存放在i处，从而保证i处一直保存着最小元素。

动图演示：

效率分析：
容易看出，待排序序列为正序，移动次数最小，为 0 次；待排序序列为逆序时，移动次数最多，为 3(n-1) 次。但无论记录的初始排列如何，关键码的比较次数相同，第 i 趟排序需进行 n-i 次关键码的比较，而简单选择排序需要进行 n-1 趟排序，因此，总的比较次数为 O(n^2)。无论是最优、最差时间复杂度，还是平均时间复杂度，均为 O(n^2)。
对于空间复杂度来说，简单选择排序仅需一个存储空间用于记录交换的暂存单元，即空间复杂度为 O(1)。

代码实现：

#include 
#include

using namespace std;

void select_sort(vector<int>& vt)
{
    for (int i = 0; i < vt.size() - 1; i ++)
    {
        int swap_pos = i;
        for (int j = i + 1; j < vt.size(); j++)
        {
            if (vt[swap_pos] > vt[j])
            {
                swap_pos = j;
            }
        }
        
        if (swap_pos != i)
        {
            swap(vt[swap_pos], vt[i]);
        }
    }
}

---

4）希尔排序

排序思想：
先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成），分别进行直接插入排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上有较大提高。当增量为1的时候，希尔排序与插入排序就完全是一样的过程。

动图演示：

效率分析：
希尔排序的时间复杂度比较复杂，选用不同的希尔增量也会导致复杂度不同。希尔排序的时间复杂度在O(nlog2n)和O(n^2)之间，大致为O(n^1.3)。
由于希尔排序对每个子序列单独比较，在比较时进行元素移动，有可能改变相同排序码元素的原始顺序，因此希尔排序是不稳定的。

代码实现：

#include 
#include

using namespace std;

void shellsort(vector<int>& a)
{
    int n = a.size();
    for (int increment = n / 2; increment > 0; increment /= 2)
    {
        for (int i = increment; i < n; i++)
        {
            int insert_num = a[i], j;
            for (j = i - increment; j >= 0; j -= increment)
            {
                if (a[j] > insert_num)
                    a[j + increment] = a[j];
                else
                    break;
            }
            a[j + increment] = insert_num;
        }
    }
}

---

5）堆排序

排序思想：
① 建立最大堆，建堆的过程是从N/2的位置开始，将父节点与子节点比较，如果子节点大于父节点则交换。为什么是N/2，是因为堆中树叶的个数是N/2。
② 从堆中删除堆顶元素，对于最大堆而言，堆顶元素也就是最大元素。每删除一个堆顶元素，就将堆顶元素放在数组的后面，因为每删除一个就出现一个空位，所以数组后面是有地方存放的。
③ 进行N-1次的删除以后，整个数组就是排序的状态了。

动图演示：

效率分析：
在整个堆排序中，共需要进行n/2+n-1次筛选运算，每次筛选运算进行双亲和盖子或兄弟结点的排序码的比较和移动次数都不会超过完全二叉树的深度log2n +1，所以，每次筛选运算的时间复杂度为O(log2n)，故整个排序过程的时间复杂度为O(nlog2n) ,是一种不稳定的排序算法。

代码实现：

#include 
#include

using namespace std;

//建立一个大顶堆O(n),要求就是 把最大的元素 移动到堆顶 也就是a[0]
void make_heap(vector<int>& a, int size) //size的当前堆的大小，也就是数组的前size个数
{
    for (int i = size - 1; i > 0; i--)
    {
        if (i % 2 && a[i] > a[(i - 1) / 2])//奇数
            swap(a[i], a[(i - 1) / 2]);
        else if (i % 2 == 0 && a[i] > a[(i - 2) / 2])//偶数
            swap(a[i], a[(i - 2) / 2]);
    }
}
void heapsort(vector<int>& a)
{
    int n = a.size();
    while (n)
    {
        make_heap(a, n); //每次把新的最大元素移到堆顶，也就是a[0]
        n--;
        swap(a[0], a[n]); //然后把当前最大移动到后面来作为排好序的元素
    }
}

---

6）归并排序

排序思想：
将两个有序表合并成一个有序表。
分解（Divide）：将n个元素分成个含n/2个元素的子序列。
解决（Conquer）：用合并排序法对两个子序列递归的排序。
合并（Combine）：合并两个已排序的子序列已得到排序结果。

动图演示：

效率分析：
不管元素在什么情况下都要做这些步骤，所以花销的时间是不变的，所以该算法的最优时间复杂度和最差时间复杂度及平均时间复杂度都是一样的为：O( nlogn )
归并的空间复杂度就是那个临时的数组和递归时压入栈的数据占用的空间：n + logn；所以空间复杂度为: O(n)。
归并排序算法中，归并最后到底都是相邻元素之间的比较交换，并不会发生相同元素的相对位置发生变化，故是稳定性算法。

代码实现：

#include 
#include

using namespace std;

vector<int> mergeHelper(vector<int> &a, int left, int right)
{
    if (left == right) return vector<int> (1, a[left]);
    int mid = (right - left) / 2 + left;
    vector<int> l = mergeHelper(a, left, mid);
    vector<int> r = mergeHelper(a, mid + 1, right);
    //merge
    vector<int> ret;
    int ll = 0, rr = 0;
    while (ll < l.size() && rr < r.size())
    {
        if (l[ll] <= r[rr])     ret.push_back(l[ll++]);
        else                    ret.push_back(r[rr++]);
    }
    while (ll < l.size()) ret.push_back(l[ll++]);
    while (rr < r.size()) ret.push_back(r[rr++]);
    return ret;
}
 
void mergesort(vector<int>& a)
{
    a = mergeHelper(a, 0, a.size() - 1);
}

---

7）快速排序

排序思想：
快速排序使用分治法策略来把一个序列分为两个子序列。
① 从数列中挑出一个元素，称为 “基准”，
② 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区 *** 作。
③ 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。

动图演示：
分区过程
建立 2 个指针（命名为 lo 和 hi），分别指向序列中第一个元素和倒数第 2 个元素，lo 指针向右移动，当指向的元素不小于 31 时暂停。hi 指针向左移动，当指向的元素不大于 31 时暂停。交换 lo 和 hi 所指元素的位置，重复执行上述步骤，直至 lo ≥ hi。此时，将 pivot 元素与 lo 所指元素交换位置。

效率分析：
快速排序是递归的，需要有一个栈存放每层递归调用的指针和参数。最大递归调用层次数和递归树高度一致。理想情况为log2(n+1);最坏情况即待排序对象序列已经按其排序码从小到大排好序的情况下，其递归树成为单只树，深度为n。因此，快速排序最好的空间度咋读为O(log2n),最坏的空间复杂度为O(n),是一种不稳定的排序方法。

代码实现：

#include 
#include

using namespace std;

void quicksortHelper(vector<int>& a, int start, int end)
{
    if (start >= end) return;
    int l = start, r = end;
    int pivot = a[(end - start) / 2 + start];
    while (l <= r)
    {
        while (l <= r && a[r] > pivot)  r--;
        while (l <= r && a[l] < pivot)  l++;
        if (l <= r) swap(a[l++], a[r--]);
    }
    quicksortHelper(a, start, r);
    quicksortHelper(a, l, end);
}
void quicksort(vector<int>& a)
{
    quicksortHelper(a, 0, a.size() - 1);
}

---

8）基数排序

排序思想：

基数排序是一种非比较型整数排序算法。原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。

在计算机上实现基数排序时，应采用链表作存储结构，即链式基数排序，具体作法为：
①待排序记录以指针相链，构成一个链表；
②“分配”时，按当前“关键字位”所取值，将记录分配到不同的“链队列”中，每个队列中记录的“关键字位”相同；
③“收集”时，按当前关键字位取值从小到大将各队列首尾相链成一个链表；
④对每个关键字位均重复②和③两步。

动图演示：

效率分析：
链式基数排序算法对数据进行d趟扫描，每趟需时间O(n+j)。因此总的计算时间为O(d(n+j))。
对于不同的基数j所用的时间是不同的。基数排序适用于链式存储结构的记录的排序，它要求的附加存储量是j个队列的头、尾指针。所以，需要O(n+j)辅助空间。
基数排序时一种稳定的排序方法。

代码实现：

#include 

using namespace std;
 
int get_max(int a[], int n)
{
    int i, max;

    max = a[0];
    for (i = 1; i < n; i++)
        if (a[i] > max)
            max = a[i];
    return max;
}

void count_sort(int a[], int n, int exp)
{
    int output[n];             // 存储"被排序数据"的临时数组
    int i, buckets[10] = {0};

    // 将数据出现的次数存储在buckets[]中
    for (i = 0; i < n; i++)
        buckets[ (a[i]/exp)%10 ]++;

    // 更改buckets[i]。目的是让更改后的buckets[i]的值，是该数据在output[]中的位置。
    for (i = 1; i < 10; i++)
        buckets[i] += buckets[i - 1];

    // 将数据存储到临时数组output[]中
    for (i = n - 1; i >= 0; i--)
    {
        output[buckets[ (a[i]/exp)%10 ] - 1] = a[i];
        buckets[ (a[i]/exp)%10 ]--;
    }

    // 将排序好的数据赋值给a[]
    for (i = 0; i < n; i++)
        a[i] = output[i];
}

void radix_sort(int a[],int n)
{
    int exp;    // 指数。当对数组按各位进行排序时，exp=1；按十位进行排序时，exp=10；...
    int max = get_max(a, n);    // 数组a中的最大值

    // 从个位开始，对数组a按"指数"进行排序
    for (exp = 1; max/exp > 0; exp *= 10)
        count_sort(a, n, exp);
}