【排序算法略解】(十种排序的稳定性,时间复杂度以及实现思想)(含代码)(完工于2023.8.3)

这篇具有很好参考价值的文章主要介绍了【排序算法略解】(十种排序的稳定性,时间复杂度以及实现思想)(含代码)(完工于2023.8.3)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


注:以下排序默认为升序排序。

稳定性:指的是排序的过程中是否会改变多个相同的值的相对次序,如果会改变则是不稳定的。

1、冒泡排序/选择排序/插入排序

冒泡排序,选择排序,插入排序是最简单的排序方法。

冒泡排序(Bubble Sort)

排序方法:扫描的过程中,比较相邻两个数的大小关系,如果存在逆序就交换这两个数,这样每趟可以保证最后一个数,也就是最大的数,一步步交换上去,如气泡上浮一样,回归到正确的位置。

时间复杂度: O ( n 2 ) O(n^2) O(n2)

稳定性:稳定。对于两个相同的值,不会发生交换。

代码实现:文章来源地址https://www.toymoban.com/news/detail-638668.html

int arr[] = {0, 2, 9, 3, 5, 7, 8, 1, 4, 6};

//arr是被排序数组,start是起点坐标,end是终点坐标(闭区间)

void sort(int* arr, int start, int end) {
    int n = end - start + 1;
    //只需要排序n - 1次
    for (int i = 1; i < n; i++) {
        //倒数i - 1个数已经归位不必交换
        for (int j = start; j <= end - i; j++) {
            //出现逆序
            if (arr[j + 1] < arr[j]) {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
    }
}

选择排序(Selection Sort)

排序方法:扫描的过程中,每次选择剩余未排序的数组中选择最小值与未排序部分第一个值进行交换,从而使得未排序部分的第一个位置得到正确的值。

时间复杂度: O ( n 2 ) O(n^2) O(n2)

稳定性:不稳定。例如,3 3 2 → 一次交换 \stackrel{一次交换}{\rightarrow} 一次交换 2 3 3 可以发现两个3的位置改变了。

代码实现:

int arr[] = {0, 2, 9, 3, 5, 7, 8, 1, 4, 6};

//arr是被排序数组,start是起点坐标,end是终点坐标(闭区间)

void sort(int* arr, int start, int end) {
    int n = end - start + 1;
    //只需要排序n - 1次
    for (int i = 1; i < n; i++) {
        int min_element_positon = start + i - 1;
        for (int j = start + i - 1; j <= end; j++) {
            if (arr[j] < arr[min_element_positon]) {
                min_element_positon = j;
            }
        }
        int tmp = arr[min_element_positon];
        arr[min_element_positon] = arr[start + i - 1];
        arr[start + i - 1] = tmp;
    }
}

插入排序(Insertion Sort)

排序方法:每次取未排序部分的数组,将其插入到前半已经排序后的数组内,类似打牌时整理牌序的方法,插入到前面整理好的数组内的合适的位置。

时间复杂度: O ( n 2 ) O(n^2) O(n2)

稳定性:稳定。相同的值符合大于等于关系,并不会插入到相同值的前面。

代码实现:

int arr[] = {0, 2, 9, 3, 5, 7, 8, 1, 4, 6};

//arr是被排序数组,start是起点坐标,end是终点坐标(闭区间)

void sort(int* arr, int start, int end) {
    int n = end - start + 1;
    //只需要排序n - 1次
    for (int i = 1; i < n; i++) {
        int key = arr[start + i];
        int j = start + i;
        while (j >= start) {
            if (j == start) break; // 如果是最小值,会一直到开头
            if (j == start + i && key >= arr[j - 1]) break; //如果是最大值
            if (key >= arr[j - 1] && key <= arr[j + 1]) break;//在中间合适的值
            arr[j] = arr[j - 1];
            j--;
        }
        arr[j] = key;
    }
}

2、希尔排序(Shell’s Sort)

排序方法:每次选择特定的增量,对这个增量下的子序列进行直接插入排序。

最好时间复杂度: O ( n log ⁡ n ) O(n\log{n}) O(nlogn)

最坏时间复杂度: O ( n n ) O(n\sqrt{n}) O(nn )【选取d={1, 2, 4, 8, …2k}大到小】,$O(n\log{n}\log{n})$【选取2m*2^n次大到小的集合】

关于时间复杂度的证明:主要考虑对于两个不同增量的序列的插入排序,两者的结果都是可以互相继承的;以及相关其他复杂度的 分析

稳定性:不稳定,因为不同序列相同的值的位置可能改变。

代码实现:

int arr[] = {0, 2, 9, 55, 54, 7, 8, 1, 40, 600};

void sort(int* arr, int start, int end) {
    int n = end - start + 1;
    for (int d = n / 2; d >= 1; d /= 2) {
        //倍减
        for (int i = d; i < n; i++) {//一共进行n - d次插入
            int tmp = arr[start + i];//取无序部分第一个数进行插排
            int j = i - d;
            for (; j >= 0 && tmp < arr[j + start]; j -= d) {
                arr[j + d + start] = arr[j + start];
            }
            //如果前面有比最后一个数小的,就腾出一位
            //实际上会多减一次,要补回d
            arr[j + d + start] = tmp;
            
        }
    }
}

3、快速排序(Quick Sort)

排序方法:“挖坑填数”,取出需要排序区间的第一个数作为基数,利用双指针方法,整理当前数组,使得这个数组成为坑左边均为小于等于基数的数,坑右边都是大于等于基数的数,最后把基数填入这个位置,此处基数回到正确的位置。然后分成两个区间,递归分治,重复上述操作。

一般时间复杂度: O ( n log ⁡ ( n ) ) O(n\log(n)) O(nlog(n))

最坏时间复杂度(例如数组已经有序的时候): O ( n 2 ) O(n^2) O(n2)

稳定性:不稳定。例如 6 3 3 经过一次的填坑得到 3 3 _ 3的次序发生了改变。

代码实现:

int arr[] = {0, 2, 9, 3, 5, 7, 8, 1, 4, 6};

//arr是被排序数组,start是起点坐标,end是终点坐标(闭区间)

void sort(int* arr, int start, int end) {
    if (start >= end) { //如果只有1个元素,或者没有元素就不需要排序
        return;
    }//目的是把数组整理成一半小于等于基数,一半大于等于基数,中间是坑位的样子
    int l = start, r = end, key = arr[l];//取第一个元素作为基数
    while (l < r) {
        while (l < r && arr[r] >= key) {
            r--;//从后往前找到第一个小于key的值
        }
        if (l < r) {//如果相遇则说坑位左右两侧都已经整理完毕
            arr[l++] = arr[r];
        }
        while (l < r && arr[l] <= key) {
            l++;//从前往后找到第一个大于key的值
        }
        if (l < r) {
            arr[r--] = arr[l];
        }
    }
    arr[l] = key;
    sort(arr, start, l - 1);
    sort(arr, l + 1, end);
}

4、堆排序(Heap Sort)

排序方法:利用标号关系构造一个无序堆,通过堆调整,形成一个有序的大顶堆。每次取堆顶的数和未排序数的最大标号,即堆底最后一个叶子交换位置,此时,最后一个叶子是当前未排序的数中最大的数,已经回到正确的位置,离开堆。之后,调整堆,维护大顶堆的性质,等待下一次交换。

关于堆调整:如果父节点最大不交换,如果父节点不是最大,则要交换左右儿子中较大的一个,交换后,可以使得原来那个较小儿子所在的子树的父节点变成较大儿子,这样保证较小儿子的子树符合二叉堆的性质,并且根节点也符合条件,但是,可能会影响较另外子数成堆,所以,为了维护堆的性质,要一直交换下去,直到符合性质,最坏可能要交换到叶子,但是这样的交换不超过 log ⁡ n \log{n} logn次,因为每次交换都可以使得近似大小的另一子树符合堆的性质,需要维护的堆的性质的节点数倍减,直至单个节点,单个节点符合堆的性质。

时间复杂度: O ( n log ⁡ n ) O(n\log{n}) O(nlogn)

时间复杂度分析:开始的堆调整 n n n次,之后每个数取出后的堆调整的交换次数取决于二叉堆的深度,由于二叉堆是一个完全二叉树,所以深度不超过 log ⁡ n \log{n} logn所以一趟的交换次数不超过 log ⁡ n \log{n} logn次。

稳定性:不稳定。如果是全相等的堆,仍然会进行交换。

代码实现:

int arr[] = {0, 2, 9, 3, 5, 7, 8, 1, 4, 6};

//arr是被排序数组,start是起点坐标,end是终点坐标(闭区间)
//堆调整函数,维护当前子树堆的性质
void heap_modify(int* arr, int root_id, int last_id, int start) {
    int tmp = arr[root_id + start];
    for (int i = 2 * root_id + 1; i <= last_id; i = i * 2 + 1) {
        //枚举左儿子
        if (i < last_id && arr[i + start] < arr[i + 1 + start]) {
            //如果有右儿子,并且右儿子更大,取右儿子进行比较
            //否则取左儿子
            i++;
        }
        //较大的儿子和根节点进行比较,都是和原来根节点交换的数进行比较
        if (arr[i + start] > tmp) {
            arr[root_id + start] = arr[i + start];
            root_id = i;//较大的儿子的id是根节点的下一个id
        }
        else {//如果较大的儿子不大于根节点,不必调整下去
            break;
        }
    }
    arr[root_id + start] = tmp;//填坑
}
void sort(int* arr, int start, int end) {
    //构造有序堆
    for (int i = end; i >= start; i--) {
        //映射成0~n的标号,倒着整理
        heap_modify(arr, i - start, end - start, start);
    }
    int n = end - start + 1;
    for (int i = 1; i < n; i++) {//n - 1趟
        int tmp = arr[start];
        arr[start] = arr[end - i + 1];//与当前无序数组最大下标交换
        arr[end - i + 1] = tmp;
        heap_modify(arr, 0, end - i - start, start);//维护堆的性质
    }
}

5、归并排序(Merge Sort)

排序方法:利用分治的思想,将数组不断划分,到单个数,然后递归合并起来,利用双指针的手法,将两个有序数组合并成一个有序的数组。

时间复杂度: O ( n log ⁡ n ) O(n\log{n}) O(nlogn)

稳定性:稳定,合并的数组的时候,如果两个值相同的话会按照原先的顺序依次放入到临时数组当中。

代码实现:

int arr[] = {0, 2, 9, 55, 54, 7, 8, 1, 40, 600};
int tmp[1000];
void merge_arr(int* arr, int* tmp, int start, int end, int mid) {
    int i = start, j = mid + 1, p = 0;
    //要保证归并排序的稳定性,<=的时候优先取左侧
    while (i <= mid && j <= end) {
        if (arr[i] <= arr[j]) {
            tmp[p++] = arr[i++];
        } else {
            tmp[p++] = arr[j++];
        }
    }
    //当一个数组填完了,剩余的部分要填完,也就是另一个数组内不存在小于等于这个数的数据了
    while (i <= mid) {
        tmp[p++] = arr[i++];
    }
    while (j <= end) {
        tmp[p++] = arr[j++];
    }
    //回填入数组
    for (int k = start; k <= end; k++) {
        arr[k] = tmp[k - start];
    }
}
void sort(int* arr, int start, int end) {
    //二分区间
    if (start < end) {//这个条件需要否则会无限递归
        int  mid = (start + end) >> 1;
        sort(arr, start, mid);//分成start~mid mid+1~end两个区间
        sort(arr, mid + 1, end);
        merge_arr(arr, tmp, start, end, mid);
    }
}

6、桶排序/计数排序/基数排序

桶排序(Bucket sort)

排序方法:将输入值的值域划分成若干个区间,分别放入到桶中,再用其他排序方法对桶内的元素进行排序,类似分块,分治。

时间复杂度:取决于桶内排序算法的时间复杂度以及分类后所在的桶的数目,如果使用堆排序来进行桶内排序的话,并且最后均匀地分入到k个桶内,那么时间复杂度是 O ( n + n log ⁡ n k ) O(n+n\log{\frac{n}{k}}) O(n+nlogkn),当桶足够多时,覆盖了值域的时候,便是 O ( n ) O(n) O(n)的计数排序。

稳定性:取决于给桶内排序的算法的稳定性,如果是插入排序就是稳定的,如果是堆排序或者快速排序就是不稳定的。

代码实现:

int arr[] = {0, 2, 9, 3, 5, 7, 8, 1, 4, 6};

//arr是被排序数组,start是起点坐标,end是终点坐标(闭区间)

void sort(int* arr, int start, int end, int bucket_size) {
    int min_value = arr[start];
    int max_value = arr[start];
    //获得值域
    for (int i = start; i <= end; i++) {
        if (arr[i] < min_value) {
            min_value = arr[i];
        }
        if (arr[i] > max_value) {
            max_value = arr[i];
        }
    }
    int val_area = max_value - min_value + 1;
    int bucket_nums = (val_area + bucket_size - 1) / bucket_size;
    //获得向上取整的桶的数目
    //如果此处size为4,分成 0~3, 4~7, 8~9三个桶,标号分别是0 1 2
    for (int i = start; i <= end; i++) {
        int x = arr[i];
        int id = (x - min_value) / bucket_size;
        buckets[id][elements_in_bukect[id]++] = x;//填入一个数字
    }

    for (int i = 0; i < bucket_nums; i++) {
        if (elements_in_bukect[i] == 0) continue;
        int len = elements_in_bukect[i];
        heap_sort(buckets[i], 0, len - 1);
    }

    //回收排序好的数字
    int p = 0;
    for (int i = 0; i < bucket_nums; i++) {
        if (elements_in_bukect[i] == 0) continue;
        int len = elements_in_bukect[i];
        for (int j = 0; j < len; j++) {
            arr[p + start] = buckets[i][j];
            p++;
        }
    }
}

计数排序(Counting Sort)

排序方法:计数排序是桶排序中桶的数量和值域长度相同的时候,就是一次读入数据,放入到对应值的桶内,最后遍历值域输出排序好的数组。

时间复杂度: O ( n + k ) O(n+k) O(n+k)其中k是值域长度,n是元素数目。

稳定性:稳定。按序读入相同值,按序拷贝出来。笔者想了想,直接用一维数组有点难以体现稳定性,如果用可变长数组或者链表来实现的话就能维护相同值的相对次序,每个链表存入该值的id。或者用二维数组。

代码实现:

int arr[] = {0, 2, 9, 3, 5, 7, 8, 1, 4, 6};

//这里没有用链表
int cnt[100];
void sort(int* arr, int start, int end) {
    int min_value = arr[start];
    int max_value = arr[start];
    for (int i = start; i <= end; i++) {
        if (arr[i] < min_value) {
            min_value = arr[i];
        }
        if (arr[i] > max_value) {
            max_value = arr[i];
        }
    }
    for (int i = start; i <= end; i++) {
        cnt[arr[i] - min_value]++;
    }
    int p = start;
    for (int i = 0; i <= max_value - min_value; i++) {
        for (int j = 0; j < cnt[i]; j++) {
            arr[p++] = i + min_value;
        }
    }
}

基数排序(Radix Sort)

排序方法:基数排序相当于对每一位作计数排序。

时间复杂度: O ( k ⋅ n ) O(k·n) O(kn)其中k是最大数的某进制形式下的数码长度(通常是十进制)

原理说明:手写高位到低位分别是主要关键字,次要关键字,,,次次关键字,最次关键字。首先我们根据最低位排序,如果后面高位不相同,会按照高位排序,如果高位相同的话,但是低位不相同,计数排序具有稳定性,不会改变低位已经排好的顺序。

稳定性:稳定。同上。

注意:基数排序的需要非负整数,如果有负数的话需要调整为非负整数。

代码实现:

int arr[] = {0, 2, 9, 3, 5, 7, 8, 1, 40, 600};

//这里没有用链表
int buckets[10][10000];//数码桶,一个桶里可以装10000个数
int elements_in_bucket[10];//数码桶内数有多少
void sort(int* arr, int start, int end) {
    int max_value = arr[start];
    for (int i = start; i <= end; i++) {
        if (arr[i] > max_value) {
            max_value = arr[i];
        }
    }
    int max_length = 0;
    while (max_value > 0) {
        max_length++;
        max_value /= 10;
    }
    if (max_length == 0) return;//如果都是0
    for (int i = 0, base = 1; i < max_length; i++, base *= 10) {
        //对每一位进行排序
        for (int j = start; j <= end; j++) {
            int digit = arr[j] / base % 10;
            //存入某位数码为digit的桶
            buckets[digit][elements_in_bucket[digit]] = arr[j];
            //桶内数目
            elements_in_bucket[digit]++;
        }
        int index = start;
        for (int j = 0; j < 10; j++) {//遍历数码桶
            if (elements_in_bucket[j] != 0) {
                for (int k = 0; k < elements_in_bucket[j]; k++) {
                    arr[index++] = buckets[j][k];
                }
            }
            elements_in_bucket[j] = 0;//
        }
    }
}

到了这里,关于【排序算法略解】(十种排序的稳定性,时间复杂度以及实现思想)(含代码)(完工于2023.8.3)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【排序算法】详解冒泡排序及其多种优化&稳定性分析

    冒泡排序(Bubble Sort) 就是从序列中的 第一个元素 开始,依次对 相邻的两个元素 进行比较,如果前一个元素 大于 后一个元素则交换它们的位置。如果前一个元素 小于或等于 后一个元素,则不交换它们;然后每一轮目前的元素中最大的或最小的排到最上面,就像水中的泡泡冒

    2024年02月07日
    浏览(38)
  • 【数据结构】排序算法的稳定性分析

    💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤 📃 个人主页 :阿然成长日记 👈点击可跳转 📆 个人专栏: 🔹数据结构与算法🔹C语言进阶 🚩 不能则学,不知则问,耻于问人,决无长进 🍭 🍯 🍎 🍏 🍊 🍋 🍒 🍇 🍉 🍓 🍑 🍈 🍌 🍐 🍍 前言: 前面我们已经

    2024年02月08日
    浏览(60)
  • 【八大排序(十)】八大排序效率与稳定性分析

    💓博主CSDN主页:杭电码农-NEO💓   ⏩专栏分类:八大排序专栏⏪   🚚代码仓库:NEO的学习日记🚚   🌹关注我🫵带你学习排序知识   🔝🔝 比较八大排序不能直接将 这八个排序放在一起讨论 我们根据大致效率将它们分为两组: (每个排序的详情链接在后面) 1. 第一组 插入排

    2024年02月11日
    浏览(56)
  • 数据结构--堆的实现-大根堆/小根堆/堆排序/堆排序稳定性证明/TOP-K

            前言          逆水行舟,不进则退!!!                目录        认识堆        堆的创建         1,向下调整的方法建立堆         2,以向下调整的方式建立小根堆         3,向上调整的方式建堆        堆的插入        堆的删除              

    2024年02月04日
    浏览(56)
  • 基于遗传算法优化BP神经网络的滑坡稳定性预测,BP神经网络的详细原理

    目录 BP神经网络的原理 BP神经网络的定义 BP神经网络的基本结构 BP神经网络的神经元 BP神经网络的激活函数, BP神经网络的传递函数 遗传算法原理 遗传算法主要参数 遗传算法流程图 完整代码包含数据下载链接: 遗传算法优化BP神经网络的MATALB代码,遗传算法优化BP神经网络

    2024年02月05日
    浏览(60)
  • 百度出品,Nature重磅 -- 优化的mRNA设计算法可改善mRNA的稳定性和免疫原性

    摘要 尽管mRNA疫苗已用于COVID-19的预防,但仍然面临不稳定和易降解的风险,这是mRNA疫苗存储、配送、效价等面临的重要障碍。先前的研究已表明, 增加二级结构可延长mRNA的半衰期 ,再加上 选择优化的密码子,可改善蛋白表 达。因此,原则上mRNA的设计算法必须优化二级结

    2024年02月08日
    浏览(56)
  • 【稳定性】稳定性建设之弹性设计

    随着业务的快速变化和技术的不断发展,系统面临着诸多挑战,例如流量峰值、依赖服务故障、硬件故障、网络中断、软件缺陷等,这些因素都可能影响到系统的正常运行。在这种背景下,弹性设计(Resilience Design)应运而生。弹性设计是一种系统的设计和构建方法, 系统的

    2024年02月08日
    浏览(47)
  • 稳定性建设框架

    一、为什么要做稳定性建设 1、从熵增定律引出稳定性建设的必要性 物理学上,用“熵”来描述一个体系的混乱程度。卡尔·弗里德曼提出熵增定律,他认为在一个封闭的系统内,如果没有外力的作用,一切物质都会从有序状态向无序状态发展。 如果我们不希望系统变混乱,

    2024年02月08日
    浏览(45)
  • 3分钟了解Android中稳定性测试_手机稳定性测试,大厂软件测试高级多套面试专题整理集合

    先自我介绍一下,小编浙江大学毕业,去过华为、字节跳动等大厂,目前阿里P7 深知大多数程序员,想要提升技能,往往是自己摸索成长,但自己不成体系的自学效果低效又漫长,而且极易碰到天花板技术停滞不前! 因此收集整理了一份《2024年最新软件测试全套学习资料》

    2024年04月26日
    浏览(46)
  • 如何做好垂直域稳定性

      一个小小的故障就可能造成巨大的负面影响,因此稳定性工作复杂却又至关重要。本文将通过故障预防、修复、复盘来讲解该如何建设一个稳定性体系。   来到阿里后,我的工作内容一直都是商品中心的稳定性,这份工作对于我个人在技术和经验上的成长提升是无比巨大的

    2024年02月11日
    浏览(65)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包