黑马程序员技术交流社区
标题: 【算法】选择排序 [打印本页]
作者: 倾心莫若初见 时间: 2016-12-15 15:38
标题: 【算法】选择排序
本帖最后由 倾心莫若初见 于 2016-12-15 17:42 编辑
选择排序的根本原理是默认第一个数为最值，第一个数的下标记为最值下标，从当前数字开始，用最值数字与其他各数字比较，把符合条件的数字下标记为最值下标，再继续使用新的最值数字与下一个数比较，直到一次循环结束，被记录下的位置一定是所有数中的最值，然后把这个数字和当前数字交换。例子如下:
假设有一个数列 2,1,3,6,8,7,4,9,5,0 共有10个数字
如果我们要从小到大排序，可按以下步骤：
1) 默认第一个数字2为最小值，定义min变量记录最值下标0
2) 把 最小值2 和 1 比较，2 比 1 大，所以更新最小值下标为1
3) 再把最小值 1和 3 比较，1比 3 小，最小值下标不需要更新，递进到下一个位置
4) 最小值1 和 6 比较，1 比 6 小，最小值下标不需要更新，递进到下一个位置
5) 最小值1 和 8 比较，1 比 8 小，最小值下标不需要更新，递进到下一个位置
6) 最小值1 和 7 比较，1 比 7 小，最小值下标不需要更新，递进到下一个位置
7) 最小值1 和 4 比较，1 比 4 小，最小值下标不需要更新，递进到下一个位置
8) 最小值1 和 9 比较，1 比 9 小，最小值下标不需要更新，递进到下一个位置
9) 最小值1 和 5 比较，1 比 5 小，最小值下标不需要更新，递进到下一个位置
10)最小值1 和 0 比较，1 比 0 大，更新最小值下标为数字0的下标9
11)一次循环结束，找到最小值为0，最小值下标为9，把最小值和当前值（第一个数字2）交换，结果如下：
0,1,3,6,8,7,4,9,5,2
12)这样就排好一个数字，接下来循环递进，把1作为默认最小值，1的下标作为最小值下标，继续与1后面的所有数字遍历比较
每次把以上的步骤执行一遍都会排好一个数，那10个数最多执行9遍就可以了，所以外循环的次数是总次数减一，而内循 环的值是从外循环的下一个位置开始，直到最后一个下标结束，代码如下：
int main()
{
int arr[10] = {2,1,3,6,8,7,4,9,5,0 }; //定义10个数的数组
int min = 0; //定义变量 min 记录下最小值的下标
for (int i = 0; i < 10 -1; ++i) //每次排好一个数,10个数最多排9次
{
min= i; //默认当前数为最小值,记录下最小值下标
for (int j = i + 1; j <10; ++j) //内循环从i的下一个数开始，到最后结束
{
if (arr[min] >arr[j]) //如果后面某个数比当前最小值还小
{
min= j; //把后面的数作为最小值，记录下它的下标
}
}
//经过上面这个循环，就找到了最小值的下标 min
if (min != i) //如果 min = i,代表i位置的数本身就是最小值，不需要交换
{
//交换最小值到当前位置
int temp = arr;
arr= arr[min];
arr[min]= temp;
}
}
//输出排好后的数组
for (int i = 0; i < 10;++i)
{
printf("%d ", arr);
}
return 0;
}
| 欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) |
黑马程序员IT技术论坛 X3.2 |