Dreamside Maroon

保持热爱，奔赴山海

0%

算法-十大排序

发表于 更新于
本文字数： 11k 阅读时长 ≈ 10 分钟

排序算法是《数据结构与算法》最基本的算法之一。常见的十大排序算法主要有：冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序。

1、冒泡排序

1.1 算法步骤

冒泡排序的步骤如同其名字一样，“冒泡冒泡”，即一直到水面上冒出泡，那么怎么样区分谁去冒泡和怎么冒泡呢？这里，怎么区分冒泡原则很重要，具体表现为是从小到大排序还是从大到小排序。

以从小到大排序为例，冒泡排序的步骤就是先比较目前相邻的元素。如果第一个比第二个大，就交换他们两个。对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。逐步做完之后，最后的元素会是最大的数。接下来的步骤比较就抛开最后的元素再次进行冒泡排序，持续进行上面的步骤，直到最后没有任何一对数字需要比较为止。

1.2 C++算法实现

vector<int> bubble_sort(vector<int>& nums) {
    bool swapped;// 定义一个变量去判别这一轮是否排序过，如果没有排序过，那么代表已经排序结束
    for (int i = 0; i < nums.size() - 1; i++) {//需要排序n-1轮
        swapped = false;// 每一轮交换之前先初始化
        // 排了i次了，前i个数不用排了
        for (int j = 0; j < nums.size() - 1 - i; j++) {
            if (nums[j] > nums[j + 1]) {
                swap(nums[j], nums[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) {
            break;
        }
    }
    return nums;
}

1.3 复杂度分析

  • 该算法的最好情况是当输入的数据刚好是我们需要的排序结果时（即正序），那么此时我们就不需要额外去交换了，这个时候只需要遍历一遍元素，确保排序结果是我们需要的，时间复杂度是**O(n)。该算法的坏的结果是当输入的数据刚好是我们需要的排序结果的倒序时（即倒序），那么此时每次排序都需要我们去不停地交换，最后交换了n-1次之后，排序结束，交换次数是n-1+n-2+n-3+…+1,此刻的时间复杂度为O(n^2)**。平均是O(n^2)

  • 空间复杂度：O(1)

1.4 总结

冒泡排序是一种简单直观的排序算法，它重复地走访过要排序地数列，一次比较两个元素，按照顺序的原则把数据进行交换，直到没有需要交换的元素为止。

2、选择排序

2.1 算法步骤

选择排序其实重在选择和选择规则，如果是从小到大排序，可以选择末尾的值作为我们需要的值，然后依次遍历前面的值，如果有比末尾大的值就进行交换，一直遍历n-1次。是不是有种冒泡排序的感觉，但是又不一样。
当然也可以选择以最首的值作为对象，然后依次遍历后面的值，如果有比当前对象更小的值，那么就进行交换。

2.2 C++算法实现

void selection_sort(vector<int>&nums, int n) {
    int mid;//当前的比较对象
    for (int i = 0; i < n - 1; i++) { //下面用到了j-1，因此是从1开始，反正理论上就是要排n-1轮
        mid = i;
        for （int j = i + 1; j < n; j++）{
            if (nums[j] < nums[mid]) {
                mid = j;
 			}
        }
         swap(nums[mid], nums[i]);
    }
}

2.3 复杂度分析

  • 不论如何，都进行了n-1轮遍历，比较了n-1+n-2+…+1次，最好和最坏的情况都是**O(n^2)**。

  • 空间复杂度：O(1)

2.4 总结

选择排序由于时间复杂度的限制，数据规模越小越好。

3、插入排序

3.1 算法步骤

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

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。

从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

3.2 C++代码实现

void insertion_sort(vector<int>& nums, int n) {
    for(int i = 1; i < n; i++){
        int key = nums[i];
        int j = i-1;
        while((j >= 0) && (key < nums[j])){//从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。
        	nums[j+1] = nums[j];
       		j--;
        }
    	nums[j+1] = key;
    }
}

3.3 复杂度分析

同冒泡排序。

3.4 总结

插入排序的原理其实和整理扑克牌的原理是一致的。

4、希尔排序

4.1 算法步骤

选择一个增量序列t1，t2，……，tk，其中 ti > tj, tk = 1；按增量序列个数 k，对序列进行 k 趟排序；每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。具体的流程可以看https://www.runoob.com/data-structures/shell-sort.html

4.2 C++代码实现(不是很懂为啥是3)

void shell_sort(vector<int>& nums, int n) {
    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 && nums[j] < nums[j-h]; j -= h) {
                swap(nums[j], nums[j-h]);
            }
        }
        h = h /3;
    }
}

4.3 复杂度分析

  • 时间复杂度：O(n(log^2n))
  • 空间复杂度：O(1)

4.4 总结

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录”基本有序”时，再对全体记录进行依次直接插入排序。希尔排序时间复杂度是 O(n^(1.3-2))，空间复杂度为常数阶 O(1)。希尔排序没有时间复杂度为 O(n(logn)) 的快速排序算法快 ，因此对中等大小规模表现良好，但对规模非常大的数据排序不是最优选择，总之比一般 O(n^2 ) 复杂度的算法快得多。

