漫话:选择排序,一首圣诞歌的时间全部掌握

简介: 漫话:选择排序,一首圣诞歌的时间全部掌握

🌟 前言

大家好,我是Edison😎

本篇文章将继续介绍常见八大排序中的 选择排序;

前面已经写过了 插入排序 和 交换排序(点击即可跳转到文章页面)

不废话,直接干!😎

Let’s get it!

🛫送给所有正在努力的大家一句话:你不一定逆风翻盘,但一定要向阳而生🌅

文章目录

1. 选择排序分类

选择排序可以分为: 简单选择排序堆排序

image.png

2. 简单选择排序

🍑 基本思想

选择排序(Selection sort)是一种简单直观的排序算法

 

它的工作原理是:每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置;直到全部待排序的数据元素排完 。

😎暴力图解展示

这里直接拿一组数来举例:

image.png

第二次交换:

image.png

第三次交换:

image.png

第四次交换:

image.png

🍑 动图演示

image.png

在元素集合array[i] 到 array[n-1]中选择关键码最大(小)的数据元素;

若它不是这组元素中的最后一个(第一个)元素,则将它与这组元素中的最后一个(第一个)元素交换;

在剩余的array[i] 到 array[n-2](array[i+1]--array[n-1])集合中,重复上述步骤,直到集合剩余1个元素

//写一个交换函数
void Swap(int* px, int* py)
{
  int tmp = *px;
  *px = *py;
  *py = tmp;
}
//选择排序(一次选一个数)
void SelectSort(int* a, int n)
{
  int i = 0;
  for (i = 0; i < n; i++)//i代表参与该趟选择排序的第一个元素的下标
  {
    int start = i;
    int min = start;//记录最小元素的下标
    while (start < n)
    {
      if (a[start] < a[min])
        min = start;//最小值的下标更新
      start++;
    }
    Swap(&a[i], &a[min]);//最小值与参与该趟选择排序的第一个元素交换位置
  }
}

其实这段代码还可以进行升级😏

实际上,我们可以一趟选出两个值:

 

一个最大值一个最小值,然后将其放在序列开头和末尾,这样可以使选择排序的效率快一倍。

void Swap(int* px, int* py)
{
  int tmp = *px;
  *px = *py;
  *py = tmp;
}
//选择排序(一次选两个数)
void SelectSort(int* a, int n)
{
  int left = 0;//记录参与该趟选择排序的第一个元素的下标
  int right = n - 1;//记录参与该趟选择排序的最后一个元素的下标
  while (left < right)
  {
    int minIndex = left;//记录最小元素的下标
    int maxIndex = left;//记录最大元素的下标
    int i = 0;
    //找出最大值及最小值的下标
    for (i = left; i <= right; i++)
    {
      if (a[i] < a[minIndex])
        minIndex = i;
      if (a[i]>a[maxIndex])
        maxIndex = i;
    }
    //将最大值和最小值放在序列开头和末尾
    Swap(&a[minIndex], &a[left]);
    if (left == maxIndex)
    {
      maxIndex = minIndex;//防止最大值位于序列开头,被最小值交换
    }
    Swap(&a[maxIndex], &a[right]);
    left++;
    right--;
  }
}

🍑 概括总结

1、直接选择排序思考非常好理解,但是效率不是很好。实际中很少使用 ;

 

2、时间复杂度:$O(N^2) $

 

3、空间复杂度:$O(1) $

 

4、稳定性:不稳定

3. 堆排序

🍑 基本思想

堆排序(Heapsort)是指:利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。

 

它是通过 来进行选择数据。需要注意的是 排升序要建大堆排降序建小堆

要学习堆排序,首先要学习堆的向下调整算法,因为要用堆排序,你首先得建堆,而建堆需要执行多次堆的向下调整算法。

关于堆的详细解释,我这里只是简单说一下,后面我会单独出一期博客来讲解,因为设计到的知识点太多了

🍑 大根堆和小根堆

堆的结构可以分为 大根堆小根堆,是一个 完全二叉树 ,而堆排序是根据堆的这种数据结构设计的一种排序,下面先来看看什么是大根堆和小根堆

 

每个结点的值都大于其 左孩子和右孩子结点的值,称之为大根堆;👇

image.png

每个结点的值都小于其 左孩子 和 右孩子 结点的值,称之为小根堆;👇

image.png

