逍遥游

选择排序------简单直观的排序算法

选择排序(Selection sort)也是一种经典排序算法(话说经典排序算法好多),它是一种简单直观的排序算法。个人觉得,选择排序算法的原理比冒泡排序算法更容易理解。

算法原理/步骤

  1. 从第一个元素开始,查找序列中最小的元素;
  2. 将该元素与第一个元素交换;
  3. 从下一个元素开始,查找剩下元素中最小的元素;
  4. 重复操作2、3直到找出最后一个元素。
    Selection_sort_animation
    (维基好呀)

时间复杂度

从算法原理中可以看到,每次选择一个最小元素,故原序列第K个位置上的元素恰需要N-K次比较和1次交换,故最优、最差、平均时间复杂度均为O(N^2)。

稳定性

选择排序中相同元素相对位置不会改变,所以是稳定的排序。

算法演示

下面给出是对数据{6,5,3,1,2,4}进行排序的过程演示。

Step 1 {1},{6,5,3,2,4}

Step 2 {1,2},{6,5,3,4}

Step 3 {1,2,3},{6,5,4}

Step 4 {1,2,3,4},{6,5}

Step 5 {1,2,3,4,5},{6}

Step 6 {1,2,3,4,5,6}

实例代码

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
47
48
49
50
51
52
53
54
55
56
57
58
#include<iostream>
#include<cstdlib>
#include<ctime>
using namespace std;
#define MAXN 10
int select_sort(int *, int);
int main()
{
int src[MAXN];
//先随机生成MAXN个数字,做测试用
for(int i=0; i<MAXN; i++)
src[i] = rand()%10000;
/**输出原始数据*/
for(int i=0; i<MAXN; i++)
cout<<src[i]<<" ";
cout<<endl;
/**执行选择排序*/
select_sort(src, MAXN);
/**检查排序结果*/
for(int i=0; i<MAXN-1; i++)
{
if(src[i] > src[i+1]){
cout<<"wrong"<<endl;
}
}
cout<<"sort finished!"<<endl;
return 0;
}
/*
* 选择排序
* @param int* src 待排序数组
* @param int size 待排序数组大小
* 默认执行升序排序
*/
int select_sort(int *src, int size){
int min;
/*找出第i小的元素并将该元素放在第i位上*/
for(int i=0; i<size; i++)
{
min=i;
//跟它后面的元素比较,选出从第i位开始最小的
for(int j=i+1; j<size; j++)
{
min=src[j] < src[min]?j:min;
}
//交换使得第i位上元素为第i小元素
swap(src[i], src[min]);
}
return 0;
}

算法改进

好像没有吧,反正我是不知道。

总结

原地操作几乎是选择排序的唯一优点,当方度(space complexity)要求较高时,可以考虑选择排序;实际适用的场合非常罕见。

详细代码请点击这里查看。


多说停止服务,disqus引导注册太过分,暂时不上评论系统了。有机会自己造轮子吧。邮箱:input@newnius.com