选择排序算法原理
从头至尾查找最小的一个元素，然后和第一个元素交换，接着从剩下的元素中继续这种选择和交换方式，最终得到一个有序数组。
思路：
步骤1：先假设数组第1个元素为最小，记录目前最小下标，然后以最小下标的数字进行依次比较，如果出现比目前还小的数字，则更新最小下标。
步骤2：找打整个数组最小下标后，将最小的下标数字与假设的数字进行换位。
- 从剩余的数字中，重复上述步骤，再找到剩余数字中最小，然后交换。最终得到一个有序数组。
举例：数组：[3,7,2,1,4] 选择排序
- 第一次，在
中找最小数字
1、先假设一个最小下标：每次都以数组剩余个数最左边的下标假设为最小下标【故第一次时：假设最小下标为0】。
2、拿假设的最小下标0，进行依次比较，找到实际最小下标：
最小下标0，与下标1比较【3小于7，最小下标不变】
最小下标3，与下标4比较【1小于4，最小下标不变】
3、找到整个数组中最小的数字下标，将实际最小数字，与假设最小数字进行位置交换。
- 第二次，
第一次最终结果：[1,7,2,3,4]
1、还是先假设一个最小下标：第二次从[1,7,2,3,4]里假设一个最小下标
2、拿假设的最小下标1，进行依次比较，找到实际最小下标：
最小下标1，与下标2比较【7大于2，最小下标更新为2】
最小下标2，与下标3比较【2小于3，最小下标不动】
最小下标2，与下标4比较【2小于4，最小下标不动】
3、找到整个数组中第二小的数字下标，将实际第二小数字，与假设第二小数字进行位置交换。
- 第三次，
第二次最终结果：[1,2,7,3,4]
1、还是先假设一个最小下标：第三次从[1,2,7,3,4]里假设一个最小下标
2、拿假设的最小下标2，进行依次比较，找到实际最小下标：
最小下标2，与下标3比较【7大于3，最小下标更新为3】
最小下标3，与下标4比较【3小于4，最小下标不动】
3、找到整个数组中第三小的数字下标
- 第四次，
第三次最终结果：[1,2,3,7,4]
1、还是先假设一个最小下标：第四次从[1,2,3,7,4]里假设一个最小下标
2、拿假设的最小下标3，进行依次比较，找到实际最小下标：
最小下标3，与下标4比较【7大于4，最小下标更新为4】
3、找到整个数组中第四小的数字下标，将实际第四小数字，与假设第四小数字进行位置交换。
规律
从上述例子中，发现一个规律：
- 总查找最小数字次数是数组长度-1，因为当找到数组第二大数字时，与剩余数字交换位置后，已经形成最终排序结果。
- 每次进行剩余数字找最小数字时，数组前面的都不需要进行比较处理了。
- 每次比较，都是已假设下标的下一个下标进行开始比较。因为假设最小下标前的元素已经处理好了，不需要处理。假设最小下标自己占用一个下标。
- 每次比较，不需要进行换位处理，待找到最小数字下标后，才做换位处理。
- 每次换位时，如果假设最小下标真的是最小下标，那么不需要进行换位处理。
java代码
int[] a = {3, 7, 2, 1, 4};
// 总查找最小次数，小于数组长度-1，因为最后2个数只需要找一次就好了。
for (int i = 0; i < a.length - 1; i++) {
int min = i; // 先假设 i 是最小下标
for (int j = i + 1; j < a.length; j++) {
/*int j = i, 就是从剩余数字中找最小数字下标。
* int j = i + 1, 是因为假设最小下标，已经算作一个了。故从最小下标下一个元素进行比较。
*
* 判断剩余元素中，是否存在小于最小下标元素的数字。
* 无：最小下标不更新。
* 有：说明假设最小下标错误，更新最小下标。
* 然后接着往后比较，
* 看有没有比当前已找到的最小下标，
* 还小的数字。
*/
if (a[j] < a[min]) {
min = j;
}
}
/*
* 确认：假设最小下标是否成立？
* 成立：不需要做换位处理。
* 不成立：做换位处理。
*/
if (min != i) {
int tmp = a[i];
a[i] = a[min];
a[min] = tmp;
}
}
网友评论