摘要：选择排序，简单粗暴直观的排序算法。我们跑一趟无序序列，把最小值和最大值都找出来。
选择排序，简单粗暴直观的排序算法。
一个长度为N的序列num[N]，分为有序部分和无序部分
第一次，num[0]~num[N-1]是无序部分，从这N个数中选出最小的数，放在序列的第一个位置，
此时，num[0]是有序部分，num[1]~num[N]是无序部分
第二次，num[0]是有序部分，num[1]~num[N]是无序部分，从N-1个数中选出最小的数，放在序列的第二个位置，
此时，num[0]~num[1]是有序部分，num[2]~num[N]是无序部分
如此进行下去，整个序列最终为有序（顺序）序列
代码：
#include#define N 10void selectsort(int *num , int length ){ int i ; int j; int temp;//中间变量，供交换值的时候使用 for(i = 0;i < length ; i ++)//假设无序序列的第一个元素num[i]为最小值 { for(j = i+1 ; j < length ;j++)//遍历最小值后面的所有元素(num[i+1]~num[length-1]) { if(num[i] > num[j])//若找到比最小值num[i]还要小的元素，则与原来的最小值元素交换值 { temp = num[i]; num[i] = num[j]; num[j] = temp; } } }}int main(){ int num[N] = {9,8,7,6,5,4,3,2,1,0}; selectsort(num , N); for(int i=0; i < N;i++) { printf("%d ",num[i]); } printf("/n"); return 0;} 运行结果
看一下程序细节
时间复杂度
第一次需要遍历N-1个元素，第二次需要遍历N-2个元素······
所以时间复杂度是）O（N^2）
然而，细想一下，选择排序，每一趟遍历无序部分，却只为了找到那个最小的数，效率太低（老子辛辛苦苦在无序序列兜了一圈，只找一个最小值，这哪行，哪像计算机人搜搜扣扣的精神（又扣时间又扣空间））
于是，赶一只羊也是赶，赶两只羊也是赶。我们跑一趟无序序列，把最小值和最大值都找出来。
代码：
#include#define N 10#includevoid swap(int *a,int *b)//函数作用，交换a和b的值{ int temp ; temp = *a; *a = *b; *b = temp;}void selectsort(int *num ,int n){ int start = 0;//无序部分的第一个元素 int end = N-1;//无序部分的最后一个元素 while(start < end) { int min_index = start;//最小值元素的下标 int max_index = end;//最大值元素的下标 int i = 0; for(i = start;i<=end;i++)//遍历无序序列 { if(num[i] < num[min_index]) min_index = i;//记录无序序列最小值元素的下标 if(num[i] > num[max_index]) max_index = i; //记录无序序列最大值元素的下标 } swap(&num[start],&num[min_index]);//将找到的最小值放在序列开头 //错误语句实例 swap(&num[end],&num[max_index]); //将找到的最大值放在序列末尾，看似合情合理，但在极端情况下与上一句语句是矛盾的 //本例就属于极端情况，此处挖一个坑 if(start == max_index)//极端情况，当最大值位于序列开头，要被最小值替换 { max_index = min_index; } start++;//缩小无序序列长度，因为有序序列变长了 end--; //细节演示 // for(int i = 0;i 运行结果：
程序细节：
对比单向选择排序算法，双向选择排序虽然时间复杂都仍然是O(N^2),但是效率优化了50%左右
填坑：
我们需要排序的序列是num[10] = {9，8，7，6，5，4，3，2，1，0}
先来看一下错误代码
错误细节，每一次遍历序列的变化
可以看到 ，第一次遍历，最小值下标是9，最大值下标是0，处理过程是将num[min_index]放在序列开头,num[max_index]放在序列末尾，即num[0] <——>num[9],即num[0]和num[9]只需要一次换值；
但是因为执行两次swap()（换值函数），相当于原来序列并没有发生变化
在以后的遍历中，也是这种情况，所以最终结果是序列没有任何变化，也就不难理解为何代码要做如下处理
正确代码
正确细节，每一次遍历序列的变化
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/124094.html
摘要：想快速入门数据结构，推荐订阅作者的初阶数据结构专栏此专栏预计更新顺序表，链表，栈，队列，二叉树，排序算法等等初阶数据结构我们通过语言实现，所以此专栏也可以帮助大家巩固大家的语言知识源代码已上传至我的码云前言非常感 ...
摘要：当到达时等同于直接插入排序，此时序列已基本有序，所有记录在统一组内排好成有序序列。当面对大量数据时，希尔排序将比直接插入排序更具优势图示讲解第一趟取增量，所有间隔为的元素分在一组，在各个组中分别进行直接插入排序。 ...
摘要：再谈大表示法快速排序的独特之处在于其速度取决于选择的基准值。在平均情况下快速排序的运行时间为在最糟情况下退化为。快速排序和合并排序的算法速度分别表示为和，是算法所需的固定时间量被称为常量。 分而治之 分而治之(divide and conquer,D&C)是一种著名的递归式问题解决方法。只能解决一种问题的算法毕竟用处有限,而D&C提供了解决问题的思路,是另一个可供你使用的工具。 D&C...
摘要：强烈推荐上值得前端学习的数据结构与算法项目，包含图的演示过程与视频讲解。该仓库包含了多种基于的算法与数据结构，提供进一步阅读的解释和链接。数据结构和算法必知必会的个代码实现。 showImg(https://segmentfault.com/img/bVbvpYZ); 前言 算法为王。想学好前端，先练好内功，内功不行，就算招式练的再花哨，终究成不了高手；只有内功深厚者，前端之路才会走得...
摘要：题目语言实现现插入排序算法把数字由小到大进行排序插入排序是把一个记录插入到已排序的有序序列中，使整个序列在插入该记录后仍然有序。 1、题目 C语言实现现插入排序算法把数字由小到大进行排序 插入排序是把一个记录插入到已排序的有序序列中，使整个序列在插入该记录后仍然有序。插入排序...
阅读 720·2021-11-22 09:34
阅读 827·2021-10-08 10:16
阅读 3940·2021-09-09 09:33
阅读 1571·2021-07-25 21:42
阅读 1678·2019-08-30 15:53
阅读 3376·2019-08-30 13:08
阅读 2020·2019-08-29 17:30
阅读 3175·2019-08-29 17:22
