查缺补漏-排序篇

今天突然被朋友问到: 来来来, 快速手写个 堆排序 看看?
我: 嗯…嗯…嗯??? 好吧, 我只记得好像需要建立一个 最大堆, 然后一个一个取出最大值, 但是 最大堆 的代码又咋写?

那么与其整理一个堆排序, 不如整理所有常见的十种排序算法!
不过这篇文章主要是总结算法的思路以及提供一份 C++ 的实现, 起到一个 助记 的目的

总览

排序算法	平均时间复杂度	最差情况	空间复杂度	排序方式	稳定性
冒泡排序	O(n2)	O(n2)	O(1)	In-place	稳定
插入排序	O(n2)	O(n2)	O(1)	In-place	稳定
选择排序	O(n2)	O(n2)	O(1)	In-place	不稳定
堆排序	O(nlogn)	O(nlogn)	O(1)	In-place	不稳定
快速排序	O(nlogn)	O(n2)	O(logn)	In-place	不稳定
希尔排序	O(nlog2n)	O(n2)	O(1)	In-place	不稳定
归并排序	O(nlogn)	O(nlogn)	O(n)	Out-place	稳定
计数排序	O(n+m)	O(n+m)	O(n+m)	Out-place	稳定
桶排序	O(n)	O(n)	O(m)	Out-place	稳定
基数排序	O(k*n)	O(n2)		Out-place	稳定

• 均按从小到大排列
• k 代表数值中的"数位"个数
• n 代表数据规模
• m 代表数据的最大值减最小值
• 稳定性：稳定排序算法 会让原本有相等键值的纪录维持相对次序。也就是如果一个排序算法是稳定的，当有两个相等键值的纪录 R和 S，且在原本的列表中 R 出现在 S 之前，在排序过的列表中 R 也将会是在S之前。

图表摘自：https://zh.wikipedia.org/wiki/排序算法

冒泡排序

(无序区，有序区)
从无序区通过交换找出最大元素放到有序区前端，直到没有任何一对数字需要比较

冒泡排序思路：

• 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
• 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
• 针对所有的元素重复以上的步骤，除了最后一个。
• 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

// 冒泡排序
void BubbleSort(std::vector<int>& v) {
    int len = v.size();
    for (int i = 0; i < len - 1; ++i)
        for (int j = 0; j < len - 1 - i; ++j)
            if (v[j] > v[j + 1]) 
                std::swap(v[j], v[j + 1]);
}

// 模板实现冒泡排序
template<typename T> //  T 对象需要支持或重载大于 (>) 运算符
void bubble_sort(T arr[], int len) {
    for (int i = 0; i < len - 1; i++)
        for (int j = 0; j < len - 1 - i; j++)
            if (arr[j] > arr[j + 1])
                std::swap(arr[j], arr[j + 1]);
}

通过一次一次的相邻元素比较，将无序区的大数一步一步移动到有序区

插入排序

(有序区，无序区)
把无序区的第一个元素插入到有序区的合适的位置。

插入排序思路：

• 从第一个元素开始，该元素可以认为已经被排序
• 取出下一个元素，在已经排序的元素序列中 从后向前 扫描
• 如果该元素（已排序）大于新元素，将该元素移到下一位置
• 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
• 将新元素插入到该位置后
• 重复步骤2~5

// 插入排序
void InsertSort(std::vector<int>& v)
{
    int len = v.size();
    for (int i = 1; i < len; ++i) {
        int temp = v[i];
        for(int j = i - 1; j >= 0; --j)
        {
            if(v[j] > temp)
            {
                v[j + 1] = v[j];
                v[j] = temp;
            }
            else
                break;
        }
    }
}

// 模板实现
template<typename T>
void InsertSort(T array[], int len) {
    for (int i = 1; i < len; ++i) {
        for (int j = i; j >= 1 && array[j] < array[j - 1]; --j)
            std::swap(array[j], array[j - 1]);
    }
}

