默认数组为升序
选择排序：
一趟选择排序的操作为：通过n-1次关键字间的比较，从n-i个记录中选出关键字最小的记录，并和第i(0<=i<n)个记录进行交换。
一共需要进行n-1趟选择排序。
排序的数组为{6, 2, 8, 1, 4, 9, 3, 0, 5, 7};
选择排序代码
#include<iostream>
using namespace std;
swap( int array[], int j ) { //交换方法
int temp = array[j];
array[j] = array[j-1];
array[j-1] = temp;
}
void insertSort( int array[] ) {//选择排序方法
for( int i = 0; i < 9; i++ ) {
for( int j = i+1; j > 0; j-- ) {
if( array[j] < array[j-1] ) {
swap( array, j );
}
else {
break;
}
}
}
}
int main() {
int array[] = {6, 2, 8, 1, 4, 9, 3, 0, 5, 7};
insertSort( array ); //调用选择排序方法
for( int i = 0; i < 10; i++ ) {
cout << "array[" << i << "] = " << array[i] << endl;
}
}
选择排序原理
如，对数组{6, 2, 8, 1, 4, 9}6个数字进行排序
数组
第一趟循环
找出最小的数字array[3]=0，与array[0]=6进行交换。确定了第一小的数字“1”
第二趟循环
此时，最小的数字即array[1]本身。确定了第二小的数字“2
第三趟循环
此时，找出最小的数字array[4]=4，与array[2]=8进行交换。确定了第三小的数字“4”
第四趟循环
此时，最小的数字即array[3]本身。确定了第四小的数字“6”
最后两次循环
确定后最后两位数字，第五小的数字“8”，以及最大的数字“9”
根据上图可知，每一趟循环可以确定一个最小的数值
再看如下例子
| 比较次数 | 6 | 2 | 8 | 1 | 4 | 9 | 3 | 0 | 5 | 7 |
|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 0 | 2 | 8 | 1 | 4 | 9 | 3 | 6 | 5 | 7 |
| 2 | 0 | 1 | 8 | 2 | 4 | 9 | 3 | 6 | 5 | 7 |
| 3 | 0 | 1 | 2 | 8 | 4 | 9 | 3 | 6 | 5 | 7 |
| 4 | 0 | 1 | 2 | 3 | 4 | 9 | 8 | 6 | 5 | 7 |
| 5 | 0 | 1 | 2 | 3 | 4 | 9 | 8 | 6 | 5 | 7 |
| 6 | 0 | 1 | 2 | 3 | 4 | 5 | 8 | 6 | 9 | 7 |
| 7 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 8 | 9 | 7 |
| 8 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 9 | 8 |
| 9 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
- 在第一层循环中：
首先min=array[i],mini=i;- min和array[1]比较，min>array[1]，则：min=array[1],mini=1;
- min和array[2]比较，min<array[2]，则无需改变min与mini;
- min和array[3]比较，min>array[3]，则：min=array[3],mini=3;
…… - min和array[9]比较，min>array[9]，则无需改变min与mini;
- 第一层循环排序的结果为：
0, 2, 8, 1, 4, 9, 3, 6, 5, 7 - 同理，第二层排序的结果
0, 1, 8, 2, 4, 9, 3, 6, 5, 7 - 第三层排序结果：
0, 1, 2, 8, 4, 9, 3, 6, 5, 7
…… - 第八层排序结果：
0, 1, 2, 3, 4, 5, 6, 7, 9, 8 - 第九层排序结果：
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
综上可得：
升序排序中，外层循环每循环一次，都会将最小的数字与当前位的数字进行交换。
如果大家有什么问题，可以在评论区中向我提问。
今天更新的是选择排序，后天我会更新“插入排序”，是三大排序中难度相对较大的。希望我的文章对大家有一定的帮助！