我们对上面的图中每个数都进行了标记,上面的结构映射成数组就变成了下面这个样子;👇

image.png

image.png

🍑 堆的性质

假设我们查找数组中某个数的父结点左右孩子结点比如已知索引为i的数,那么👇

1、父结点索引: ( i − 1 ) / 2 (i-1)/2 (i−1)/2(这里计算机中的除以2,省略掉小数)

2、左孩子索引: 2 ∗ i + 1 2*i+1 2∗i+1

3、右孩子索引: 2 ∗ i + 2 2*i+2 2∗i+2


所以上面两个数组可以脑补成堆结构,因为他们满足堆的定义性质👇

大根堆: a r r ( i ) > a r r ( 2 ∗ i + 1 ) arr(i)>arr(2*i+1) arr(i)>arr(2∗i+1) && a r r ( i ) > a r r ( 2 ∗ i + 2 ) arr(i)>arr(2*i+2) arr(i)>arr(2∗i+2)

小根堆: a r r ( i ) < a r r ( 2 ∗ i + 1 ) arr(i)<arr(2*i+1) arr(i)<arr(2∗i+1) && a r r ( i ) < a r r ( 2 ∗ i + 2 ) arr(i)<arr(2*i+2) arr(i)<arr(2∗i+2)

🍑 构造堆

排序步骤👇

首先将待排序的数组构造成一个大根堆,此时,整个数组的最大

值就是堆结构的顶端

顶端的数末尾的数交换,此时,末尾的数为最大值,剩余待排序数组个数为n-1

将剩余的n-1个数再构造成大根堆,再将顶端数与n-1位置的数交换,如此反复执行,便能得到有序数组

构造👇

将无序数组构造成一个大根堆(升序用大根堆,降序就用小根堆)

 

假设存在以下数组

image.png

🤔主要思路:

第一次保证 0~0 位置大根堆结构;

 

第二次保证0~1位置大根堆结构;

 

第三次保证0~2位置大根堆结构;

直到保证0~n-1位置大根堆结构;

 

(每次新插入的数据都与其父结点进行比较,如果插入的数比父结点大,则与父结点交换;否则一直向上交换,直到小于等于父结点,或者来到了顶端)

开始交换👇

插入6的时候,6大于他的父结点3,即arr(1)>arr(0),则交换;

 

此时,保证了0~1位置是大根堆结构,如下图:

image.png

插入8的时候,8大于其父结点6,即arr(2)>arr(0),则交换;

 

此时,保证了0~2位置是大根堆结构,如下图:

image.png

插入5的时候,5大于其父结点3,则交换;交换之后,5又发现比8小,所以不交换;

 

此时,保证了0~3位置大根堆结构,如下图:

image.png

插入7的时候,7大于其父结点5,则交换;交换之后,7又发现比8小,所以不交换;

 

此时 整个数组已经是大根堆结构

image.png

🍑 固定最大值再构造堆

此时,我们已经得到一个大根堆,下面将顶端的数与最后一位数交换,然后将剩余的数再构造成一个大根堆👇

image.png

此时最大数8已经来到末尾,则固定不动,后面只需要对顶端的数据进行操作即可;

拿顶端的数与其左右孩子较大的数进行比较,如果顶端的数大于其左右孩子较大的数,则停止;

如果顶端的数小于其左右孩子较大的数,则交换,然后继续与下面的孩子进行比较;

下图中,5的左右孩子中,左孩子7比右孩子6大,则5与7进行比较,发现5<7,则交换;交换后,发现5已经大于他的左孩子,说明剩余的数已经构成大根堆,后面就是重复固定最大值,然后构造大根堆👇

image.png

顶端数7末尾数3进行交换,固定好7, 如下图👇

image.png

剩余的数开始构造大根堆 ,然后顶端数与末尾数交换,固定最大值再构造大根堆,重复执行上面的操作,最终会得到有序数组👇

image.png

到这里,大家应该对堆排序都有了自己的见解,我们对上面的流程总结下:

1、首先将无需数组构造成一个大根堆(新插入的数据与其父结点比较)

 

2、固定一个最大值,将剩余的数重新构造成一个大根堆,重复这样的过程

🍑 动图演示

看过了上面的推排序流程以后,我们再来看一张经典的 堆排序 动图👇

image.png

是不是思路一下子就通顺了?

📃 代码实现