从无序区取出一个值，将这个值在有序区从后向前的比较直到插入到正确的位置

选择排序

(有序区，无序区)
在无序区里找一个最小的元素跟在有序区的后面。

选择排序思路：

• 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
• 从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾
• 以此类推，直到所有元素均排序完毕

// 选择排序
void SelectionSort(std::vector<int>& v) {
    int min, len = v.size();
    for (int i = 0; i < len - 1; ++i) {
        min = i;
        for (int j = i + 1; j < len; ++j) {
            if (v[j] < v[min]) {    // 标记最小的
                min = j;
            }
        }
        if (i != min)  // 交换到前面
            std::swap(v[i], v[min]);
    }
}

// 模板实现
template<typename T> 
void Selection_Sort(std::vector<T>& arr) {
    int len = arr.size();
    for (int i = 0; i < len - 1; i++) {
        int min = i;
        for (int j = i + 1; j < len; j++)
            if (arr[j] < arr[min])
                min = j;
        if(i != min)
            std::swap(arr[i], arr[min]);
    }
}

找出无序区的最小值，经过一次交换，移动有序区的最后

不稳定的例子

[5, 8, 5, 2, 9]
// 第一趟就改变了两个 5 的位置
[2, 8, 5, 5, 9]

堆排序

(最大堆，有序区)
从堆顶把根卸出来放在有序区之前，再恢复堆。

以升序排序说明思路:

• 把数组转换成最大堆 (降序的话就是转换成最小堆)
• 重复从最大堆取出数值最大的结点(把根结点和最后一个结点交换，把交换后的最后一个结点移出堆)，并让残余的堆维持最大堆性质。

#include <iostream>
#include <algorithm>
using namespace std;

void max_heapify(int arr[], int start, int end) {
    // 建立父节点指标和子节点指标
    int dad = start;
    int son = dad * 2 + 1;
    while (son <= end) { // 若子节点指标在范围内才做比较
        if (son + 1 <= end && arr[son] < arr[son + 1]) // 先比较两个子节点大小，选择最大的
            son++;
        if (arr[dad] > arr[son]) // 如果父节点大于子节点代表调整完毕，直接跳出函数
            return;
        else { // 否则交换父子内容再继续子节点和孙节点比较
            swap(arr[dad], arr[son]);
            dad = son;
            son = dad * 2 + 1;
        }
    }
}

void heap_sort(int arr[], int len) {
    // 初始化，i从最后一个父节点开始调整
    for (int i = len / 2 - 1; i >= 0; i--)
        max_heapify(arr, i, len - 1);
    // 先将第一个元素和已经排好的元素前一位做交换，再从新调整(刚调整的元素之前的元素)，直到排序完毕
    for (int i = len - 1; i > 0; i--) {
        swap(arr[0], arr[i]);
        max_heapify(arr, 0, i - 1);
    }
}

int main() {
    int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
    int len = (int) sizeof(arr) / sizeof(*arr);
    heap_sort(arr, len);
    for (int i = 0; i < len; i++)
        cout << arr[i] << ' ';
    cout << endl;
    return 0;
}

神似选择排序，类似于利用最大堆，找出 “无序区” 中最大值后放入有序区

不稳定的例子

// 输入
[5, 8, 5, 2, 4]
// 创建最大堆
[8, 5, 5, 2, 4]
// 第一次取出最大值
[4, 5, 5, 2, 8]
// 维护最大堆
[5, 4, 5, 2, 8]
// 5 和 2 需要交换
[2, 4, 5, 5, 8]

快速排序

(小数，基准元素，大数)
在区间中随机挑选一个元素作基准，将小于基准的元素放在基准之前，大于基准的元素放在基准之后，再分别对小数区与大数区进行排序。

快速排序思路：

• 挑选基准值：从数列中挑出一个元素，称为“基准”（pivot），
• 分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成，
• 递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。

