C++ 实现十大排序算法

????????教你手撕排序，这里有一个概念就是稳定排序。假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。并不是其算法复杂度的稳定，注意一下。

????????算法（Algorithm）?代表着用系统的方法描述解决问题的策略机制，可以通过一定规范的?输入，在有限时间内获得所需要的?输出。

算法的好坏

????????一个算法的好坏是通过?时间复杂度?与?空间复杂度?来衡量的。就是代码需要的时间和内存，也就你时间成本和空间成本。其实这个一个动态的调整，到一定程度，往往就是用空间去换取时间，或者去时间去换取空间（dp其实就是在用空间去换取时间）。当然优秀的代码就是很优秀，排序也是这样，他们的目标都是把一堆数字进行排序。

常见时间复杂度的?“大O表示法”?描述有以下几种：

时间复杂度	非正式术语
O(1)	常数阶
O(n)	线性阶
O(n2)	平方阶
O(log n)	对数阶
O(n log n)	线性对数阶
O(n3)	立方阶
O(2n)	指数阶

一个算法在N规模下所消耗的时间消耗从大到小如下：

O(1) < O(log n) < O(n) < O(n log n) < O(n2) < O(n3) < O(2n)

指数级的增长是非常快的

常见的排序算法

根据时间复杂度的不同，常见的算法可以分为3大类。

1.O(n2)?的排序算法

• 冒泡排序

• 选择排序

• 插入排序

2.O(n log n)?的排序算法

• 希尔排序

• 归并排序

• 快速排序

• 堆排序

3.线性的排序算法

• 计数排序

• 桶排序

• 基数排序

各种排序的具体信息

冒泡排序（Bubble Sort）

冒泡排序（Bubble Sort）?是一种基础的?交换排序。

冒泡排序之所以叫冒泡排序，是因为它每一种元素都像小气泡一样根据自身大小一点一点往数组的一侧移动。

算法步骤如下：

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个；

2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数；

3. 针对所有的元素重复以上的步骤，除了最后一个；

4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

图示如下：

代码如下：

void bubbleSort(vector<int> &a)
{
    int len = a.size();
    for (int i = 0; i < len - 1; i++) //需要循环次数
    {
        for (int j = 0; j < len - 1 - i; j++) //每次需要比较个数
        {
            if (a[j] > a[j + 1])
            {
                swap(a[j], a[j + 1]); //不满足偏序，交换
            }
        }
    }
}

还有一种假的写法就是保证第一个最小，第二个次小，比较的是i和j，虽然也是对的，有点像选择排序，但也不是。其不是冒泡排序

选择排序（Selection Sort）

选择排序（Selection sort）?是一种简单直观的排序算法。

选择排序的主要优点与数据移动有关。

如果某个元素位于正确的最终位置上，则它不会被移动。

选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对?n?个元素的表进行排序总共进行至多?n - 1?次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

选择排序的算法步骤如下：

1. 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置；

2. 然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾；

3. 以此类推，直到所有元素均排序完毕。

图示如下：

代码如下：

void selectionSort(vector<int> &a)
{
    int len = a.size();
    for (int i = 0, minIndex; i < len - 1; i++) //需要循环次数
    {
        minIndex = i;                     //最小下标
        for (int j = i + 1; j < len; j++) //访问未排序的元素
        {
            if (a[j] < a[minIndex])
                minIndex = j; //找到最小的
        }
        swap(a[i], a[minIndex]);
    }
}

插入排序（Insertion Sort）

插入排序（Insertion?sort）?是一种简单直观的排序算法。

它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

插入排序的算法步骤如下：

1. 从第一个元素开始，该元素可以认为已经被排序；

2. 取出下一个元素，在已经排序的元素序列中从后向前扫描；

3. 如果该元素（已排序）大于新元素，将该元素移到下一位置；

4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；

5. 将新元素插入到该位置后；

6. 重复步骤2~5。

图示如下：

代码如下：

