基础算法(1):排序(1):选择排序

这篇具有很好参考价值的文章主要介绍了基础算法(1):排序(1):选择排序。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

     今天对算法产生了兴趣,开始学习基础算法,比如排序,模拟,贪心,递推等内容,算法是很重要的,它是解决某个问题的特定方法,程序=数据结构+算法,所以对算法的学习是至关重要的,它可以提高程序效率,不同的算法也是有优劣的,如何进行评价,这也是我们需要知道的,我会在学习中穿插这种评价方法,下面让我们看看第一个基础算法排序中的选择排序。

1.选择排序的实现

     选择排序(SelectionSort)算法的工作原理是每一次遍历从待排序的元素中选出最小(或最大)的一个元素,将其放在已经排好序的数列之后,直到全部排好序为止。

     其核心就是选择和交换,流程如下:

      假如给定初始数据 8 4 2 7 3(红色为每次遍历交换的数据)

      第一次排序 2 4 8 7 3

      第二次排序 2 3 8 7 4

      第三次排序 2 3 4 7 8

      首先在未排序序列中找到最小(或最大)元素,放到排序序列的起始位置,然后再从剩余未排序元素中继续寻找最小(或最大)元素,然后放到已排序序列的末尾,直到所有元素全部排好序。

      逻辑是这样:

   (1)第一轮从下标为 1 到下标为 n-1 的元素中选取最小值,若小于第一个数,则交换
   (2)第二轮从下标为 2 到下标为 n-1 的元素中选取最小值,若小于第二个数,则交换
        依次类推下去……

      我们可以再看一个动画演示加深对过程的理解,本图非本人所作,借鉴别人的。

基础算法(1):排序(1):选择排序,基础算法,算法

       下面是代码实现:

void selectionSort(int arr[],int len)
{
  int i,j,min,temp;
  for(i=0;i<len-1;i++)
 {
     min=i;//先定义一个最小值对应的下标
     for(j=i+1;j<len;j++)
   {
         if(arr[min]>arr[j])//如果大于就更新最小值对应的下标
         {
            min=j;
         }
    }
      temp=arr[min];//循环结束,找到本次待排序序列的最小值,和序列首元素进行交换,之后进入下一次循环
      arr[min]=arr[i];
      arr[i]=temp;
    
  }
}
    

       或者下面这个版本

void selectSort(int arr[], int n) {
    if(n==0||n==1)return;
    int i, j, minIndex;
    for (int i = 0; i < n - 1; i++) {
        minIndex = i;//先定义最小值对应的下标
        for (int j = i + 1; j < n-1; j++)
        {
            minIndex = arr[j] < arr[minIndex] ? j : minIndex;//如果小于就更新最小值下标
        }
        int temp=arr[min];//循环结束,找到本次待排序序列的最小值,和序列首元素进行交换,之后进入下一次循环
        arr[min]=arr[i];
        arr[i]=temp;
    }
}

2.选择排序的时间复杂度

      时间复杂度?这是什么玩意?别搞我啊?可能大家在看到这个词的心理状态是这样的,但你先别急。

2.1 时间复杂度

       时间复杂度是用来评价算法性能的,它是用来方便开发者估算程序的运行时间,我们如何估计程序运行时间呢?我们通常会估计算法的操作单元数量,来代表程序消耗的时间

      假设算法道德问题规模为n,那么操作单元数量就用函数f(n)来表示,随着n的增大,算法执行时间的增长率和f(n)的增长率相同,这就称作算法的时间复杂度,记为O(f(n))。

      大O用来表示上界的,当用它作为算法的最坏情况运行时间的上界,就是对任意数据输入的运行时间的上界。

  2.2 如何描述时间复杂度