// 模板实现快速排序（递归）
template <typename T>
void quick_sort_recursive(T arr[], int start, int end) {
    if (start >= end)
        return;
    T mid = arr[end];
    int left = start, right = end - 1;
    while (left < right) {
        while (arr[left] < mid && left < right)
            left++;
        while (arr[right] >= mid && left < right)
            right--;
        std::swap(arr[left], arr[right]);
    }
    if (arr[left] >= arr[end])
        std::swap(arr[left], arr[end]);
    else
        left++;
    quick_sort_recursive(arr, start, left - 1);
    quick_sort_recursive(arr, left + 1, end);
}
template <typename T> //整数或浮点数皆可使用,若要使用class时必须重载"小于"(<)、"大于"(>)、"不小于"(>=)的运算符
void quick_sort(T arr[], int len) {
    quick_sort_recursive(arr, 0, len - 1);
}

// 模板实现快速排序（迭代）
struct Range {
    int start, end;
    Range(int s = 0, int e = 0) {start = s, end = e;}
};

template<typename T> 
void quick_sort(T arr[], const int len) {
    if (len <= 0) return; //避免len等于负值时错误
    //r[]模拟堆迭,p为数量,r[p++]为push,r[--p]为pop且取得元素
    Range r[len]; int p = 0;
    r[p++] = Range(0, len - 1);
    while (p) {
        Range range = r[--p];
        if(range.start >= range.end) continue;
        T mid = arr[range.end];
        int left = range.start, right = range.end - 1;
        while (left < right) {
            while (arr[left] < mid && left < right) left++;
            while (arr[right] >= mid && left < right) right--;
            std::swap(arr[left], arr[right]);
        }
        if (arr[left] >= arr[range.end])
            std::swap(arr[left], arr[range.end]);
        else
            left++;
        r[p++] = Range(range.start, left - 1);
        r[p++] = Range(left + 1, range.end);
    }
}

一趟找出基准所在的正确位置，然后递归基准左右2侧其他元素

不稳定的例子

// 选择最后一个数 4 作为基准
[5, 8, 5, 2, 4]
// left 指向的 5 和 right 指向的 2 需要交换
[2, 8, 5, 5, 4]

希尔排序

每一轮按照事先决定的间隔进行插入排序，间隔会依次缩小，最后一次一定要是 1。

希尔排序的实质就是 分组 插入排序，是插入排序的一种更高效的改进版本。

希尔排序思路：

• 先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序
• 依次 缩减增量 再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。

template<typename T>
void shell_sort(T array[], int length) {
    int h = 1;
    while (h < length / 3) {
        h = 3 * h + 1;
    }
    while (h >= 1) {
        for (int i = h; i < length; i++) {
            for (int j = i; j >= h && array[j] < array[j - h]; j -= h)
                std::swap(array[j], array[j - h]);
        }
        h = h / 3;
    }
}

不稳定的例子

// 基础输入
[5, 8, 5, 2, 4, 6]
// 初始步长为 4 
// 第一组 [5,4],  第二组 [8,6],  第三组 [5], 第四组 [2]
// 第一组第二组按照插入排序思路交换位置
[4, 6, 5, 2, 5, 8]

按照一定间隔分组，分组内的最后一个元素按照插入排序的思路从后向前插入到合适位置，然后逐渐缩小间隔

归并排序

把数据分为两段，从两段中逐个选最小的元素移入新数据段的末尾。可从上到下或从下到上进行。

递归法（Top-down）

• 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
• 设定两个指针，最初位置分别为两个已经排序序列的起始位置
• 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
• 重复步骤3直到某一指针到达序列尾
• 将另一序列剩下的所有元素直接复制到合并序列尾

