排序算法总结 C++

使用模板编写，自带类型均可使用，使用类 class 或结构体 struct 时必须重载大于 > 运算符

参数汇总

1. 冒泡排序

思路：比较相邻两个元素，小者交换到前面
从前到后两两交换，一直比较到最后，最大值置于最后

1.0 简化冒泡

template <typename T>
void bubbleSort(vector<T>& nums)
{
    for (int i = 0; i < nums.size() - 1; ++i)
    {
        for (int j = 0; j < nums.size() - 1 - i; ++j)
            if (nums[j] > nums[j + 1])
                swap(nums[j], nums[j + 1]);
    }
}

1.1 优化

用 flag 优化，写有序时跳出循环

void bubbleSort(vector<T>& nums)
{
    for (int i = 0; i < nums.size() - 1; ++i)
    {
       bool flag = true;
        for (int j = 0; j < nums.size() - 1 - i; ++j)
            if (nums[j] > nums[j + 1])
            {
               swap(nums[j], nums[j + 1]);
               flag = false;
            }
        if(flag)
           break;
    }
}

参数

2. 选择排序

思路：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾。

template<typename T>
void selectSort(vector<T>& nums)
{
    for (int i = 0; i < nums.size() - 1; ++i)
    {
        int min = i;
        for (int j = i + 1; j < nums.size(); ++j)
        {
            if (nums[j] < nums[min])
                min = j;
        }
        swap(nums[i], nums[min]);
    }
}

参数

3. 插入排序

思路：从数组的第二个元素开始，将元素按顺序插入到前面已经排好序的数组中
一般以第一个元素作为起始元素，从第二个元素开始依次插入

template<typename T>
void insertSort(vector<T>& nums)
{
    for (int i = 0; i < nums.size() - 1; ++i)
    {
        for (int j = i + 1; j > 0; --j)
        {
            if (nums[j] >= nums[j - 1])
                break;// 减少比较次数
            else
                swap(nums[j], nums[j - 1]);
        }
    }
}

参数

4. 希尔排序

思路：希尔排序 插入排序的一种更高效的改进版本，非稳定排序算法
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰分成一组，算法便终止
与插入排序区别是，插入排序每次递增量是 1 ，希尔排序是 gap

template<typename T>
void shellSort(vector<T>& nums)
{
    int i, j, gap;
    int n = nums.size();
    for (gap = n / 2; gap > 0; gap /= 2)
    {
        // 共 gap 个组，对每组都执行直接插入排序
        for (int i = 0; i < gap; ++i)
        {// 此后为插入排序！！！
            // 注意内部循环写法
            for (j = i + gap; j < n; j += gap)
            {
                // 如果a[j] < a[j-gap]，则寻找a[j]位置，并将后面数据的位置都后移。
                if (nums[j] < nums[j - gap])
                {
                    T tmp = nums[j];
                    int k = j - gap;
                    // 此时插入要向前循环，k 会变化，因此要检验
                    // 不能简单将上面式子代入！！
                    while (k >= 0 && nums[k] > tmp)
                    {
                        nums[k + gap] = nums[k];
                        k -= gap;
                    }
                    nums[k + gap] = tmp; //交换完成
                }
            }
        }
    }
}

参数

5. 归并排序

思路：分而治之，后序遍历二叉树的思想

template<typename T>
void mergeSort(vector<T>& nums,int left,int right)
{
    if (left < right)
    {
        int mid = (left + right) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        mergeSortHelper(nums, left, mid, right);
    }
}
template<typename T>
void mergeSortHelper(vector<T>&nums, int a, int mid, int right)
{
    int i= a, j = mid + 1;
    // 注意此处 start = a，不是 0
    int start = a;
    vector<T> tmp = nums;
    while (i <= mid && j <= right) nums[start++] = tmp[i] < tmp[j] ? tmp[i++] : tmp[j++];
    while (i <= mid) nums[start++] = tmp[i++];
    while (j <= right) nums[start++] = tmp[j++];
}

参数

6. 快速排序

思路：在数组中选择一个元素作为基准
小于基准元素移到基准左边，反之移到基准右边（分区操作）
此时基准元素所在位置就是排序完成后，基准元素的最终位置
对基准元素的左右两个子集重复一二步，直到子集中剩余一个元素为止

template<typename T>
void quickSort(vector<T>& nums, int left, int right)
{
    if (left < right)
    {
        int pivot = quickSortHelper(nums, left, right);
        quickSort(nums, left, pivot - 1);
        quickSort(nums, pivot + 1, right);
    }
}
template<typename T>
int quickSortHelper(vector<T>&nums, int left, int right)
{
    int pivot = nums[left];
    while (left < right)
    {
        // pivot 取 left，则先从右边开始 --
        // 都是交换 left 与 right，pivot 只是起到一个记录的作用
        while (left < right&&pivot <= nums[right]) right--;
        nums[left] = nums[right];
        while (left < right&&nums[left] <= pivot) left++;
        nums[right] = nums[left];
    }
    nums[left] = pivot;
    return left;
}

参数

7. 堆排序

利用堆此种数据结构设计的排序算法
堆是一种特殊的树（完全二叉树 叶子结点只可能在最大的两层出现）

