小朋友学C语言（27）：选择排序

小朋友学C语言（27）：选择排序

（一）基本原理（由小到大）：

如果有n个数，需要比较n-1轮： 第1轮，将n个数中最小的数与a[0]对换，当然若a[0]就是最小的数则不用对换。 第2轮，将a[1]到a[n-1]中最小的数与a[1]对换，当然若a[1]就是最小的数则不用对换。 …… 第n-1轮，将最后的两个数，即a[n-2]与a[n-1]比较，若a[n-2] > a[n-1]，则对换。至此，排序完毕。

（二）例子

例1：a[] = {5, 1, 2, 3, 4}

分析 ：需要比较n - 1 = 4轮。

第1轮，a[1]=1是5个元素中最小的，并且a[1]不等于a[0]，则对换a[1]与a[0]。对换后数组变为a[] = {1,5,2,3,4}

第2轮，对于a[]的后四个元素来说，a[2]=2是最小的，并且a[2]不等于a[1]，则对换a[2]与a[1]。对换后数组变为a[] = {1, 2, 5, 3, 4}

第3轮，对于a[]的后三个元素来说，a[3]=3是最小的，并且a[3]不等于a[2]，则对换a[3]与a[2]。对换后数组变为a[] = {1, 2, 3, 5, 4}

第4轮，对于a[]的最后两个元素来说，a[4]=4是最小的，并且a[4]不等于a[3]，则对换a[4]与a[3]。对换后数组变为a[] = {1, 2, 3, 4, 5} 至此，排序结束。

例2：b[] = {1, 3, 5, 4, 2, 6}

分析：需要比较n - 1 = 5轮。

第1轮，b[0]就是六个元素中最小的数，不用对换。

第2轮，对于后五个元素来说，b[4] = 2是最小的数，b[4]不等于b[1]，则对换b[4]和b[1]，对换后，数组变为b = {1, 2, 5, 4, 3, 6}。

第3轮，对于后四个元素来说，b[4] = 3是最小的数，b[4]不等于b[2]，则对换b[4]和b[2]，对换后，数组变为b = {1, 2, 3, 4, 5, 6}。

第4轮，对于后三个元素来说，b[3] = 4是最小的数，不用对换。

第5轮，对于最后两个元素来说，b[4] = 5是最小的数，不用对换。至此排序结束。

（三）编程实现

#include// 打印数组，方便观察结果void print_array(int a[], int n){ for(int i = 0; i < n; i++) { printf("%d ", a[i]); } printf("\n");}// 选择排序算法void select_sort(int a[],int n){ int i, j, min; // i代表比较的轮数，i的取值范围是0到n-2，共n-1轮 for(i = 0; i < n - 1; i++) { /* min表示本轮比较中，最小元素的下标。 这里先赋值为i，也就是本轮比较的首个元素所在的位置。 下面根据比较结果，有可能变化，也有可能不变。*/ min = i; // a[i]右侧的所有元素都与a[i]比较 for(j = i + 1; j < n; j++) { // 若发现有更小的数，把该数的下标赋值给min // min在这个循环里可能会不断变化，最后会停在最小数所在的下标 if(a[j] < a[min]) { min = j; } } // 如果min与i不相等，说明a[i]右侧有比a[i]更小的数（可能不止一个） // 则a[min]就是a[i]右侧最小的数，将a[i]与a[min]互换位置 if(min != i) { a[min] ^= a[i]; a[i] ^= a[min]; a[min] ^= a[i]; } printf("After %d round sort, the array is:", i + 1); print_array(a, n); }}int main(){ int b[] = {5, 1, 2, 3, 4}; int cnt = sizeof(b) / sizeof(int); select_sort(b, cnt); return 0;}

运行结果：

After 1 round sort, the array is:1 5 2 3 4 After 2 round sort, the array is:1 2 5 3 4 After 3 round sort, the array is:1 2 3 5 4 After 4 round sort, the array is:1 2 3 4 5

（四）程序分析：

n - 1 = 4轮比较中，共产生了十次循环。分别是 i = 0, j = 1 i = 0, j = 2 i = 0, j = 3 i = 0, j = 4 i = 1, j = 2 i = 1, j = 3 i = 1, j = 4 i = 2, j = 3 i = 2, j = 4 i = 3, j = 4

具体执行如下：

i = 0, min = 0 j = 1, 第一个if成立，min = 1 j = 2, 第一个if不成立，min仍然为1 j = 3, 第一个if不成立，min仍然为1。 j = 4, 第一个if不成立，min仍然为1。内循环结束，跳出内循环 。第二个if成立，a[0]与a[min]（即a[1]）对换，数组变为{1, 5, 2, 3, 4}

i = 1, min = 1 j = 2, 第一个if成立，min = 2 j = 3, 第一个if不成立，min仍然为2。 j = 4, 第一个if不成立，min仍然为2。内循环结束，跳出内循环 。第二个if成立，a[1]与a[min]（即a[2]）对换，数组变为{1, 2, 5, 3, 4}

i = 2, min = 2 j = 3, 第一个if成立，min = 3 j = 4, 第一个if不成立，min仍然为3。内循环结束，跳出内循环 。第二个if成立，a[2]与a[min]（即a[3]）对换，数组变为{1, 2, 3, 5, 4}

i = 3, min = 3 j = 4, 第一个if成立，min = 4。内循环结束，跳出内循环 。第二个if成立，a[3]与a[min]（即a[4]）对换，数组变为{1, 2, 3, 4, 5} 至此，外循环结束，跳出外循环，继续执行下面的代码。

（五）作业

编写代码； 断点调试； 默写。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。