5、归并排序

5.1 算法步骤

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

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

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

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

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

5.2 C++代码实现

//递归版本
void merge_sort(vector<int>& nums, int l, int r, vector<int>& temp) {
    if (l + 1 >= r) {//此时只有一个元素，不能再继续划分
        return;
    }
    //divide
    int m = l + (r - l) / 2;
    //左边排序
    merge_sort(nums, l, m, temp);
    //右边排序
    merge_sort(nums, m, r, temp);
    //conquer
    int p = l, q = m, i = l;
    while (p < m || q < r) {//左边的边界条件和右边的边界条件
        if (q >= r || (p < m && nums[p] <= nums[q])) {//右边全部归并结束或者左边的小于右边的值
            temp[i++] = nums[p++];
        }
        else {//除了这个之外
            temp[i++] = nums[q++];
        }
    }
    for (i = l; i < r; ++i) {
        nums[i] = temp[i];//临时数组覆盖当前数组
    }
}

5.3 复杂度分析

  • 时间复杂度：O(nlogn),每一层是n，logn层
  • 空间复杂度：用了一个临时数组O(n)

5.4 总结

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：

  • 自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；
  • 自下而上的迭代；
    非递归版可以继续练习一下

6、快速排序

6.1 算法步骤

快速排序的最坏运行情况是 O(n²)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。
快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。

  • 从数列中挑出一个元素，称为 “基准”（pivot）;

  • 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；

  • 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

6.2 C++代码实现

void quick_sort(vector<int>& nums, int l, int r) {
    if (l + 1 >= r) {//只有一个元素时，不用再排序
        return;
    }
    int first = 1, last = r - 1, key = nums[first];//key是一个枢纽pivot
    while (first < last) {
        // 找出分割枢纽
        //后面的都比它大
        while (first < last && nums[last] >= key) {
            --last;
        }
        nums[first] = nums[last];
        //前面的都比它小
        while (first < last && nums[first] >= key) {
            ++first;
        }
        nums[last] = nums[first];

    }
    nums[first] = key;//此时key处于了正确的位置，前面的都比它小，后面的都比它大
    
    //分而治之 
    quick_sort(nums, l ,first);
    quick_sort(nums, first + 1, r);
}

6.3 复杂度分析

  • 时间复杂度，最好是排n次，每次里面都排好了，logn最好是O(nlogn),最坏是进行O(n^2)次比较
  • 空间复杂度：O(1)

6.4 总结

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

7、堆排序

7.1 算法步骤

  • 创建一个堆 H[0……n-1]；

  • 把堆首（最大值）和堆尾互换；

  • 把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；

  • 重复步骤 2，直到堆的尺寸为 1。

7.2 C++代码

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

//堆的结构其实是一个完整二叉树，但不一定是完美二叉树
//正因为如此，建议堆的时候，dad和son的指标才能确定

//建立大顶堆
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;
}

7.3 复杂度分析

  • 时间复杂度，最好是排n次，每次里面都排好了，logn最好是O(nlogn)
  • 空间复杂度：O(1)

7.4 总结

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

  • 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
  • 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

堆排序的平均时间复杂度为 Ο(nlogn)。

堆排序的思想是根据堆这种数据结构的特性，进行排序，先建立起堆，每次利用堆的特征进行排序，如大顶堆的堆头是整个堆里面最大的值，每次都将堆与堆的最深层的最右边交换，交换完之后断开连接进而重新建立起堆，依次这么进行，直到最后排序结束。

8、计数排序

8.1 算法步骤

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

8.2 C++总结

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

void counting_sort(int arr[], int len) {
    if (len < 1) return;

    int max = arr[0];//记录数组的最大值
    int min = arr[0];//记录数组的最小值

    for (int i = 1; i < len; i++) {
        if (arr[i] > max) max = arr[i];
        if (arr[i] < min) min = arr[i];
    }

    //分配一个长度为max-min+1的数组存储计数，并且将其初始化为0
    int* coutarr = new int[max - min + 1];
    memset(coutarr, 0, len);
    for (int i = 0; i < len; i++) {
        coutarr[arr[i] - min]++;//统计值数组中各个值的元素个数
    }

    int sum = 0;
    for (int i = 0; i < max - min + 1; i++) {//统计数组做变形，后面的元素等于前面元素的和
        sum += coutarr[i];
        coutarr[i] = sum;
    }

    int* sortarr = new int[len];
    memset(sortarr, 0, len);
    for (int i = len - 1; i >= 0; i--) {//倒序遍历原始数组，从统计数组中找到正确位置
        sortarr[coutarr[arr[i] - min] - 1] = arr[i];//读取每一个数
        coutarr[arr[i] - min]--;//对应该数的值的个数-1
    }
    delete coutarr;
    for (int i = 0; i < len; i++) {
        cout << sortarr[i] << ' ';
    }
    cout << endl;
}

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);

    counting_sort(arr, len);
    
    return 0;
}

8.3 复杂度分析

  • 时间复杂度：只需要遍历原始数组和计数数组的长度，所以是O(n+k)
  • 空间复杂度：用了计数数组，因此空间复杂度为O（k）