特点：根节点下标为 0，若父节点下标为 i

1. 其左孩子下标为 2*i+1
2. 右孩子为 2*i+2
3. 第一个非叶子节点为 arr.size()/2-1

• 小顶堆：每个节点的值都 >= 其子节点的值 => 堆排序的升序排序
• 大顶堆：每个节点的值都 <= 其子节点的值 => 堆排序的降序排序
• 大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
• 小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
  

思想

利用大(小)顶堆记录最大(小)关键词的特性

1. 将数组构建成大顶堆，此堆为初始的无序区(堆顶确定)
2. 将堆顶元素R[0]与最后一个元素R[n-1]交换得到无序区[0,n-2]与有序区[n-1]
3. 调整无序区为新堆，重复2，3
4. 无序区不断减少，有序区逐渐增加，当有序区间元素个数为 n-1 时完成

template <typename T>
    void heapSort(vector<T> &nums)
    {
        int n = nums.size();
        //1. 构建一个最大堆
        // 从最后一个非叶子节点开始
        for (int i = n / 2 - 1; i >= 0; --i)
        {
            heapSortHelperMin(nums, i, n);
            //heapSortHelperMax(nums, i, n);
        }
        //2. 将堆顶（最大值）与末位交换，再重新调整最大堆
        for (int i = n - 1; i > 0; --i)
        {
            swap(nums[0], nums[i]);
            // 构造堆时，遍历每个非叶子节点已经排好序
            // 当交换元素时，只会影响最顶端的顺序，最低端是有序区
            // 因为堆是整体有序的，因此只需要管理受影响的最顶端，有问题可以递归处理后面受影响的堆
            heapSortHelperMin(nums, 0, i);
            //heapSortHelperMax(nums, 0, i);
        }
    }

    // 调整堆，不是构造堆
    template <typename T>
    void heapSortHelperMax(vector<T> &nums, int father, int length)
    {
        int maxIndex = father;
        // 如有左子树，同时左子树大于父节点，则最大指针指向左子树
        if (father * 2 + 1 < length && nums[father * 2 + 1] > nums[maxIndex])
            maxIndex = 2 * father + 1;
        // 如有右子树，同时右子树大于父节点和左子树，则最大指针指向右子树
        if (father * 2 + 2 < length && nums[father * 2 + 2] > nums[maxIndex])
            maxIndex = 2 * father + 2;
        // 父节点不是最大值，则将父节点与最大值交换，同时递归调整
        if (maxIndex != father)
        {
            swap(nums[maxIndex], nums[father]);
            heapSortHelperMax(nums, maxIndex, length);
        }
    }

    template <typename T>
    void heapSortHelperMin(vector<T> &nums, int father, int length)
    {
        int minIndex = father;
        if (father * 2 + 1 < length && nums[father * 2 + 1] < nums[minIndex])
            minIndex = 2 * father + 1;
        if (father * 2 + 2 < length && nums[father * 2 + 2] < nums[minIndex])
            minIndex = 2 * father + 2;
        if (minIndex != father)
        {
            swap(nums[minIndex], nums[father]);
            heapSortHelperMin(nums, minIndex, length);
        }
    }

构造堆的其它方法

使用 STL 的优先队列，priority_queue，需要头文件
底层就是一个堆结构，通过 top() 来访问队首元素
priority_queue< type, container, function >
三个参数，后面两个可以省略，第一个不可以。其中：

1. type数据类型；
2. container实现优先队列的底层容器；
3. function元素之间的比较方式；
   container，要求必须是数组形式实现的容器，例如vector、deque，不能是list

在STL中，默认情况下（不加后面两个参数）是以vector为容器，以 operator< 为比较方式，所以在只使用第一个参数时，优先队列默认是一个最大堆，每次输出的堆顶元素是此时堆中的最大元素。

// 默认为大顶堆
priority_queue<int> big_heap;
//另一种构建大顶堆的方法
priority_queue<int,vector<int>,less<int> > big_heap2; 
//构造一个空的优先队列,此优先队列是一个小顶堆
priority_queue<int,vector<int>,greater<int> > small_heap;

优先队列堆排序

// 利用优先队列实现
template <typename T>
// 调整遍历顺序或大小堆，即可逆转排序
void heapSort(vector<T> &nums)
{
    int n = nums.size();
    //1. 构建一个最大堆
    priority_queue<T, vector<T>> bigHeap;
    priority_queue<T, vector<T>, less<T>> smallHeap;
    for (auto x : nums)
        bigHeap.push(x);

    //2. 将堆顶（最大值）与末位交换，再重新调整最大堆
    for (int i = 0; i < n; ++i)
    {
        nums[i] = bigHeap.top();
        bigHeap.pop();
    }
}

参数

8. 计数排序

思路：将输入的数据值转化为键存储在额外开辟的数组空间中
要求输入的数据：必须在确定范围内的整数

• 找出待排序的数组中最大和最小的元素
• 统计数组中每个值为i的元素出现的次数，存入数组C的第i项
• 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
• 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