void Merge(vector<int> &Array, int front, int mid, int end) {
    // preconditions:
    // Array[front...mid] is sorted
    // Array[mid+1 ... end] is sorted
    // Copy Array[front ... mid] to LeftSubArray
    // Copy Array[mid+1 ... end] to RightSubArray
    vector<int> LeftSubArray(Array.begin() + front, Array.begin() + mid + 1);
    vector<int> RightSubArray(Array.begin() + mid + 1, Array.begin() + end + 1);
    int idxLeft = 0, idxRight = 0;
    LeftSubArray.insert(LeftSubArray.end(), numeric_limits<int>::max());
    RightSubArray.insert(RightSubArray.end(), numeric_limits<int>::max());
    // Pick min of LeftSubArray[idxLeft] and RightSubArray[idxRight], and put into Array[i]
    for (int i = front; i <= end; i++) {
        if (LeftSubArray[idxLeft] < RightSubArray[idxRight]) {
            Array[i] = LeftSubArray[idxLeft];
            idxLeft++;
        } else {
            Array[i] = RightSubArray[idxRight];
            idxRight++;
        }
    }
}

void MergeSort(vector<int> &Array, int front, int end) {
    if (front >= end)
        return;
    int mid = front + (end - front) / 2;
    MergeSort(Array, front, mid);
    MergeSort(Array, mid + 1, end);
    Merge(Array, front, mid, end);
}

迭代法（Bottom-up）
原理如下（假设序列共有 n 个元素）：

• 将序列每相邻两个数字进行归并操作，形成 ceil(n/2) 个序列，排序后每个序列包含两/一个元素
• 若此时序列数不是1个则将上述序列再次归并，形成 ceil(n/4) 个序列，每个序列包含四/三个元素
• 重复步骤2，直到所有元素排序完毕，即序列数为1

template<typename T> // 整数或浮点数皆可使用,若要使用 class 时必须重载"小于"(<)的运算符
void merge_sort(T arr[], int len) {
    T *a = arr;
    T *b = new T[len];
    for (int seg = 1; seg < len; seg += seg) {
        for (int start = 0; start < len; start += seg + seg) {
            int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);
            int k = low;
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            while (start1 < end1 && start2 < end2)
                b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
            while (start1 < end1)
                b[k++] = a[start1++];
            while (start2 < end2)
                b[k++] = a[start2++];
        }
        // 交换指针，将这一次合并的结果 b 执行下一次 a 数组中，下一次保存结果指向这一次的 a
        T *temp = a;
        a = b;
        b = temp;
    }
    // 因为交换过的指针，最后的结果可能在 `b` 或者在 `a` 上，需要做一次额外判断和赋值
    if (a != arr) {
        for (int i = 0; i < len; i++)
            b[i] = a[i];
        b = a;
    }
    delete[] b;
}

从两个排好序的序列中取出各自最小的数比较，取出更小值放入新的队列，然后重新从这两个序列中取最小数比较

计数排序

统计小于等于该元素值的元素的个数i，于是该元素就放在目标数组的索引i位（i≥0）。

计数排序思路：

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

// 计数排序
void CountSort(vector<int>& vecRaw, vector<int>& vecObj)
{
    // 确保待排序容器非空
    if (vecRaw.size() == 0)
        return;

    // 使用 vecRaw 的最大值 + 1 作为计数容器 countVec 的大小
    int vecCountLength = (*max_element(begin(vecRaw), end(vecRaw))) + 1;
    vector<int> vecCount(vecCountLength, 0);

    // 统计每个键值出现的次数
    for (int i = 0; i < vecRaw.size(); i++)
        vecCount[vecRaw[i]]++;

    // 后面的键值出现的位置为前面所有键值出现的次数之和
    for (int i = 1; i < vecCountLength; i++)
        vecCount[i] += vecCount[i - 1];

    // 将键值放到目标位置
    for (int i = vecRaw.size(); i > 0; i--) // 此处逆序是为了保持相同键值的稳定性
        vecObj[--vecCount[vecRaw[i - 1]]] = vecRaw[i - 1];
}

很巧妙的思路，用一个新的数组的下标来表示值，对应位置保存存在几个值，计算次数和是为了得到这个数在新数值中的位置，反向填充保持键值的稳定性

桶排序

将值为 i 的元素放入i号桶，最后依次把桶里的元素倒出来。