8.4 总结

计数排序是一种通过计数数组计数而不是比较来进行排序,适用于范围较小的整数序列

9、桶排序

9.1 算法步骤

其实就是计数排序的思路，但此时的计数排序中的计数方式变成了计函数

9.2 C++代码

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

void bucket_sort(int arr[], int len) {
    int size = len;//建立桶的个数
    vector<int> buckets[size];//有size个数据，就分配size个桶
    for (int i = 0; i < len; i++) {
        int bi = size * arr[i];//元素arr[i]的桶编号
        buckets[bi].push_back(arr[i]);//将元素ar[i]压入桶中
    }
    for (int i = 0; i < size; i++)
        sort(buckets[i].begin(), buckets[i].end());//桶内排序
    int idx = 0;//指向数组A的下标
    for (int i = 0; i < size; i++) {//遍历桶
        for (int j = 0; j < buckets[i].size(); j++) {//遍历桶内元素
            arr[idx++] = buckets[i][j];
        }
    }
}

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

9.3 复杂度分析

  • 时间复杂度：只需要遍历原始数组和计数数组的长度，所以是O(n+k)，复杂度都是平均的，但是最坏的情况，由于桶内采用了快排，所以是O（n^2）
  • 空间复杂度：用了计数数组，因此空间复杂度为O（k）

9.4 总结

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

  • 在额外空间充足的情况下，尽量增大桶的数量
  • 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中
    同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

10、基数排序

10.1 算法步骤

  • 确定数组中的最大元素有几位(MAX)(确定执行的轮数)
  • 创建0-9个桶（桶的底层是队列），因为所有的数字元素都是由0-9的十个数字组成
  • 依次判断每个元素的个位、十位至MAX位，存入对应的桶中，出队，存入原数组；直到MAX轮结束输出数组

10.2 C++代码

#include<iostream>
using namespace std;

/*
 * 获取数组a中最大值
 *
 * 参数说明：
 *     a -- 数组
 *     n -- 数组长度
 */
int get_max(int a[], int n) {
    int max;
    
    max = a[0];
    for (int i = 1; i < n; i++) {
        if (a[i] > max) {
            max = a[i];
        }
    }
    return max;
}


/*
 * 对数组按照"某个位数"进行排序(桶排序)
 *
 * 参数说明：
 *     a -- 数组
 *     n -- 数组长度
 *     exp -- 指数。对数组a按照该指数进行排序。
 *
 * 例如，对于数组a={50, 3, 542, 745, 2014, 154, 63, 616}；
 *    (01) 当exp=1表示按照"个位"对数组a进行排序
 *    (02) 当exp=10表示按照"十位"对数组a进行排序
 *    (03) 当exp=100表示按照"百位"对数组a进行排序
 *    ...
 */
void count_sort(int a[], int n, int exp) {
    int output[100]; //存储"被排序数据"的临时数组(这里需要定义一个足够大的数)
    int buckets[10] = { 0 };

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

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

    //将数据存储到临时数组output[]中
    for (int i = n - 1; i >= 0; i--) {
        output[buckets[(a[i] / exp) % 10] - 1] = a[i];
        buckets[(a[i] / exp) % 10]--;
    }
    //将排序好的数据赋值给a[]
    for (int i = 0; i < n; i++) {
        a[i] = output[i];
    }
}

/*
 * 基数排序 Radix sort
 * 参数说明：a:数组，n：数组长度
 */
int main() {

    int a[] = { 50, 3, 542, 745, 2014, 154, 63, 616 };
    int n = (int)sizeof(a) / sizeof(*a);
    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);
    }


    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
    cout << endl;
    system("pause");
    return 0;
}

10.3 复杂度分析

  • 时间复杂度：O(N*k),该算法所花费的时间基本就是把元素分配到桶里和把元素从桶里串起来；

    把元素从桶里串起来：这个计算有点麻烦，看似两个循环，其实第二循环是根据桶里面的元素而定的，可以表示为：k×buckerCount；其中 k 表示某个桶中的元素个数，buckerCount 则表示存放元素的桶个数；有几种特殊情况：第一、所有的元素都存放在一个桶内：k = length，buckerCount = 1；第二、所有的元素平均分配到每个桶中：k = length/ bukerCount，buckerCount = 10；（这里已经固定了10个桶）所以平均情况下收集部分所花的时间为：length （也就是元素长度 n）
    综上所述：时间复杂度为：posCount * (length + length) ；其中 posCount 为数组中最大元素的最高位数；简化下得：O(N*k)，其中k为常数（桶数），n为元素个数

  • 空间复杂度：O(N), 该算法的空间复杂度就是在分配元素时，使用的桶空间；所以空间复杂度为：O（10 × length）= O（length）

10.4 总结

基数排序有两种方法：

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

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

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

参考资料

1、https://github.com/hustcc/JS-Sorting-Algorithm
2、菜鸟教程-十大经典排序算法
3、https://zhuanlan.zhihu.com/p/42586566

-------------本文结束感谢您的阅读-------------

欢迎关注我的其它发布渠道