void countSort(vector<int>& nums)
{
    int n = nums.size();
    int minVal = nums[0], maxVal = nums[0];
    for (int i = 0; i < n; ++i)
    {
        minVal = min(minVal , nums[i]);
        maxVal = max(maxVal, nums[i]);
    }
    vector<int> bucket(maxVal - minVal + 1, 0);
    int offset = minVal - 0;

    // 将数据存入 bucket
    for (auto x : nums)
        bucket[x - offset]++;
    int j = 0;
    for (int i = 0; i < bucket.size(); ++i)
    {
        // 对应数值是 i+offset
        // 每个数值次数是 bucket[i]
        // 外部 --
        while (bucket[i]--)
            nums[j++] = i + offset;
    }
}

参数

9. 桶排序

桶排序是计数排序的升级版，利用函数的映射关系，把计数排序中的多个坑位整合成为一个桶

思路

(1) 设置一个定量的数组当作空桶；
(2) 遍历输入数据，并且把数据一个一个放到对应的桶里去；
(3) 对每个不是空的桶进行排序；
(4) 从不是空的桶里把排好序的数据拼接起来。

算法效率在于映射函数的确定。为了更加高效，需要：

1. 在外部空间充足的情况下，尽可能增大桶的数量
2. 使用的映射函数能够将输入的 N 个数据均匀地分配到 K 个桶中

最快：输入数据均匀分配到每个桶中
最慢：输入数据被分配到同一个桶中
当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间 O(n)

// 桶排序
// 桶的大小
void bucketSort(vector<int>& nums, int bucketSize)
{
    int n = nums.size();
    if (n < 2) return;
    int minVal = nums[0], maxVal = nums[0];
    for (int i = 1; i < n; ++i)
    {
        minVal = min(nums[i], minVal);
        maxVal = max(nums[i], maxVal);
    }

    // 桶的数量，当 bucketSize 为 1 时，退货为计数排序
    int bucketCount = (maxVal - minVal) / bucketSize + 1;
    int offset = minVal - 0;
    vector<vector<int>> bucketVec(bucketCount, vector<int>());

    // 元素入桶
    for (int i = 0; i < n; ++i)
    {
        // 重点！！！
        bucketVec[(nums[i] - offset) / bucketSize].push_back(nums[i]);
    }
    // clear 之后，不能直接用 []，因为并没有初始化，需要用 push_back
    nums.clear();
    for (int i = 0; i < bucketCount; ++i)
    {
        // 内部可以选择方法对桶内元素进行排序
        // 空桶跳过，提高效率
        if (bucketVec[i].size() != 0)
        {
            sort(bucketVec[i].begin(), bucketVec[i].end());
            for (auto x : bucketVec[i])
                nums.push_back(x);
                //nums[j++] = x;
        }
    }
}

参数

10. 基数排序

一种非比较型整数排序算法，原理是将整数按位数切割成不同的数字，按每个位数分别比较
因为整数可以表达字符串(名字或日期)和特定模式的浮点数，因此基数排序也可用于字符串

计数排序，桶排序，基数排序区别

三者都使用了桶的概念，但是

1. 计数排序：每个桶只存储单一键值
2. 桶排序：每个桶存储一定范围的数值
3. 基数排序：根据键值的每位数字来分配桶

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

• LSD: 由键值的 最右边（最小位） 开始, 适用于位数少的序列，可采用桶排序
• MSD: 由键值的 最左边（最大位） 开始, 适用于位数多的序列，可采用计数排序

在进行某个特定位数比较时，要用稳定排序，将上次排序成果保留。例如十位数的排序过程能保留个位数的排序成果，百位数的排序过程能保留十位数的排序成果。
基数排序对有负数和0的数列难以进行排序

void radixSort(vector<int>& nums)
{
    int maxVal = 0;
    for (int x : nums)
        if (x > maxVal) maxVal = x;

    // d 表示 1，10，100 等，序列最大值长度为3，d = 100
    int d = 10;
    while (maxVal / 10)
    {
        d *= 10;
        maxVal /= 10;
    }

    // 从个位开始
    int index = 1;
    while (index<d)
    {
        // 从0到9总共10个桶
        // 每个桶最多有 nums.size()个元素，初始化大小后才能使用 []
        // 如何要使用 push_back() 就不要初始化大小，因为再 push_back() 则会将元素保存在初始化大小的元素之后！！！
        // 同时放于此处可以不用清空数组，当更换数位时
        vector<vector<int>> bucketVec(10, vector<int>());
        //将序列的每个数字放在相应的桶里
        for (int x : nums)
        {
            // 当前位上的数值
            int digit = (x / index) % 10;
            bucketVec[digit].push_back(x);
        }

        // 重写入数组时遍历秩，当下一轮位数变化时，k 能自己重置为 0
        int k = 0;
        // 将上一次排序结果覆盖到原数组
        for (int i = 0; i < 10; i++)
        {
            // 若桶内有元素，依次取出放到原数组中
            if (bucketVec[i].size()!=0)
            {
                for (int j = 0; j < bucketVec[i].size(); ++j)
                    nums[k++] = bucketVec[i][j];
            }
        }
        // 将位数前移
        index *= 10;
    }
}

参数