void insertionSort(vector<int> &a)
{
    int len = a.size();
    for (int i = 0, j, temp; i < len - 1; i++) //需要循环次数
    {
        j = i;
        temp = a[i + 1];
        while (j >= 0 && a[j] > temp)
        {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = temp;
    }
}

希尔排序（Shell Sort）

希尔排序，也称?递减增量排序算法，是?插入排序?的一种更高效的改进版本。希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

1. 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到?线性排序?的效率；

2. 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。

步长的选择是希尔排序的重要部分。

只要最终步长为1任何步长序列都可以工作。

算法最开始以一定的步长进行排序。

然后会继续以一定步长进行排序，最终算法以步长为1进行排序。

当步长为1时，算法变为普通插入排序，这就保证了数据一定会被排序。

希尔排序的算法步骤如下：

1. 定义一个用来分割的步长；

2. 按步长的长度K，对数组进行K趟排序；

3. 不断重复上述步骤。

图示如下：

?代码如下：

void shell_Sort(vector<int> &a)
{
    int len = a.size();
    for (int gap = len / 2; gap > 0; gap /= 2)
    {
        for (int i = 0; i < gap; i++)
        {
            for (int j = i + gap, temp, preIndex; j < len; j = j + gap) //依旧需要temp作为哨兵
            {
                temp = a[j];        //保存哨兵
                preIndex = j - gap; //将要对比的编号
                while (preIndex >= 0 && a[preIndex]>temp)
                    {
                        a[preIndex + gap] = a[preIndex]; //被替换
                        preIndex -= gap;                 //向下走一步
                    }
                a[preIndex + gap] = temp; //恢复被替换的值
            }
        }
    }
}

快速排序（Quick Sort）

快速排序（Quicksort），又称?划分交换排序（partition-exchange sort）?。

快速排序（Quicksort）?在平均状况下，排序?n?个项目要?O(n log n)?次比较。在最坏状况下则需要?O(n2)?次比较，但这种状况并不常见。事实上，快速排序?O(n log n)?通常明显比其他算法更快，因为它的?内部循环（inner loop）?可以在大部分的架构上很有效率地达成。

快速排序使用?分治法（Divide and conquer）?策略来把一个序列分为较小和较大的2个子序列，然后递归地排序两个子序列。

快速排序的算法步骤如下：

1. 挑选基准值：从数列中挑出一个元素，称为?“基准”（pivot）?；

2. 分割：重新排序序列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成；

3. 递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。

递归到最底部的判断条件是序列的大小是零或一，此时该数列显然已经有序。

选取基准值有数种具体方法，此选取方法对排序的时间性能有决定性影响。

图示如下：

代码如下：

int partition(vector<int> &a, int left, int right)
{
    int pivot = a[right];
    int i = left - 1;
    for (int j = left; j < right; j++)
    {
        if (a[j] <= pivot)
        {
            i++;
            swap(a[i], a[j]);
        }
    }
    swap(a[i + 1], a[right]);
    return i + 1;
}

void quickSort(vector<int> &a, int left, int right)
{
    if (left < right)
    {
        int mid = partition(a, left, right);
        quickSort(a, left, mid - 1);
        quickSort(a, mid + 1, right);
    }
}

void qSort(vector<int> &a)
{
    quickSort(a, 0, a.size() - 1);
}

归并排序（Merge Sort）

归并排序（Merge sort）?，是创建在归并操作上的一种有效的排序算法，时间复杂度为?O(n log n)?。1945年由约翰·冯·诺伊曼首次提出。该算法是采用?分治法（Divide and Conquer）?的一个非常典型的应用，且各层分治递归可以同时进行。

其实说白了就是将两个已经排序的序列合并成一个序列的操作。

并归排序有两种实现方式

第一种是?自上而下的递归?，算法步骤如下：

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；

2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置；

3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；

4. 重复步骤3直到某一指针到达序列尾；

5. 将另一序列剩下的所有元素直接复制到合并序列尾。

具体代码：

void mergeSort(vector<int> &a, vector<int> &T, int left, int right)
{
    if (right - left == 1)
        return;
    int mid = left + right >> 1, tmid = left + right >> 1, tleft = left, i = left;
    mergeSort(a, T, left, mid), mergeSort(a, T, mid, right);
    while (tleft < mid || tmid < right)
    {
        if (tmid >= right || (tleft < mid && a[tleft] <= a[tmid]))
        {
            T[i++] = a[tleft++];
        }
        else
        {
            T[i++] = a[tmid++];
        }
    }
    for (int i = left; i < right; i++)
        a[i] = T[i];
}
void mSort(vector<int> &a)
{
    int len = a.size();
    vector<int> T(len);
    mergeSort(a, T, 0, len);
}

迭代比起递归还是安全很多，太深的递归容易导致堆栈溢出。所以建议可以试下迭代实现，acm里是够用了。

堆排序（Heap Sort）

堆排序（Heapsort）?是指利用?二叉堆?这种数据结构所设计的一种排序算法。堆是一个近似?完全二叉树?的结构，并同时满足?堆积的性质?：即子节点的键值或索引总是小于（或者大于）它的父节点。

二叉堆是什么？

二叉堆分以下两个类型：

1.最大堆：最大堆任何一个父节点的值，都大于等于它左右孩子节点的值。

• 图示如下：

  

?

• 数组表示如下：

  [10, 8, 9, 7, 5, 4, 6, 3, 2]

2.最小堆：最小堆任何一个父节点的值，都小于等于它左右孩子节点的值。

• 图示如下：

• 数组表示如下：

  [1, 3, 2, 6, 5, 7, 8, 9, 10]

堆排序的算法步骤如下：

1. 把无序数列构建成二叉堆；

2. 循环删除堆顶元素，替换到二叉堆的末尾，调整堆产生新的堆顶。

代码如下：

void adjustHeap(vector<int> &a, int i,int len)
{
    int maxIndex = i;
    //如果有左子树，且左子树大于父节点，则将最大指针指向左子树
    if (i * 2 + 1 < len && a[i * 2 + 1] > a[maxIndex])
        maxIndex = i * 2 + 1;
    //如果有右子树，且右子树大于父节点和左节点，则将最大指针指向右子树
    if (i * 2 + 2 < len && a[i * 2 + 2] > a[maxIndex])
        maxIndex = i * 2 + 2;
    //如果父节点不是最大值，则将父节点与最大值交换，并且递归调整与父节点交换的位置。
    if (maxIndex != i)
    {
        swap(a[maxIndex], a[i]);
        adjustHeap(a, maxIndex,len);
    }
}

void Sort(vector<int> &a)
{
    int len = a.size();
    //1.构建一个最大堆
    for (int i = len / 2 - 1; i >= 0; i--) //从最后一个非叶子节点开始
    {
        adjustHeap(a, i,len);
    }
    //2.循环将堆首位（最大值）与末位交换，然后在重新调整最大堆

    for (int i = len - 1; i > 0; i--)
    {
        swap(a[0], a[i]);
        adjustHeap(a, 0, i);
    }
}

我这里用了递归写法，非递归也很简单，就是比较哪个叶子节点大，再继续for下去。

计数排序（Counting Sort）

计数排序（Counting sort）?是一种稳定的线性时间排序算法。该算法于1954年由 Harold H. Seward 提出。计数排序使用一个额外的数组来存储输入的元素，计数排序要求输入的数据必须是有确定范围的整数。

当输入的元素是?n?个?0?到?k?之间的整数时，它的运行时间是?O(n + k)?。计数排序不是比较排序，排序的速度快于任何比较排序算法。

计数排序的算法步骤如下：

1. 找出待排序的数组中最大和最小的元素；

2. 统计数组中每个值为?i?的元素出现的次数，存入数组?C?的第?i?项；

3. 对所有的计数累加（从数组?C?中的第一个元素开始，每一项和前一项相加）；

4. 反向填充目标数组：将每个元素?i?放在新数组的第?C[i]?项，每放一个元素就将 C[i] 减去1。

代码如下：

void CountingSort(vector<int> &a)
{
    int len = a.size();
    if (len == 0)
        return;
    int Min = a[0], Max = a[0];
    for (int i = 1; i < len; i++)
    {
        Max = max(Max, a[i]);
        Min = min(Min, a[i]);
    }
    int bias = 0 - Min;
    vector<int> bucket(Max - Min + 1, 0);
    for (int i = 0; i < len; i++)
    {
        bucket[a[i] + bias]++;
    }
    int index = 0, i = 0;
    while (index < len)
    {
        if (bucket[i])
        {
            a[index] = i - bias;
            bucket[i]--;
            index++;
        }
        else
            i++;
    }
}

桶排序（Bucket Sort）

桶排序（Bucket Sort）?跟?计数排序（Counting sort）?一样是一种稳定的线性时间排序算法，不过这次需要的辅助不是计数，而是桶。

工作的原理是将数列分到有限数量的桶里。每个桶再个别排序。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间?O(n)。

桶排序的算法步骤如下：

1. 设置一个定量的数组当作空桶子；

2. 寻访序列，并且把项目一个一个放到对应的桶子去；

3. 对每个不是空的桶子进行排序；

4. 从不是空的桶子里把项目再放回原来的序列中。

代码如下：

我觉得递归调用桶排序比较慢，这里直接用了sort函数，其实这个函数能决定这个算法的优劣，这些排序都是针对固定的序列的，可以自己尝试不同的算法去优化

size为1是，其实和计数排序是一样的，不过这里使用了辅助的空间，没有合并相同的，内存消耗要更大。

void bucketSort(vector<int> &a, int bucketSize)
{
    int len = a.size();
    if (len < 2)
        return;
    int Min = a[0], Max = a[0];
    for (int i = 1; i < len; i++)
    {
        Max = max(Max, a[i]);
        Min = min(Min, a[i]);
    }
    int bucketCount = (Max - Min) / bucketSize + 1;
    //这个区间是max-min+1，但是我们要向上取整，就是+bucketSize-1，和上面的形式是一样的
    vector<int> bucketArr[bucketCount];
    for (int i = 0; i < len; i++)
    {
        bucketArr[(a[i] - Min) / bucketSize].push_back(a[i]);
    }
    a.clear();
    for (int i = 0; i < bucketCount; i++)
    {
        int tlen = bucketArr[i].size();
        sort(bucketArr[i].begin(),bucketArr[i].end());
        for (int j = 0; j < tlen; j++)
            a.push_back(bucketArr[i][j]);
    }
}

基数排序（Radix Sort）

基数排序（Radix sort）?是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

工作原理是将所有待比较数值（正整数）统一为同样的数字长度，数字较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。

基数排序的方式可以采用?LSD（Least significant digital）?或?MSD（Most significant digital）?。

LSD?的排序方式由键值的?最右边（最小位）?开始，而?MSD?则相反，由键值的?最左边（最大位）?开始。

MSD?方式适用于位数多的序列，LSD?方式适用于位数少的序列。

基数排序?、?桶排序?、?计数排序?原理都差不多，都借助了?“桶”?的概念，但是使用方式有明显的差异，其差异如下：

• 基数排序：根据键值的每位数字来分配桶；

• 桶排序：每个桶存储一定范围的数值；

• 计数排序：每个桶只存储单一键值。

LSD?图示如下：

LSD?实现如下：

注意不要用负数，用负数完全相反，正负都有可以都转换为正数

void RadixSortSort(vector<int> &a)
{
    int len = a.size();
    if (len < 2)
        return;
    int Max = a[0];
    for (int i = 1; i < len; i++)
    {
        Max = max(Max, a[i]);
    }
    int maxDigit = log10(Max) + 1;
    //直接使用log10函数获取位数，这样的话就不用循环了，这里被强制转换是向下取整
    int mod = 10, div = 1;
    vector<int> bucketList[10];
    for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10)
    {
        for (int j = 0; j < len; j++)
        {
            int num = (a[j] % mod) / div;
            bucketList[num].push_back(a[j]);
        }
        int index = 0;
        for (int j = 0; j < 10; j++)
        {
            int tlen=bucketList[j].size();
            for (int k = 0; k < tlen; k++)
                a[index++] = bucketList[j][k];
            bucketList[j].clear();
        }
    }
}