首页 > 其他分享 >简单选择排序

简单选择排序

时间:2023-03-10 20:57:26浏览次数:42  
标签:min int 交换 选择 关键字 简单 排序 define

背景

爱炒股票短线的人,总是喜欢不断的买进卖出,想通过价差来实现盈利。但通常这种频繁操作的人,即使失误不多,也会因为操作的手续费和印花税过高而获得很少。

还有一种做股票的人,他们很少出手,只是在不断的观察和判断,等到时机一到,果断买进或卖出。

这些人因为冷静和沉着,以及交易的次数少,而最终收益颇丰。

 

冒泡排序的思想是不断地在交换,通过交换完成最终的排序,这和做股票短线频繁操作的人是类似的。

我们可不可以像只有在时机非常明确到来时才出手的股票高手一样,也就是在排序时找到合适的关键字再做交换,并且只移动一次就完成相应关键字的排序定位工作。

选择排序的算法思想就是受到股票高手的启发,并通过计算机的编程语言加以实现。

算法实现

预先定义排序的数据结构、公共函数,代码放在Sort.h 头文件中,供cpp文件通过include关键字包含进来。

Sort.h

#include <stdio.h>


#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int Status;

#define MAXSIZE 1000       /*用于要排序数组个数最大值,可根据需要修改*/

/*定义排序用的顺序表结构*/
typedef struct
{
    int r[MAXSIZE+1];       /*用于存储要排序数组,r[0]用作哨兵或临时变量*/
    int length;             /*用于记录顺序表的长度*/
}SqList;

void print(SqList L)
{
    int i;
    for(i=1;i<L.length;i++)
    {
        printf("%d",L.r[i]);
    }
    printf("%d",L.r[i]);
    printf("\n");
}

/*由于排序经常要对数组两元素进行交换操作,把交换操作定义为函数*/
void swap(SqList *L,int i,int j)
{
    int temp=L->r[i];
    L->r[i]=L->r[j];
    L->r[j]=temp;
}

SimpleSelectionSort.cpp

#include "Sort.h"

//简单选择排序法就是通过n-i次关键字间的比较,
//从n-i+1个记录中选出关键字最小的记录
//和第i(1<=i<=n)个记录交换。

/*对顺序表L作简单选择排序*/
void SelectSort(SqList *L)
{
    int i,j,min;
    for(i=1;i<L->length;i++){
        min=i;           /*将当前下标定义为最小值下标*/
        for(j=i+1;j<=L->length;j++){
           if(L->r[min]>L->r[j]){  //如果有小于当前最小值的关键字
            min=j;                  //将此关键字的下标赋值给min
           }
        }
        if(i!=min){/*
            若min不等于i,
            说明找到最小值,
            交换
        */
        swap(L,i,min);/*交换L->r[i]
        与L->r[min]的值。
        */
        }
    }
}

#define N 9

int main()
{
    int i;

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

    SqList L1;
    for(i=0;i<N;i++){
        //顺序表的下标保证是从1开始的
        L1.r[i+1]=f[i];
    }
    L1.length=N;
    printf("排序前:\n");
    print(L1);

    printf("最简单的选择排序:\n");
    SelectSort(&L1);
    print(L1);
}

 

针对待排序的关键字序列是{9,1,5,8,3,7,4,6,2},对i从1循环到8。

当i=1时,L->r[i]=9,min开始是1。

然后j=2~9比较L->r[min]与L->r[j]的大小,因为j=2时最小,所以min=2。

 

最终交换了L->r[2]与L->r[1]的值,注意,这里比较了8次,却只交换数据操作一次。

 

 

当i=2时,L->r[i]=9,min开始是2,经过比较后,min=9。

 

 

 

交换L->r[min]与L->r[j]的值,

 

之后的数据比较和交换完全雷同,

最多经过8次交换,就可以完成排序工作。

 

算法复杂度分析

从简单选择排序的过程来看,它最大的特点就是交换移动数据次数相当少,这样就节约了一些的时间。

分析它的时间复杂度发现,无论最好最差的情况,其比较次数都是一样的多,

第i趟排序需要进行n-i次关键字的比较,此时需要比较

 

 

 而对于交换次数而言,当最好的时候,交换为0次;当最差的时候,也就初始降序时,交换次数为n-1次。

基于最终的排序时间是比较与交换的次数总和,因此,总的时间复杂度依然为

 

 

 尽管与冒泡排序同为

 

 

 但简单选择排序的性能还是要略优于冒泡排序。

 

 

标签:min,int,交换,选择,关键字,简单,排序,define
From: https://www.cnblogs.com/gltks/p/Selection_Sort.html

相关文章

  • 归并排序
    归并排序采用了分治的思想,以及递归的写法。[图解来源:排序算法:归并排序【图解+代码】]合并两个有序数组的示意图:[图解来源:图解排序算法(四)之归并排序]代码实现:class......
  • Linux简单命令练习
     ......
  • CSS3选择器
    一、属性选择器属性选择器可以根据元素的属性及属性值来选择元素。1、E[att^=value]属性选择器E[att^=value]属性选择器是指选择名称为E的标记,且该标记定义了att属性,att......
  • 【Linux】Ubuntu系列简单调优
    是不是觉得你的Ubuntu比别人的慢?是不是并发数不够高?是不是启动个服务慢到怀疑人生?下面是我从网上收集回来的Ubuntu系列的简单性能配置,希望能够帮助到更多的人。1.修改/etc/......
  • react antd rangPicker组件选择当月、本月时间
    可以通过设置reactantdesign的RangePicker的disableDate的属性来实现只选择当月、本月时间的效果,实现代码如下1、设置RangePicker<RangePickerdis......
  • 【希尔排序ShellSort算法详解】Java/Go/Python/JS/C不同语言实现
    【希尔排序算法详解】Java/Go/Python/JS/C不同语言实现 说明希尔排序(ShellSort)是插入排序的一种改进版,也称递减增量排序算法(DiminishingIncrementSort),其实质是将数......
  • java学习日记20230310-排序
    排序 指将一组数据按照指定的顺序排列的过程分类:内部排序:指将需要处理的所有数据都加载到内存储存器中,进行排序,包括交换排序法,选择排序法,插入排序法外部排序:......
  • 该如何选择适合企业发展的邮件系统?
    很多人将邮件服务器单纯的理解为帮助企业收发邮件,其实邮箱类服务器不但可以收发邮件,还能够通过更多广受欢迎的功能实现更多企业管理的需求。如邮箱类服务器拥有邮件整理的......
  • ES Linux集群简单搭建
    1环境这里使用的是虚拟机,系统是centos7,jdk11,es7.6.2 2虚拟机安装centos及静态ip配置虚拟机安装centos及静态ip配置 3JDK安装配置安装配置 4先......
  • 拓扑排序
      拓扑排序的核心就是找入度为零的点,然后把于该点相连接的边去掉,同时更新剩余点的入度,由于n可能很大,需要邻接表,(这里用vector模拟),也可以学习链式向前星。点击查看代......