选择排序基本思想
基本思想：在未排序序列中选取最小元素与序列第一位交换，接下来再从剩下的未排序序列`中选取最小值与整个序列第二位交换,依次类推，最后形成从小到大的已排序序列
选择排序动画演示：
##简单选择排序源码
SimpleSelectSort.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#include <stdio.h>
#include <stdlib.h>
#include "math.h"
#include "SortHelper.h"
// 时间复杂度 O(n^2) 空间复杂度O(1):只声明了i，j，minIndex等变量
void selectionSort(int * arr, int n)
{
int i ;
for(int i = 0 ; i < n ; i ++){ // n-1趟
// 寻找[i, n)区间里的最小值
int minIndex = i;
for( int j = i + 1 ; j < n ; j ++ ) // 寻找[i,n-1]中最小值元素
if( arr[j] < arr[minIndex] )
minIndex = j;
if (minIndex != i) {
swap( arr[i] , arr[minIndex] );
}
}
}
int main(void)
{
int n = pow(10, 5);
int *arr = generateRandomArray(n, 0, n);
int *arr1 = generateNearlyOrderArray(n, 100);
int *arr2 = generateRandomArray(n, 0, 10);
testSort("simple seletion sort RandomArray", selectionSort, arr, n);
testSort("simple seletion sort NearlyOrderArray", selectionSort, arr1, n);
testSort("simple seletion sort RandomArray [0,10]", selectionSort, arr2, n);
return 0;
}
Clion运行结果如下：(数据规模：100000 十万)
总结
时间复杂度：O(n^2) 指的是平均时间复杂度空间复杂度：O(1) 只开辟了i，j，minIndex等常数个空间
稳定性 ： 稳定的 元素关键字相等的两个元素进行比较时并不会发生交换，即相对位置不会发生变化
选择排序无论在什么情况下，都需要比较N*(N-1)/2次，故时间复杂度O(N^2).事实上，在将第i个元素与最小元素交换之前，我们可以判断一下，如果minIndex == i，则无需交换，那么简单选择排序移动元素ishu在最好的情况下时0次(序列已经有序),在最坏的情况下为3(N-1)次(除去最后一个元素外，每个元素都要经过3步交换位置)
pS:源代码链接