1.直接选择排序的基本思想
N个元素,每次挑出最大或者最小,执行(n-1)次循环。实际上选择排序是最简单的一种排序算法，因为它的思想非常朴素，每趟都选出剩余中最大或者最小的排在已经排好的数据后面。
2.直接选择排序的具体步骤
从待排序序列中，找到关键字最小的元素；
如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换；
从余下的 N - 1 个元素中，找出关键字最小的元素，重复1，2步，直到排序结束。
直接插入排序示意图
3.直接选择排序分析
（1）时间复杂度
直接选择排序的排序码比较次数KCN 与整个待排序对象序列象的初始排列无关。KCN=∑n−2i=0(n−i−1)=n(n−1)2。
移动次数：最好的时候为0；最坏的时候为3(n−1)；
说明一下：基本上所有的排序算法最后的时候都是对应着已经完全排好序了，而最坏的时候通常都是反序排列。
所以，综合以上，简单排序的时间复杂度为 O(N2)。
（2）空间复杂度
简单选择排序需要占用一个临时空间，在交换数值时使用。
（3）特点
a.对于大数据表效率不高；
b.简单；
c.重复执行相同的工作，并没有从上一次的迭代中学到任何有助于的排序的知识。
d.移动次数可能是排序算法中比较好的了。如果采用in-place的数据交换方法，选择排序数据项的移动次数就一直为0。
e.不是一个稳定排序（从给的图示就可以看出）
单纯从每趟的效果上看，选择排序挑选最大或最小与冒泡算法有点类似，都是将剩下中的最大最小排起来，唯一的区别是冒泡算法是临近的两个数据项如果逆序就会交换，而选择排序不进行交换，只是在选定最值后进行交换。因此选择排序实际上并没有学到什么东西，每次迭代就是为了排好一个。而冒泡排序通过逆序的两个两两交换能够使得最值冒出来，而且还能实现未排序部分的初排序，最后能够通过判定是否发生交换提前终止迭代。
4.直接选择排序算法C语言源代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 | /** * 算法君：一个专业的算法学习分享网站 * 算法君：专业分享--数据剖析--算法精解 * 算法君：http://www.suanfajun.com */ #include "stdio.h" /* * 函数：choose_sort(int *array, int n) * 功能：插入排序 * 参数：n为数组元素的个数 */ void choose_sort(int array[],int n) { int i,j; int b,temp,num; for(i=0;i<n-1;i++) { temp=i; for(j=i+1;j<n;j++) { if(array[j]<=array[temp])//获取待排序的元素中最小的元素 { temp=j;//记录最小元素的下标 } } if(i!=temp) { b=array[temp]; array[temp]=array[i]; array[i]=b; } } } int main(int argc,char *argv[]) { int array[]={3,8,4,7,1}; choose_sort(array,5); for(int i=0;i<5;i++) { printf("%d ",array[i]); } printf("\n"); return 0; } |
5.直接选择排序算法C++源代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 | /** * 算法君：一个专业的算法学习分享网站 * 算法君：专业分享--数据剖析--算法精解 * 算法君：http://www.suanfajun.com */ #include <iostream> using namespace std; void swap(int *n, int *m) { int tmp; tmp = *m; *m = *n; *n = tmp; } void print(int a[], int sz) { for (int i = 0; i < sz; i++ ) cout << a[i] << " "; cout << endl; } void SelectionSort(int a[], int sz) { int i,j,mn; /* traverse the entire array */ for (i = 0; i < sz; i++) { /* find the min */ mn = i; /* compare against all other elements */ for (j = i + 1; j < sz; j++) { if (a[j] < a[mn]) mn = j; } swap(a[mn], a[i]); print(a,sz); } } int main() { int a[] = {4,6,9,1,2,0,8,7,5,3}; const size_t sz = sizeof(a)/sizeof(a[0]); print(a,sz); cout << "---------------------\n" ; SelectionSort(a, sz); } |