桶排序思路：

• 设置一个定量的数组当作空桶子。
• 寻访序列，并且把项目一个一个放到对应的桶子去。
• 对每个不是空的桶子进行排序。
• 从不是空的桶子里把项目再放回原来的序列中。

// 假设数据分布在[0，100)之间，每个桶内部用链表表示，在数据入桶的同时插入排序。然后把各个桶中的数据合并。
const int BUCKET_NUM = 10;

struct ListNode{
    explicit ListNode(int i=0):mData(i),mNext(NULL){}
    ListNode* mNext;
    int mData;
};

ListNode* insert(ListNode* head,int val){
    ListNode dummyNode;
    ListNode *newNode = new ListNode(val);
    ListNode *pre,*curr;
    dummyNode.mNext = head;
    pre = &dummyNode;
    curr = head;
    while(NULL!=curr && curr->mData<=val){
        pre = curr;
        curr = curr->mNext;
    }
    newNode->mNext = curr;
    pre->mNext = newNode;
    return dummyNode.mNext;
}


ListNode* Merge(ListNode *head1,ListNode *head2){
    ListNode dummyNode;
    ListNode *dummy = &dummyNode;
    while(NULL!=head1 && NULL!=head2){
        if(head1->mData <= head2->mData){
            dummy->mNext = head1;
            head1 = head1->mNext;
        }else{
            dummy->mNext = head2;
            head2 = head2->mNext;
        }
        dummy = dummy->mNext;
    }
    if(NULL!=head1) dummy->mNext = head1;
    if(NULL!=head2) dummy->mNext = head2;
    
    return dummyNode.mNext;
}

void BucketSort(int n,int arr[]){
    vector<ListNode*> buckets(BUCKET_NUM,(ListNode*)(0));
    for(int i=0;i<n;++i){
        int index = arr[i]/BUCKET_NUM;
        ListNode *head = buckets.at(index);
        buckets.at(index) = insert(head,arr[i]);
    }
    ListNode *head = buckets.at(0);
    for(int i=1;i<BUCKET_NUM;++i){
        head = Merge(head,buckets.at(i));
    }
    for(int i=0;i<n;++i){
        arr[i] = head->mData;
        head = head->mNext;
    }
}

基数排序

一种多关键字的排序算法，可用桶排序实现。

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

基数排序思路：

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

int maxbit(int data[], int n) //辅助函数，求数据的最大位数
{
    int maxData = data[0];        ///< 最大数
    /// 先求出最大数，再求其位数，这样有原先依次每个数判断其位数，稍微优化点。
    for (int i = 1; i < n; ++i)
    {
        if (maxData < data[i])
            maxData = data[i];
    }
    int d = 1;
    int p = 10;
    while (maxData >= p)
    {
        //p *= 10; // Maybe overflow
        maxData /= 10;
        ++d;
    }
    return d;
}

void radixsort(int data[], int n) //基数排序
{
    int d = maxbit(data, n);
    int *tmp = new int[n];
    int *count = new int[10]; //计数器
    int i, j, k;
    int radix = 1;
    for(i = 1; i <= d; i++) //进行d次排序
    {
        for(j = 0; j < 10; j++)
            count[j] = 0; //每次分配前清空计数器
        for(j = 0; j < n; j++)
        {
            k = (data[j] / radix) % 10; //统计每个桶中的记录数
            count[k]++;
        }
        for(j = 1; j < 10; j++)
            count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶
        for(j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中
        {
            k = (data[j] / radix) % 10;
            tmp[count[k] - 1] = data[j];
            count[k]--;
        }
        for(j = 0; j < n; j++) //将临时数组的内容复制到data中
            data[j] = tmp[j];
        radix = radix * 10;
    }
    delete []tmp;
    delete []count;
}

小结

每一种算法涉及的知识都很多，我这里总结更大的目的是 助记 ，也可以时不时再回味一下代码，再思考一下实现思路，更强化记忆~