基础算法(1):排序(1):选择排序,基础算法,算法

      

      

     决定使用哪个算法不仅仅要考虑时间复杂度,不是时间复杂越低的越好,要考虑数据规模,如果数据规模很小,甚至可以用O(n^2)的算法比 O(n)的更合适,就像上图中图中 O(5n^2) 和O(100n) 在n小于2的时候 O(5n^2)是更优的,所花费的时间也是最少的。

     那我们为什么在计算时间复杂度的时候要忽略常数项系数呢,也就说O(100n) 就是O(n)的时间复杂度,并且要默认O(n) 优于O(n^2) 呢 ?

     因为大O其实就是数据量级突破一个点且数据量级非常大的情况下所表现出的时间复杂度,也就是刚才说的上界,在这个时候,常数项系数已经不起决定性作用了,所以可以省略。

     例如上图中 20 就是那个点 ,n只要大于20 常数项系数已经不起决定性作用了,其实也包括除最高次数项的其他项。

     所以我们说的时间复杂度都是省略常数项系数的,是因为一般情况下我们都是默认数据规模足够的大,基于这样的事实 我们给出的算法时间复杂的的一个排行如下所示:

     O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)

     这里只是大概列出概念,后面会专门写一篇来讲这方面的问题。

2.3 选择排序的时间复杂度

     从上面的代码我们可以知道选择排序套用了两个循环:

for(i=0;i<n-1;i++)
{
    
     for(j=i+1;j<n;j++)
   {

   }

}

     很显然问题规模是n,问题规模就是需要解决问题处理数据量的大小,显然是处理n个元素的排序问题,规模为n。

     当i=0时,下面内循环比较n-1次,每次i+1下面内循环比较n-i次,因此总共循环次数(操作单元数量)为(n-1)+(n-2)+......+2+1=n^2/2,舍去最高项系数,时间复杂度为O(n^2)

3.leetcode题目

3.1 颜色分类

基础算法(1):排序(1):选择排序,基础算法,算法

    

void sortColors(int* nums, int numsSize) {
    int i,j,min,temp;
   for(i=0;i<numsSize-1;i++)
  {
     min=i;
     for(j=i+1;j<numsSize;j++)
     {
         if(nums[min]>nums[j])
         {
            min=j;
         }
     }
      temp=nums[min];
      nums[min]=nums[i];
      nums[i]=temp;
  }
}
   

      这个没什么好说的,就是排序,太水了,模板题。

3.2 至少是其他数字两倍的最大数

基础算法(1):排序(1):选择排序,基础算法,算法

int dominantIndex(int* nums, int numsSize) {
    if(numsSize==1)return 0;
    int max=0;
    for(int i=0;i<numsSize;i++)
    {
        if(nums[max]<nums[i])max=i;
    }
     int minindex=0;
    for(int i=0;i<numsSize-1;i++)
    {
        minindex=i;
        for(int j=i+1;j<numsSize;j++)
        {
            minindex=nums[j]<nums[minindex]?j:minindex;
        }
        if(i!=minindex)
        {
            int temp=nums[i];
            nums[i]=nums[minindex];
            nums[minindex]=temp;
        }
    }
        if(nums[numsSize-1]>=2*nums[numsSize-2])return max;
        else return -1;
}

      这个题也不难,关键在于我们要先记录最大数对应的下标,因为我们排序后会破坏原来的顺序,再就是我们只需要判断排序后最后一个数是不是至少是前一个数的两倍,如果这个满足,那这个最大数也必然是其他是的至少两倍。

3.3 判断能否形成等差数列

基础算法(1):排序(1):选择排序,基础算法,算法

bool canMakeArithmeticProgression(int* arr, int arrSize) {
     for(int i=0;i<n;i++)
    {
        int minindex=i;
        for(int j=i+1;j<n;j++)
        {
            minindex=nums[j]<nums[minindex]?j:minindex;
        }
            int temp=nums[i];
            nums[i]=nums[minindex];
            nums[minindex]=temp;
    }
    int d=arr[1]-arr[0];
    for(int i=2;i<arrSize;i++)
    {
       if((arr[i]-arr[i-1])!=d)return false;
    }
    return true;
}

    这个题就是先排序,这样我们就可以很容易的判断,先假定公差为前两个数之差,如果遍历后面相邻两个数之差等于该公差,那说明是等差数列,否则不是。文章来源地址https://www.toymoban.com/news/detail-757377.html

