算法-排序-选择

算法-排序

2 选择排序

特点

  • 不稳定(你也许没听懂)
  • 较简单(至少我认为)

简介

选择排序,顾名思义,选择一个数,放到相应的位置.

演示

原始数据(8个)
7 4 8 3 2 5 1 6

第一次排序
1 4 8 3 2 5 7 6

第二次排序
1 2 8 3 4 5 7 6

第三次排序
1 2 3 8 4 5 7 6

第四次排序
1 2 3 4 8 5 7 6

第五次排序
1 2 3 4 5 8 7 6

第六次排序
1 2 3 4 5 6 7 8

演示解析

从数据变化中我们可以看出,每一次都选择了未排序的子序列中的最小值和当前要排序的值进行交换.

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int FindiMin(int array[], int n, int start)  //找到array[start] ~ array[n - 1]中的最小值
{
int imin = start;
for(int i = start + 1; i < n; i++)
{
if(array[i] < array[imin])
{
imin = i;
}
}
return imin;
}
void Sort(int array[], int n)
{
for(int i = 0; i < n; i++)
{
int imin = FindiMin(array, n, i);
swap(array[imin], array[i]);
}
}

END

选择排序还是一种比较简单的排序方法,接下来还有插入、快速、堆、桶排序等.