选择排序(附代码详解)(C语言)

简介: 选择排序(附代码详解)(C语言)

简介



什么是选择排序


选择排序法是一种不稳定排序算法。它的工作原理是:每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到全部待排序的数据元素排完。


算法描述


是在每次进入的第二层循环之前,将外层循环的下标赋值给临时变量,接下来的第二层循环中,如果发现有比这个最小位置处的元素更小的元素,则将那个更小的元素的下标赋给临时变量,最后,在二层循环退出后,如果临时变量改变,则说明,有比当前外层循环位置更小的元素,需要将这两个元素交换 ;  


排序算法过程图解分析

48b36b97aa03470ab88bf21fa1b1a3d0.png


选择排序法的性能分析



时间复杂度


选择排序的交换操作介于 0 和 (n - 1) 次之间。选择排序的比较操作为 n (n - 1) / 2 次之间。选择排序的赋值操作介于 0 和 3 (n - 1) 次之间。比较次数O(n^2),比较次数与关键字的初始状态无关,总的比较次数N=(n-1)+(n-2)+...+1=n*(n-1)/2。交换次数O(n),最好情况是,已经有序,交换0次;最坏情况交换n-1次,逆序交换n/2次。交换次数比冒泡排序少多了,由于交换所需CPU时间比比较所需的CPU时间多,n值较小时,选择排序比冒泡排序快。


稳定性


选择排序是给每个位置选择当前元素最小的,比如给第一个位置选择最小的,在剩余元素里面给第二个元素选择第二小的,依次类推,直到第n-1个元素,第n个元素不用选择了,因为只剩下它一个最大的元素了。那么,在一趟选择,如果一个元素比当前元素小,而该小的元素又出现在一个和当前元素相等的元素后面,那么交换后稳定性就被破坏了。举个例子,序列5 8 5 2 9,我们知道第一遍选择第1个元素5会和2交换,那么原序列中两个5的相对前后顺序就被破坏了,所以选择排序是一个不稳定的排序算法 。


代码实现



#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
void Print(int* arr, int n)    
{
  int i = 0;
  for (i = 0; i < n - 1; i++)       //打印结果
  {
    printf("%d ", arr[i]);
  }
  printf("\n");
}
void Sort_arr(int *arr,int n)
{
  int i = 0;
  int j = 0;
  int min = 0;
  for (i = 0; i < n-1; i++)
  {
      min = i;
    for (j = i + 1; j < n; j++)    
    {
      if (arr[j] < arr[min])     //这里是找最小的那个数,然后记下该下标
            {
        min = j;               
      }
    }
    if (i != min)         //这里如果i==min时,就不需要交换
    {
      int tmp = arr[i];
      arr[i] = arr[min];
      arr[min] = tmp;
    }
    Print(arr, 10);      //打印排序过程
  }
}
int main()
{
  int arr[10] = { 2,6,1,-2,-4,9,19,37,-15,0 };
  Sort_arr(arr,10);                              //实现排序的函数
  printf("排序后的数组:\n");
  Print(arr, 10);            //实现打印的函数
  return 0;
}


运行结果


e7271a9340114bdca36204f77ba1eaea.png


目录
相关文章
|
监控 安全 数据安全/隐私保护
云通信短信服务安全事项
云通信短信服务安全事项
|
开发工具 Android开发 Windows
Android sdk下载安装配置教程
Android sdk下载安装配置教程
Android sdk下载安装配置教程
|
11月前
|
C语言 开发者
C语言实现猜数字小游戏(详细教程)
C语言实现猜数字小游戏(详细教程)
|
小程序 Python
用Python制作一个桌面宠物,真好玩!
用Python制作一个桌面宠物,真好玩!
336 2
|
11月前
|
Java 数据库 Spring
java读取配置文件数据
java读取配置文件数据
376 0
|
搜索推荐 C语言 C++
【排序算法】C语言实现归并排序,包括递归和迭代两个版本
【排序算法】C语言实现归并排序,包括递归和迭代两个版本
319 1
|
缓存 移动开发 算法
[计算机网络(第八版)]第三章 数据链路层(学习笔记)
[计算机网络(第八版)]第三章 数据链路层(学习笔记)
|
存储 缓存 人工智能
[计算机网络(谢希仁 第八版)]第一章 概述(小节随堂测验+答案解析)
[计算机网络(谢希仁 第八版)]第一章 概述(小节随堂测验+答案解析)
atoi函数(想要彻底了解atoi函数,那么看这一篇就足够了!)
atoi函数(想要彻底了解atoi函数,那么看这一篇就足够了!)
|
C语言
PTA 浙大版《C语言程序设计(第3版)》题目集 习题8-4 报数 (20分)
PTA 浙大版《C语言程序设计(第3版)》题目集 习题8-4 报数 (20分)