排序算法总结

#1 序
- 我们通常所说的排序算法往往指的是内部排序算法，即数据记录在内存中进行排序。排序算法大体可分为两种：
##1.1 比较排序
时间复杂度`O(nlogn) ~ O(n^2)`,主要有:`冒泡排序,选择排序,插入排序,归并排序,堆排序,快速排序`等。
##1.2 非比较排序
时间复杂度可以达到`O(n)`,主要有:`计数排序,基数排序,桶排序`等。
##1.3 图表
![title](https://leanote.com/api/file/getImage?fileId=5e9465d2ab644137e7003193)
这里的排序算法稳定性的简单形式化定义为:如果`Ai = Aj`,排序前Ai在Aj之前,排序后Ai还在Aj之前,则称这种排序算法是稳定的。通俗地讲就是保证排序前后两个相等的数的相对顺序不变。

对于基础类型，相同值是无差别的，排序前后相同值的相对位置并不重要，所以选择更为高效的快速排序，尽管它是不稳定的排序算法；而对于非基础类型，排序前后相等实例的相对位置不宜改变，所以选择稳定的归并排序。
#2 比较排序代码
##2.1 冒泡排序
```
// 分类 -------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- O(n^2)
// 最优时间复杂度 ---- 如果能在内部循环第一次运行时,使用一个旗标来表示有无需要交换的可能,可以把最优时间复杂度降低到O(n)
// 平均时间复杂度 ---- O(n^2)
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 稳定
void Swap(int A[], int i, int j)
{
    int temp = A[i];
    A[i] = A[j];
    A[j] = temp;
}

void BubbleSort(int A[], int n)
{
    for (int j = 0; j < n - 1; j++)         // 每次最大元素就像气泡一样"浮"到数组的最后
    {
        for (int i = 0; i < n - 1 - j; i++) // 依次比较相邻的两个元素,使较大的那个向后移
        {
            if (A[i] > A[i + 1])            // 如果条件改成A[i] >= A[i + 1],则变为不稳定的排序算法
            {
                Swap(A, i, i + 1);
            }
        }
    }
}
```
## 2.2 简单选择排序
```
#include <stdio.h>

// 分类 -------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- O(n^2)
// 最优时间复杂度 ---- O(n^2)
// 平均时间复杂度 ---- O(n^2)
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 不稳定

void Swap(int A[], int i, int j)
{
    int temp = A[i];
    A[i] = A[j];
    A[j] = temp;
}

void SelectionSort(int A[], int n)
{
    for (int i = 0; i < n - 1; i++)         // i为已排序序列的末尾
    {
        int min = i;
        for (int j = i + 1; j < n; j++)     // 未排序序列
        {
            if (A[j] < A[min])              // 找出未排序序列中的最小值
            {
                min = j;
            }
        }
        if (min != i)
        {
            Swap(A, min, i);    // 放到已排序序列的末尾，该操作很有可能把稳定性打乱，所以选择排序是不稳定的排序算法
        }
    }
}

int main()
{
    int A[] = { 8, 5, 2, 6, 9, 3, 1, 4, 0, 7 }; // 从小到大选择排序
    int n = sizeof(A) / sizeof(int);
    SelectionSort(A, n);
    printf("选择排序结果：");
    for (int i = 0; i < n; i++)
    {
        printf("%d ", A[i]);
    }
    printf("\n");
    return 0;
}
```
## 2.3 直接插入排序
```
#include <stdio.h>

// 分类 ------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- 最坏情况为输入序列是降序排列的,此时时间复杂度O(n^2)
// 最优时间复杂度 ---- 最好情况为输入序列是升序排列的,此时时间复杂度O(n)
// 平均时间复杂度 ---- O(n^2)
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 稳定

void InsertionSort(int A[], int n)
{
    for (int i = 1; i < n; i++)         // 类似抓扑克牌排序
    {
        int get = A[i];                 // 右手抓到一张扑克牌
        int j = i - 1;                  // 拿在左手上的牌总是排序好的
        while (j >= 0 && A[j] > get)    // 将抓到的牌与手牌从右向左进行比较
        {
            A[j + 1] = A[j];            // 如果该手牌比抓到的牌大，就将其右移
            j--;
        }
        A[j + 1] = get; // 直到该手牌比抓到的牌小(或二者相等)，将抓到的牌插入到该手牌右边(相等元素的相对次序未变，所以插入排序是稳定的)
    }
}

int main()
{
    int A[] = { 6, 5, 3, 1, 8, 7, 2, 4 };// 从小到大插入排序
    int n = sizeof(A) / sizeof(int);
    InsertionSort(A, n);
    printf("插入排序结果：");
    for (int i = 0; i < n; i++)
    {
        printf("%d ", A[i]);
    }
    printf("\n");
    return 0;
}
```
直接插入排序的改进版本, 二分插入排序, 但感觉好像也没怎么提升??只是比较大小的次数少了, 移动元素的次数还是那么多:
```
// 分类 -------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- O(n^2)
// 最优时间复杂度 ---- O(nlogn)
// 平均时间复杂度 ---- O(n^2)
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 稳定

void InsertionSortDichotomy(int A[], int n)
{
    for (int i = 1; i < n; i++)
    {
        int get = A[i];                    // 右手抓到一张扑克牌
        int left = 0;                    // 拿在左手上的牌总是排序好的，所以可以用二分法
        int right = i - 1;                // 手牌左右边界进行初始化
        while (left <= right)            // 采用二分法定位新牌的位置
        {
            int mid = (left + right) / 2;
            if (A[mid] > get)
                right = mid - 1;
            else
                left = mid + 1;
        }
        for (int j = i - 1; j >= left; j--)    // 将欲插入新牌位置右边的牌整体向右移动一个单位
        {
            A[j + 1] = A[j];
        }
        A[left] = get;                    // 将抓到的牌插入手牌
    }
}
```
## 2.4 希尔排序
希尔排序是插入排序的更高效的改进, 也叫递减增量排序
```
#include <stdio.h>

// 分类 -------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- 根据步长序列的不同而不同。已知最好的为O(n(logn)^2)
// 最优时间复杂度 ---- O(n)
// 平均时间复杂度 ---- 根据步长序列的不同而不同。
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 不稳定

void ShellSort(int A[], int n)
{
    int h = 0;
    while (h <= n)                          // 生成初始增量
    {
        h = 3 * h + 1;
    }
    while (h >= 1)
    {
        for (int i = h; i < n; i++)
        {
            int j = i - h;
            int get = A[i];
            while (j >= 0 && A[j] > get)
            {
                A[j + h] = A[j];
                j = j - h;
            }
            A[j + h] = get;
        }
        h = (h - 1) / 3;                    // 递减增量
    }
}

int main()
{
    int A[] = { 5, 2, 9, 4, 7, 6, 1, 3, 8 };// 从小到大希尔排序
    int n = sizeof(A) / sizeof(int);
    ShellSort(A, n);
    printf("希尔排序结果：");
    for (int i = 0; i < n; i++)
    {
        printf("%d ", A[i]);
    }
    printf("\n");
    return 0;
}
```
## 2.5 堆排序
```
#include <stdio.h>

// 分类 -------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- O(nlogn)
// 最优时间复杂度 ---- O(nlogn)
// 平均时间复杂度 ---- O(nlogn)
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 不稳定

void Swap(int A[], int i, int j)
{
    int temp = A[i];
    A[i] = A[j];
    A[j] = temp;
}

void Heapify(int A[], int i, int size)  // 从A[i]向下进行堆调整
{
    int left_child = 2 * i + 1;         // 左孩子索引
    int right_child = 2 * i + 2;        // 右孩子索引
    int max = i;                        // 选出当前结点与其左右孩子三者之中的最大值
    if (left_child < size && A[left_child] > A[max])
        max = left_child;
    if (right_child < size && A[right_child] > A[max])
        max = right_child;
    if (max != i)
    {
        Swap(A, i, max);                // 把当前结点和它的最大(直接)子节点进行交换
        Heapify(A, max, size);          // 递归调用，继续从当前结点向下进行堆调整
    }
}

int BuildHeap(int A[], int n)           // 建堆，时间复杂度O(n)
{
    int heap_size = n;
    for (int i = heap_size / 2 - 1; i >= 0; i--) // 从每一个非叶结点开始向下进行堆调整
        Heapify(A, i, heap_size);
    return heap_size;
}

void HeapSort(int A[], int n)
{
    int heap_size = BuildHeap(A, n);    // 建立一个最大堆
    while (heap_size > 1)    　　　　　　 // 堆（无序区）元素个数大于1，未完成排序
    {
        // 将堆顶元素与堆的最后一个元素互换，并从堆中去掉最后一个元素
        // 此处交换操作很有可能把后面元素的稳定性打乱，所以堆排序是不稳定的排序算法
        Swap(A, 0, --heap_size);
        Heapify(A, 0, heap_size);     // 从新的堆顶元素开始向下进行堆调整，时间复杂度O(logn)
    }
}

int main()
{
    int A[] = { 5, 2, 9, 4, 7, 6, 1, 3, 8 };// 从小到大堆排序
    int n = sizeof(A) / sizeof(int);
    HeapSort(A, n);
    printf("堆排序结果：");
    for (int i = 0; i < n; i++)
    {
        printf("%d ", A[i]);
    }
    printf("\n");
    return 0;
}
```
自己实现的C++迭代版本:
```
  void swap(int &a,int &b)
    {
        int temp = a;
        a = b;
        b = temp;
    }
    //堆排序
    vector<int>& HeapSort(vector<int> &nums)
    {
        int len = nums.size();
        if(len<=1) return nums;
        //从前到后,构造大顶堆
        int left(0),right(0);
        int parent(0),child(0);
        while(right < len-1)
        {
            ++right;
            child = right;
            while(child > 0)
            {
                parent = (child - 1)/2;
                if(nums[parent] < nums[child]) 
                {
                    swap(nums[parent],nums[child]);
                    child = parent;
                }
                else break;
            }
        }
        //依次将大顶堆根节点,放到最后
        left = len;
        int child1,child2;
        while(left>0)
        {
            --left;
            swap(nums[0],nums[left]);
            parent = 0;
            child1 =  1;
            child2 =  2;
            while(child1 < left)
            {
                if(child1 < left) child = child1;
                if(child2 < left && nums[child2] > nums[child1]) child = child2;
                if(nums[parent] < nums[child])
                {
                    swap(nums[parent],nums[child]);
                    parent = child;
                    child1 = 2*parent + 1;
                    child2 = 2*parent + 2;
                }
                else break;
            }
        }
        return nums;
    }
```

## 2.6 归并排序
```
#include <stdio.h>
#include <limits.h>

// 分类 -------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- O(nlogn)
// 最优时间复杂度 ---- O(nlogn)
// 平均时间复杂度 ---- O(nlogn)
// 所需辅助空间 ------ O(n)
// 稳定性 ------------ 稳定

void Merge(int A[], int left, int mid, int right)// 合并两个已排好序的数组A[left...mid]和A[mid+1...right]
{
    int len = right - left + 1;
    int *temp = new int[len];       // 辅助空间O(n)
    int index = 0;
    int i = left;                   // 前一数组的起始元素
    int j = mid + 1;                // 后一数组的起始元素
    while (i <= mid && j <= right)
    {
        temp[index++] = A[i] <= A[j] ? A[i++] : A[j++];  // 带等号保证归并排序的稳定性
    }
    while (i <= mid)
    {
        temp[index++] = A[i++];
    }
    while (j <= right)
    {
        temp[index++] = A[j++];
    }
    for (int k = 0; k < len; k++)
    {
        A[left++] = temp[k];
    }
}

void MergeSortRecursion(int A[], int left, int right)    // 递归实现的归并排序(自顶向下)
{
    if (left == right)    // 当待排序的序列长度为1时，递归开始回溯，进行merge操作
        return;
    int mid = (left + right) / 2;
    MergeSortRecursion(A, left, mid);
    MergeSortRecursion(A, mid + 1, right);
    Merge(A, left, mid, right);
}

void MergeSortIteration(int A[], int len)    // 非递归(迭代)实现的归并排序(自底向上)
{
    int left, mid, right;// 子数组索引,前一个为A[left...mid]，后一个子数组为A[mid+1...right]
    for (int i = 1; i < len; i *= 2)        // 子数组的大小i初始为1，每轮翻倍
    {
        left = 0;
        while (left + i < len)              // 后一个子数组存在(需要归并)
        {
            mid = left + i - 1;
            right = mid + i < len ? mid + i : len - 1;// 后一个子数组大小可能不够
            Merge(A, left, mid, right);
            left = right + 1;               // 前一个子数组索引向后移动
        }
    }
}

int main()
{
    int A1[] = { 6, 5, 3, 1, 8, 7, 2, 4 };      // 从小到大归并排序
    int A2[] = { 6, 5, 3, 1, 8, 7, 2, 4 };
    int n1 = sizeof(A1) / sizeof(int);
    int n2 = sizeof(A2) / sizeof(int);
    MergeSortRecursion(A1, 0, n1 - 1);          // 递归实现
    MergeSortIteration(A2, n2);                 // 非递归实现
    printf("递归实现的归并排序结果：");
    for (int i = 0; i < n1; i++)
    {
        printf("%d ", A1[i]);
    }
    printf("\n");
    printf("非递归实现的归并排序结果：");
    for (int i = 0; i < n2; i++)
    {
        printf("%d ", A2[i]);
    }
    printf("\n");
    return 0;
}
```

##2.7 快速排序
```
// 分类 ------------ 内部比较排序
// 数据结构 --------- 数组
// 最差时间复杂度 ---- 每次选取的基准都是最大（或最小）的元素，导致每次只划分出了一个分区，需要进行n-1次划分才能结束递归，时间复杂度为O(n^2)
// 最优时间复杂度 ---- 每次选取的基准都是中位数，这样每次都均匀的划分出两个分区，只需要logn次划分就能结束递归，时间复杂度为O(nlogn)
// 平均时间复杂度 ---- O(nlogn)
// 所需辅助空间 ------ 主要是递归造成的栈空间的使用(用来保存left和right等局部变量)，取决于递归树的深度，一般为O(logn)，最差为O(n)       
// 稳定性 ---------- 不稳定
void Swap(int A[], int i, int j)
{
    int temp = A[i];
    A[i] = A[j];
    A[j] = temp;
}

int Partition(int A[], int left, int right)  // 划分函数
{
    int pivot = A[right];               // 这里每次都选择最后一个元素作为基准
    int tail = left - 1;                // tail为小于基准的子数组最后一个元素的索引
    for (int i = left; i < right; i++)  // 遍历基准以外的其他元素
    {
        if (A[i] <= pivot)              // 把小于等于基准的元素放到前一个子数组末尾
        {
            Swap(A, ++tail, i);
        }
    }
    Swap(A, tail + 1, right);           // 最后把基准放到前一个子数组的后边，剩下的子数组即是大于基准的子数组
                                        // 该操作很有可能把后面元素的稳定性打乱(比如右半边元素完全一样大时)，所以快速排序是不稳定的排序算法
    return tail + 1;                    // 返回基准的索引
}

void QuickSort(int A[], int left, int right)
{
    if (left >= right)
        return;
    int pivot_index = Partition(A, left, right); // 基准的索引
    QuickSort(A, left, pivot_index - 1);
    QuickSort(A, pivot_index + 1, right);
}
```
#3 非比较排序代码
## 3.1 计数排序
通俗地理解，例如有10个年龄不同的人，假如统计出有8个人的年龄不比小明大（即小于等于小明的年龄，这里也包括了小明），那么小明的年龄就排在第8位，通过这种思想可以确定每个人的位置，也就排好了序。当然，年龄一样时需要特殊处理（保证稳定性）：通过反向填充目标数组，填充完毕后将对应的数字统计递减，可以确保计数排序的稳定性。
```
#include<iostream>
using namespace std;

// 分类 ------------ 内部非比较排序
// 数据结构 --------- 数组
// 最差时间复杂度 ---- O(n + k)
// 最优时间复杂度 ---- O(n + k)
// 平均时间复杂度 ---- O(n + k)
// 所需辅助空间 ------ O(n + k)
// 稳定性 ----------- 稳定

const int k = 100;   // 基数为100，排序[0,99]内的整数
int C[k];            // 计数数组

void CountingSort(int A[], int n)
{
    for (int i = 0; i < k; i++)   // 初始化，将数组C中的元素置0(此步骤可省略，整型数组元素默认值为0)
    {
        C[i] = 0;
    }
    for (int i = 0; i < n; i++)   // 使C[i]保存着等于i的元素个数
    {
        C[A[i]]++;
    }
    for (int i = 1; i < k; i++)   // 使C[i]保存着小于等于i的元素个数，排序后元素i就放在第C[i]个输出位置上
    {
        C[i] = C[i] + C[i - 1];
    }
    int *B = (int *)malloc((n) * sizeof(int));// 分配临时空间,长度为n，用来暂存中间数据
    for (int i = n - 1; i >= 0; i--)    // 从后向前扫描保证计数排序的稳定性(重复元素相对次序不变)
    {
        B[--C[A[i]]] = A[i];      // 把每个元素A[i]放到它在输出数组B中的正确位置上
                                  // 当再遇到重复元素时会被放在当前元素的前一个位置上保证计数排序的稳定性
    }
    for (int i = 0; i < n; i++)   // 把临时空间B中的数据拷贝回A
    {
        A[i] = B[i];
    }
    free(B);    // 释放临时空间 
}

int main()
{
    int A[] = { 15, 22, 19, 46, 27, 73, 1, 19, 8 };  // 针对计数排序设计的输入，每一个元素都在[0,100]上且有重复元素
    int n = sizeof(A) / sizeof(int);
    CountingSort(A, n);
    printf("计数排序结果：");
    for (int i = 0; i < n; i++)
    {
        printf("%d ", A[i]);
    }
    printf("\n");
    return 0;
}
```
## 3.2 基数排序
```
#include<iostream>
using namespace std;

// 分类 ------------- 内部非比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- O(n * dn)
// 最优时间复杂度 ---- O(n * dn)
// 平均时间复杂度 ---- O(n * dn)
// 所需辅助空间 ------ O(n * dn)
// 稳定性 ----------- 稳定

const int dn = 3;                // 待排序的元素为三位数及以下
const int k = 10;                // 基数为10，每一位的数字都是[0,9]内的整数
int C[k];

int GetDigit(int x, int d)          // 获得元素x的第d位数字
{
    int radix[] = { 1, 1, 10, 100 };// 最大为三位数，所以这里只要到百位就满足了
    return (x / radix[d]) % 10;
}

void CountingSort(int A[], int n, int d)// 依据元素的第d位数字，对A数组进行计数排序
{
    for (int i = 0; i < k; i++)
    {
        C[i] = 0;
    }
    for (int i = 0; i < n; i++)
    {
        C[GetDigit(A[i], d)]++;
    }
    for (int i = 1; i < k; i++)
    {
        C[i] = C[i] + C[i - 1];
    }
    int *B = (int*)malloc(n * sizeof(int));
    for (int i = n - 1; i >= 0; i--)
    {
        int dight = GetDigit(A[i], d);  // 元素A[i]当前位数字为dight   
        B[--C[dight]] = A[i];           // 根据当前位数字，把每个元素A[i]放到它在输出数组B中的正确位置上
        // 当再遇到当前位数字同为dight的元素时，会将其放在当前元素的前一个位置上保证计数排序的稳定性
    }
    for (int i = 0; i < n; i++)
    {
        A[i] = B[i];
    }
    free(B);
}

void LsdRadixSort(int A[], int n)     // 最低位优先基数排序
{
    for (int d = 1; d <= dn; d++)     // 从低位到高位
        CountingSort(A, n, d);        // 依据第d位数字对A进行计数排序
}

int main()
{
    int A[] = { 20, 90, 64, 289, 998, 365, 852, 123, 789, 456 };// 针对基数排序设计的输入
    int n = sizeof(A) / sizeof(int);
    LsdRadixSort(A, n);
    printf("基数排序结果：");
    for (int i = 0; i < n; i++)
    {
        printf("%d ", A[i]);
    }
    printf("\n");
    return 0;
}

```
## 3.3 桶排序
```
#include<iostream>
using namespace std;

// 分类 ------------- 内部非比较排序
// 数据结构 --------- 数组
// 最差时间复杂度 ---- O(nlogn)或O(n^2)，只有一个桶，取决于桶内排序方式
// 最优时间复杂度 ---- O(n)，每个元素占一个桶
// 平均时间复杂度 ---- O(n)，保证各个桶内元素个数均匀即可
// 所需辅助空间 ------ O(n + bn)
// 稳定性 ----------- 稳定

/* 本程序用数组模拟桶 */
const int bn = 5;    // 这里排序[0,49]的元素，使用5个桶就够了，也可以根据输入动态确定桶的数量
int C[bn];           // 计数数组，存放桶的边界信息

void InsertionSort(int A[], int left, int right)
{
    for (int i = left + 1; i <= right; i++)  // 从第二张牌开始抓，直到最后一张牌
    {
        int get = A[i];
        int j = i - 1;
        while (j >= left && A[j] > get)
        {
            A[j + 1] = A[j];
            j--;
        }
        A[j + 1] = get;
    }
}

int MapToBucket(int x)
{
    return x / 10;    // 映射函数f(x)，作用相当于快排中的Partition，把大量数据分割成基本有序的数据块
}

void CountingSort(int A[], int n)
{
    for (int i = 0; i < bn; i++)
    {
        C[i] = 0;
    }
    for (int i = 0; i < n; i++)     // 使C[i]保存着i号桶中元素的个数
    {
        C[MapToBucket(A[i])]++;
    }
    for (int i = 1; i < bn; i++)    // 定位桶边界：初始时，C[i]-1为i号桶最后一个元素的位置
    {
        C[i] = C[i] + C[i - 1];
    }
    int *B = (int *)malloc((n) * sizeof(int));
    for (int i = n - 1; i >= 0; i--)// 从后向前扫描保证计数排序的稳定性(重复元素相对次序不变)
    {
        int b = MapToBucket(A[i]);  // 元素A[i]位于b号桶
        B[--C[b]] = A[i];           // 把每个元素A[i]放到它在输出数组B中的正确位置上
                                    // 桶的边界被更新：C[b]为b号桶第一个元素的位置
    }
    for (int i = 0; i < n; i++)
    {
        A[i] = B[i];
    }
    free(B);
}

void BucketSort(int A[], int n)
{
    CountingSort(A, n);          // 利用计数排序确定各个桶的边界（分桶）
    for (int i = 0; i < bn; i++) // 对每一个桶中的元素应用插入排序
    {
        int left = C[i];         // C[i]为i号桶第一个元素的位置
        int right = (i == bn - 1 ? n - 1 : C[i + 1] - 1);// C[i+1]-1为i号桶最后一个元素的位置
        if (left < right)        // 对元素个数大于1的桶进行桶内插入排序
            InsertionSort(A, left, right);
    }
}

int main()
{
    int A[] = { 29, 25, 3, 49, 9, 37, 21, 43 };// 针对桶排序设计的输入
    int n = sizeof(A) / sizeof(int);
    BucketSort(A, n);
    printf("桶排序结果：");
    for (int i = 0; i < n; i++)
    {
        printf("%d ", A[i]);
    }
    printf("\n");
    return 0;
}
```

#4 参考链接
(这两篇讲的很好,还有动画,值得一看)
https://www.cnblogs.com/eniac12/p/5329396.html
https://www.cnblogs.com/eniac12/p/5332117.html
#5 leetcode912题排序数组
```
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        //基本的比较排序
        //return BubbleSort(nums);
        //return SelectionSort(nums);
        //return InsertionSort(nums);
        
        //非比较排序,通常主要针对正数
        //return CountingSort(nums);
        //return RadixSort(nums);
        return BucketSort(nums);

//进阶的比较排序
        //return HeapSort(nums);
        //return QuickSort(nums,0,nums.size()-1);
        //return MergeSort(nums,0,nums.size()-1);
        //return MergeSort(nums);
        //return ShellSort(nums);
        
    }
private:
    //交换函数
    void swap(int &a,int &b)
    {
        int temp = a;
        a = b;
        b = temp;
    }
    //划分函数
    int partition(vector<int> &nums,int left,int right)
    {
        //每以都以最右边的数作为基准, 分为两部分
        int pivot = nums[right];
        int tail = left - 1;
        for(int i = left;i<right;++i)
        {
            if(nums[i] < pivot)
            {
                swap(nums[++tail],nums[i]);
            }
        }
        //把基准放到前一个子数组的后边,正是该步造成了快排的不稳定
        swap(nums[++tail],nums[right]);
        //返回基准的索引
        return tail;
    }
    //合并函数,合并[left,mid]和[mid+1,right]
    void merge(vector<int> &nums,int left,int mid,int right)
    {
        if(right<mid || mid<left) return;  
        int len = right - left + 1;
        int *auxiliary = new int[len];
        int i = left,j = mid+1;
        int k = -1;
        while(i<=mid && j<=right)
        {
            if(nums[i] <= nums[j])
            {
                auxiliary[++k] = nums[i++];
            }
            else
            {
                auxiliary[++k] = nums[j++];
            }
        }
        while(i<=mid)
        {
            auxiliary[++k] = nums[i++];
        }
        while(j<=right)
        {
            auxiliary[++k] = nums[j++];
        }
        //拷贝回原数组
        for(k = left;k<left + len;++k)
        {
            nums[k] = auxiliary[k-left];
        }
        delete []auxiliary;
        auxiliary = nullptr;
    }
    //获取数字n的倒数第d位数
    int getDigit(int n,int d)
    {
        int t = d,y=0;
        while(t)
        {
            y = n%10;
            n = n/10;
            --t;
        }
        return y;
    }

//堆排序
    vector<int>& HeapSort(vector<int> &nums)
    {
        int len = nums.size();
        if(len<=1) return nums;
        //从前到后,构造大顶堆
        int left(0),right(0);
        int parent(0),child(0);
        while(right < len-1)
        {
            ++right;
            child = right;
            while(child > 0)
            {
                parent = (child - 1)/2;
                if(nums[parent] < nums[child]) 
                {
                    swap(nums[parent],nums[child]);
                    child = parent;
                }
                else break;
            }
        }
        //依次将大顶堆根节点,放到最后
        left = len;
        int child1,child2;
        while(left>0)
        {
            --left;
            swap(nums[0],nums[left]);
            parent = 0;
            child1 =  1;
            child2 =  2;
            while(child1 < left)
            {
                if(child1 < left) child = child1;
                if(child2 < left && nums[child2] > nums[child1]) child = child2;
                if(nums[parent] < nums[child])
                {
                    swap(nums[parent],nums[child]);
                    parent = child;
                    child1 = 2*parent + 1;
                    child2 = 2*parent + 2;
                }
                else break;
            }
        }
        return nums;
    }
    //快速排序
    vector<int>& QuickSort(vector<int> &nums,int left,int right)
    {
        int len = nums.size();
        if(len<=1) return nums;
        if(left >= right) return nums;
        int pivot_index = partition(nums,left,right);
        QuickSort(nums,left,pivot_index-1);
        QuickSort(nums,pivot_index+1,right);
        return nums;
    }
    //冒泡排序,代码无误,但会超时
    vector<int>& BubbleSort(vector<int> &nums)
    {
        int len = nums.size();
        if(len <= 1) return nums;
        for(int i = 0;i < len-1;++i)
        {
            for(int j = 0;j < len - i - 1;++j)
            {
                if(nums[j]>nums[j+1]) 
                    swap(nums[j],nums[j+1]);
            }
        }
        return nums;
    }
    //选择排序,会超时
    vector<int>& SelectionSort(vector<int> &nums)
    {
        int len = nums.size();
        if(len <= 1) return nums;
        int index = 0;
        for(int i = 0;i<len;++i)
        {
            index = i;
            //寻找最小值,然后将其置于数组前面
            for(int j = i;j<len;++j)
            {
                if(nums[j] < nums[index])
                {
                    index = j;
                }
            }
            swap(nums[i],nums[index]);
        }
        return nums;
    }
    //直接插入排序,超时
    vector<int>& InsertionSort(vector<int> &nums)
    {
        int len = nums.size();
        if(len <= 1) return nums;
        for(int i = 1;i<len;++i)
        {
            int j = 0;
            int curr = nums[i];
            for(j = i-1;j>=0;--j)
            {
                if(nums[j] > curr)
                {
                    nums[j+1] = nums[j];
                }
                else break;
            }
            nums[j+1] = curr;
        }
        return nums;
    }
    //归并递归排序
    vector<int>& MergeSort(vector<int> &nums,int left,int right)
    {
        if(left >= right) return nums;
        int mid = left + (right - left)/2;
        MergeSort(nums,left,mid);
        MergeSort(nums,mid+1,right);
        merge(nums,left,mid,right);
        return nums;
    }
    //归并迭代排序
    vector<int>& MergeSort(vector<int>&nums)
    {
        int len = nums.size();
        int left,mid,right; //不断合并[left,mid]和[mid+1,right]
        //写法一,容易犯错
        // for(int i = 2;i/2-1<len;i*=2)//i代表每个待合并的区间的长度
        // {
        //     left = 0;
        //     while(left + i/2 -1 < len)
        //     {
        //         mid = left + i/2 -1;
        //         right = left + i - 1 < len ? left + i - 1:len-1;
        //         merge(nums,left,mid,right);
        //         left = right + 1; 
        //     }
        // }
        //写法二,推荐
        for(int i = 1;i<len;i*=2) //i代表每个子区间的长度,每两个子区间合并成一个区间
        {
            left = 0;
            while (left + i - 1 < len - 1)              // 后一个子数组存在(需要归并)
            {
                mid = left + i - 1;
                right = mid + i < len ? mid + i : len - 1;// 后一个子数组大小可能不够
                merge(nums, left, mid, right);
                left = right + 1;               // 前一个子数组索引向后移动
            }
        }
        return nums;
    }
    //希尔排序,插入排序的改进,不会超时
    vector<int>& ShellSort(vector<int>& nums)
    {
        int len = nums.size();
        int h = 0;
        while(h<len)
        {
            h = 1 + 5*h;
        }
        while(h>=1)
        {
            for(int i = h;i<len;++i)
            {
                int j = i-h;
                int temp = nums[i];
                while(j>=0 && nums[j] > temp)
                {
                    nums[j+h] = nums[j];
                    j-=h;
                }
                nums[j+h] = temp;
            }
            //必须保证最后一个h为1
            h = (h - 1)/5;
        }
        return nums;
    }
    //计数排序,对于数据范围很大的数组，计数排序需要大量时间和内存, 如果要支持负数,代码要改动,需要找到最大值最小值
    vector<int>& CountingSort(vector<int>& nums)
    {
        int len = nums.size();
        int maxNum = 200; //假定数组中最大的数组为200
        vector<int> countArr(maxNum+1,0);
        vector<int> helpArr(len,0);
        //统计每个数字出现的次数
        for(auto n:nums)
        {
            countArr[n]++;
        }
        //countArr[i]为小于等于i的数字个数
        for(int i = 1;i<=maxNum;++i)
        {
            countArr[i] = countArr[i] + countArr[i-1];
        }
        //因为是正向统计的,所以要保证稳定性,必须反向填充
        for(int i = len -1;i>=0;--i)
        {
            helpArr[--countArr[nums[i]]] = nums[i];
        }
        //拷贝回原数组
        for(int i = 0;i<len;++i)
        {
            nums[i] = helpArr[i];
        }
        return nums;
    }
    //计数排序,依据倒数第d位数字进行计数排序
    void CountingSort(vector<int> &nums,int d)
    {
        int len = nums.size();
        vector<int> countArr(10,0);
        vector<int> helpArr(len,0);
        for(int i = 0;i<len;++i)
        {
            countArr[getDigit(nums[i],d)]++;
        }
        for(int i = 1;i<countArr.size();++i)
        {
            countArr[i] = countArr[i] + countArr[i-1];
        }      
        for(int i = len-1;i>=0;--i)
        {
            helpArr[--countArr[getDigit(nums[i],d)]] = nums[i];
        }
        for(int i = 0;i<len;++i)
        {
            nums[i] = helpArr[i];
        }
    }
    //基数排序,从低位到高位,使用计数排序,负数则需要改代码
    vector<int>& RadixSort(vector<int>& nums)
    {
        int len = nums.size();
        //假设数字最多为4位
        for(int d = 1;d<=4;++d)
        {
            CountingSort(nums,d);
        }
        return nums;
    }

//桶排序,也是只针对正数,且受到数据分布的影响
    vector<int>& BucketSort(vector<int>& nums)
    {   //对[5,1,1,2,0,12,1,13,4,4,12,13,14,51,13,23,51,13,41,0]进行排序
        // 利用计数排序确定各个桶的边界（分桶）,假设bn个桶
        int len = nums.size();
        int bn = 6; //使用除以10来分桶, 因此当最大值不大于等于60时, 六个桶即可
        vector<int> countArr(bn,0);
        vector<int> helpArr(len,0);
        for(int i = 0;i<len;++i)
        {
            countArr[nums[i]/10]++;
        }
        for(int i = 1;i<countArr.size();++i)
        {    //这里countArr[i]被更新为第i个桶里面最后一个元素的排名,countArr[i]-1即为其在数组中的位置
            countArr[i] = countArr[i] + countArr[i-1];
        }      
        for(int i = len-1;i>=0;--i)
        {
            //这里countArr[i]将被更新为第i个桶里的第一个元素的位置
            helpArr[--countArr[nums[i]/10]] = nums[i];
        }
        for(int i = 0;i<len;++i)
        {
            nums[i] = helpArr[i];
        }
        for(int i = 0; i < countArr.size(); i++) // 对每一个桶中的元素应用插入排序
        {
            int left = countArr[i];         // countArr[i]为i号桶第一个元素的位置
            int right = (i == countArr.size()-1 ? len-1 : countArr[i + 1] - 1);// countArr[i+1]-1为i号桶最后一个元素的位置
            if (left < right)        // 对元素个数大于1的桶进行桶内插入排序
            {
                for(int i = left;i<=right;++i)
                {
                    int j;
                    int curr = nums[i];
                    for(j = i-1;j>=0;--j)
                    {
                        if(nums[j] > curr)
                        {
                            nums[j+1] = nums[j];
                        }
                        else break;
                    }
                    nums[j+1] = curr;
                }
            }
        }
        return nums;
    }

};
```

lee-romantic 's Blog

导航

最近发表

友情链接