void Swap(int* px, int* py)
{
  int tmp = *px;
  *px = *py;
  *py = tmp;
}
//堆排序
void AdjustDown(int* a, int n, int parent){
    int child = parent*2 + 1;
    while(child < n){
        if(child+1<n && a[child+1] > a[child]){
            ++child;
        }
        if(a[child]>a[parent]){
            Swap(&a[child], &a[parent]);
            parent = child;
            child = parent*2+1;
        }else{
            break;
        }
    }
}
void HeapSort(int* a, int n){
    //排升序建大堆 O(N)
    for(int i=(n-1-1)/2; i>=0; i--){
        AdjustDown(a, n, i);
    }
    //O(N*logN)
    int end = n - 1;
    while(end > 0){
        Swap(&a[0], &a[end]);
        AdjustDown(a, end, 0); //是不是妙不可言hhh!
        end--;
    }
}

🍑 概括总结

1、堆排序使用堆来选数,效率就高了很多。



2、时间复杂度: O ( N ∗ l o g N ) O(N*logN) O(N∗logN)



3、空间复杂度: O ( 1 ) O(1) O(1)



4、稳定性:不稳定

4. 总结

其实在选择排序里面 直接选择排序 是很简单的😏

但是 堆排序 可能你看了这篇文章,并不一定能学会,或者说,还是不明白什么是 堆排序

别急,这是正常现象,那么可以去网上找找视频,然后再看一些书籍,来加深自己的理解💪

🤗作者水平有限,如有总结不对的地方,欢迎留言或者私信!

 

💕如果你觉得这篇文章还不错的话,那么点赞👍、评论💬、收藏🤞就是对我最大的支持!

 

🌟你知道的越多,你不知道越多,我们下期见!

相关文章
|
2月前
|
机器学习/深度学习 算法 搜索推荐
让星星⭐月亮告诉你,Java冒泡排序及其时间复杂度计算
冒泡排序是一种简单的排序算法,通过多次遍历数组,每次比较相邻元素并交换位置,将较小的元素逐步移至数组前端。第一轮结束后,最小值会位于首位;第二轮则将次小值置于第二位,依此类推。经过 (n-1) 轮遍历后,数组完成排序。冒泡排序的时间复杂度为 O(n²),在最优情况下(已排序数组)时间复杂度为 O(n)。示例代码展示了如何实现冒泡排序。
54 1
|
6月前
|
算法 搜索推荐 数据可视化
【漫画算法】插入排序:插入宝石的传说
【漫画算法】插入排序:插入宝石的传说
|
6月前
|
搜索推荐
【海贼王的数据航海】排序——直接选择排序|堆排序
【海贼王的数据航海】排序——直接选择排序|堆排序
25 0
|
6月前
|
搜索推荐 算法
【海贼王的数据航海】排序——冒泡|快速|归并排序|总结
【海贼王的数据航海】排序——冒泡|快速|归并排序|总结
1345 0
leetcode 1921. 消灭怪物的最大数量(每日一题)
leetcode 1921. 消灭怪物的最大数量(每日一题)
84 0
|
搜索推荐 算法
【排序算法 上】带你手撕常见排序 (插入,希尔,选择,堆排序) (动图详解)
【排序算法 上】带你手撕常见排序 (插入,希尔,选择,堆排序) (动图详解)
112 0
【排序算法 上】带你手撕常见排序 (插入,希尔,选择,堆排序) (动图详解)
|
搜索推荐 算法 C语言
【排序算法 下】带你手撕常见排序 (冒泡,快排,归并排序) (动图详解)
【排序算法 下】带你手撕常见排序 (冒泡,快排,归并排序) (动图详解)
167 0
【排序算法 下】带你手撕常见排序 (冒泡,快排,归并排序) (动图详解)
|
存储 机器学习/深度学习 算法
【第二天】算法图解 之 选择排序
【第二天】算法图解 之 选择排序
|
机器学习/深度学习 算法 搜索推荐
算法渣-排序-选择排序
没有一身好内功,招式再多都是空;算法绝对是防身必备,面试时更是不可或缺;跟着算法渣一起从零学算法
114 0
算法渣-排序-选择排序
|
机器学习/深度学习 算法 搜索推荐
算法渣-排序-冒泡
没有一身好内功,招式再多都是空;算法绝对是防身必备,面试时更是不可或缺;跟着算法渣一起从零学算法
121 0
算法渣-排序-冒泡