到了这里,关于基础算法(1):排序(1):选择排序的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【算法】排序——选择排序和交换排序(快速排序)

     ========================================================================= 主页点击直达: 个人主页 我的小仓库: 代码仓库 C语言偷着笑: C语言专栏 数据结构挨打小记:初阶数据结构专栏 Linux被操作记:Linux专栏 LeetCode刷题掉发记:LeetCode刷题 算法头疼记:算法专栏  =========================

    2024年02月08日
    浏览(43)
  • 【数据结构与算法】排序算法(选择排序,冒泡排序,插入排序,希尔排序)

    基本概念这了就不浪费时间解释了,这四种都是很简单的排序方式,本专栏后续文章会出归并排序,计数排序,快速排序,堆排序,桶排序等排序算法,今天这篇文章中给出选择排序,冒泡排序,插入排序和希尔排序的实现; 如果发现文章中有错误,还请大家指出来,我会非

    2024年02月15日
    浏览(81)
  • 排序算法(一) -- 选择排序和冒泡排序

    选择排序和冒泡排序是我们初学C语言必学的两种简单的排序算法,也是我们以后学习数据结构与算法课程中更复杂的排序算法的基础。本文用由浅入深的逻辑条理,试图将这两种排序算法讲解清楚。 本文所有的排序均是针对一维数组的,全文所用的一维数组的例子如下: 一

    2024年02月06日
    浏览(32)
  • 排序算法之详解选择排序

    选择排序顾名思义是需要进行选择的,那么就要问题了,选择到底是选择什么呢? 选择排序的选择是 选择 数组中 未排序的数组 中 最小的值 ,将被选择的元素放在 未排序数组 的 首位 如果你对 ‘未排序数组’ , ‘选择’ 的概念不理解,那么你可以看看下面的图 有了上面

    2023年04月25日
    浏览(44)
  • 排序算法:选择排序

    选择排序的思想是:双重循环遍历数组,每经过一轮比较,找到最小元素的下标,将其交换至首位。         选择排序就好比第一个数字站在擂台上,大吼一声:“还有谁比我小?”。剩余数字来挨个打擂,如果出现比第一个数字小的数,则新的擂主产生。每轮打擂结束

    2024年02月11日
    浏览(80)
  • 【算法系列 | 3】深入解析排序算法之——选择排序

    你只管努力,其他交给时间,时间会证明一切。 文章标记颜色说明: 黄色 :重要标题 红色 :用来标记结论 绿色 :用来标记一级论点 蓝色 :用来标记二级论点 决定开一个算法专栏,希望能帮助大家很好的了解算法。主要深入解析每个算法,从概念到示例。 我们一起努力

    2024年02月08日
    浏览(41)
  • 【数据结构】常见排序算法——常见排序介绍、选择排序(直接选择排序、堆排序)交换排序(冒泡排序)

      选择排序是一种简单但不高效的排序算法,其基本思想是从待排序的数据中选择最小(或最大)的元素放到已排序的数据末尾。具体操作步骤如下: (1)找到数据中最小的元素,并把它交换到第一个位置; (2)在剩下未排序的元素中找到最小的元素,并把它交换到已排

    2024年02月04日
    浏览(52)
  • 排序算法(初阶)【冒泡,插入,选择排序】

    比较相邻的两个元素。如果第一个比第二个大,就交换他们两个。 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对,这被称为一趟冒泡排序 这样就可以把数组中要排序的数中的最大值放到最后,也相当于把一个元素排在了元素有序时它应处于的位置,它既

    2024年01月21日
    浏览(48)
  • 排序算法一:冒泡、选择、插入排序

    目录         冒泡排序 理论 代码实现 时间复杂度 选择排序 理论 代码实现  时间复杂度 插入排序 理论分析 代码实现 时间复杂度    冒泡,我们很容易联想到水煮沸,或者是鱼儿吐泡的情景,水泡会在水中上升到达水面。冒泡排序正如其名,即大的数一个个往上冒出来。

    2024年02月22日
    浏览(39)
  • 十大排序算法之插入排序、希尔排序、选择排序

    个人主页:平行线也会相交 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 平行线也会相交 原创 收录于专栏【数据结构初阶(C实现)】 本篇主要讲解八大排序算法中的三种排序,分别是: 插入排序、希尔排序、选择排序 。 在我们的日常生活最常见的一个场景就是斗地主,

    2023年04月16日
    浏览(36)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包