选择排序(多方式)

简介: 选择排序(多方式)



直接选择排序

基本思想:给定一个待排序的数组或列表,简单选择排序通过不断选择最小(或最大)元素,并将其放置到已排好序部分的末尾,从而逐步构建有序序列

实现步骤:1、记录无序数组的首尾元素坐标begin和end,同时利用maxi和mini记录每次比较过程中最大数和最小数的下标(只是下标而不是具体的数字,在一轮比较完成后才会进行数字的交换,而且由于是要选出每次比较的最大/小值,所以当一个数字的大小在下标为maxi和mini的元素之间时,maxi或mini的值不会改变),二者的初始值都是数组首元素下标0(这样从第一次开始比较时就能将maxi或者mini分开便于后续的比较)

2、我们在这里规定比较是“新元素(初始新元素为数组首元素的下一个元素,所以要begin+1)与元素下标为maxi和mini之间的关系,第一次比较是“新数字89”与元素下标为maxi和mini之间的关系,89大于5,所以此时mini不变,但是maxi发生改变,它此时记录新的最大值下标(0->1)

3、第二次比较,“新数字3”与元素下标为maxi和mini之间的关系,3小于5,所以此时mini改变,记录新的最小值下标(0->2)

4、 第三次比较,“新数字6”与元素下标为maxi和mini之间的关系,6大于3小于89,不算最大也不算最小,所以此时mini和maxi均不发生改变

5、 第四次比较,“新数字0”与元素下标为maxi和mini之间的关系,0小于3,所以此时mini改变,记录新的最小值下标(2->4)

5、 第五次比较,“新数字48”与元素下标为maxi和mini之间的关系,48大于0小于89,不算最大也不算最小,所以此时mini和maxi均不发生改变

6、 第六比较,“新数字12”与元素下标为maxi和mini之间的关系,12大于0小于89,不算最大也不算最小,所以此时mini和maxi均不发生改变

7、 第七次比较,“新数字2”与元素下标为maxi和mini之间的关系,2大于0小于89,不算最大也不算最小,所以此时mini和maxi均不发生改变

8、至此第一轮比较结束,此时将下标为maxi和mini元素分别与数组首尾元素交换位置

9、此外,为了避免由于代表最大值下标的maxi与begin相等,即在交换完a[mini]与a[begin]之后,a[mini]的位置被最大值覆盖,所以我们要在交换完后更新maxi的位置,将此时mini赋值给maxi,然后再去交换a[maxi]与a[end](不需要考虑mini与maxi重合的问题,因为每次每次循环开始是它们都会被重置)

10、最后外面再多套一层while循环,保证不断缩小比较的范围,当begin与end相等时,整个序列就会变为有序序列:

//简单选择排序
void SelectSort(int* a, int n)
{
  int begin = 0, end = n - 1;
  while (begin < end)
  {
    int mini = begin, maxi = begin;
    for (int i = begin + 1; i <= end; ++i)
    {
      if (a[i] < a[mini])
      {
        mini = i;
      }
      if (a[i] > a[maxi])
      {
        maxi = i;
      }
    }
    Swap(&a[begin], &a[mini]);
    if (maxi == begin)
    {
      maxi = mini;
    }
    Swap(&a[end], &a[maxi]);
    ++begin;
    --end;
  }
}

11、如果你觉得这种方法很难理解,那还是用之前的常见的简单选择排序吧:

void selectionSort(int arr[], int n) {
    int i, j, minIndex, temp;
    for (i = 0; i < n-1; i++) {
        minIndex = i;
        // 在剩余未排序部分找到最小元素的索引
        for (j = i+1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        // 将找到的最小元素与当前位置交换
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

关于它的解释等有空了我会补上😭

时空复杂度

最坏时间复杂度:O(N^2)一共需要进行 n-1 轮比较和交换操作。每一轮中,需要在剩余未排序的元素中找到最小/大的元素,并将其与当前位置进行交换,(n-1) + (n-2) + ... + 1 = (n^2 - n)/2

最好时间复杂度:O(N^2)(无论输入数据的初始顺序如何,简单选择排序都需要进行 n-1 轮比较和交换操作。在每一轮中,需要找到剩余未排序部分中的最小(或最大)元素,并将其与当前位置进行交换)

空间复杂度:O(1)

简单选择排序的特性

  1. 直接选择排序思考非常好理解,但是效率不是很好。实际中很少使用
  2. 稳定性:不稳定

堆排序

堆的相关内容放在这里了:http://t.csdnimg.cn/XO9Qh

时空复杂度

最坏时间复杂度:O(N*logN)(我们将它们放在了链接中)

最好时间复杂度:O(N*logN)(输入序列已经是一个完全有序的大顶堆或小顶堆时(即满足所有父节点都比子节点大或小),不需要进行任何交换操作。但仍然需要对每个非叶子节点执行一次向下调整操作以保持树形结构性质)

空间复杂度:O(1)

堆排序的特性总结

  1. 堆排序使用堆来选数,效率就高了很多
  2. 稳定性:不稳定

~over~

相关文章
|
分布式计算 DataWorks 数据管理
DataWorks操作报错合集之资源组切换后仍然报错,并且提示了新的IP地址172.25.0.67,该如何排查
DataWorks是阿里云提供的一站式大数据开发与治理平台,支持数据集成、数据开发、数据服务、数据质量管理、数据安全管理等全流程数据处理。在使用DataWorks过程中,可能会遇到各种操作报错。以下是一些常见的报错情况及其可能的原因和解决方法。
|
Java
【Java】接口组成更新
【Java】接口组成更新
171 0
|
JavaScript 前端开发 Java
程序员如何给变量起名字
程序员如何给变量起名字
|
监控 应用服务中间件 数据库
数据库连接池种类及性能
数据库连接池种类及性能 现在很多Web服务器(Weblogic, WebSphere, Tomcat)都提供了DataSoruce的实现,即连接池的实现。通常我们把DataSource的实现,按其英文含义称之为数据源,数据源中都包含了数据库连接池的实现。
2158 0
|
数据库 关系型数据库 MySQL
数据库触发器
~~语法~~ CREATE TRIGGER &lt;触发器名称&gt;  --触发器必须有名字,最多64个字符,可能后面会附有分隔符.它和MySQL中其他对象的命名方式基本相象. { BEFORE | AFTER }  --触发器有执行的时间设置:可以设置为事件发生前或后。 { INSERT | UPDATE | DELETE }  --同样也能设定触发的事件:它们可以在执行inse
1907 0
|
10天前
|
存储 关系型数据库 分布式数据库
PostgreSQL 18 发布,快来 PolarDB 尝鲜!
PostgreSQL 18 发布,PolarDB for PostgreSQL 全面兼容。新版本支持异步I/O、UUIDv7、虚拟生成列、逻辑复制增强及OAuth认证,显著提升性能与安全。PolarDB-PG 18 支持存算分离架构,融合海量弹性存储与极致计算性能,搭配丰富插件生态,为企业提供高效、稳定、灵活的云数据库解决方案,助力企业数字化转型如虎添翼!