背景
爱炒股票短线的人,总是喜欢不断的买进卖出,想通过价差来实现盈利。但通常这种频繁操作的人,即使失误不多,也会因为操作的手续费和印花税过高而获得很少。
还有一种做股票的人,他们很少出手,只是在不断的观察和判断,等到时机一到,果断买进或卖出。
这些人因为冷静和沉着,以及交易的次数少,而最终收益颇丰。
冒泡排序的思想是不断地在交换,通过交换完成最终的排序,这和做股票短线频繁操作的人是类似的。
我们可不可以像只有在时机非常明确到来时才出手的股票高手一样,也就是在排序时找到合适的关键字再做交换,并且只移动一次就完成相应关键字的排序定位工作。
选择排序的算法思想就是受到股票高手的启发,并通过计算机的编程语言加以实现。
算法实现
预先定义排序的数据结构、公共函数,代码放在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