选择排序(selection sort)是一种简单直观的排序算法。
选择排序(由小到大的顺序)的工作原理如下：首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
初始序列： 70 75 69 32 88 18 16 58
1 2 3 4 5 6 7 | 16 75 69 32 88 18 70 58 16 18 69 32 88 75 70 58 16 18 32 69 88 75 70 58 16 18 32 58 88 75 70 69 16 18 32 58 69 75 70 88 16 18 32 58 69 70 75 88 16 18 32 58 69 70 75 88 |
经过7轮排序后，8个数的排序完毕。
第一轮的排序代码如下所示：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | #include <stdio.h> int main(int argc, char *argv[]) { int a[8]= {70,75,69,32,88,18,16,58}; int j, k, t, n=8; k=0; /* 假定第0个位置的数最小 */ for(j=1; j<n; j++) /* 寻找最小数所在的位置*/ if (a[j]<a[k]) k=j; t=a[k]; a[k]=a[0]; a[0]=t; /* 交换a[0]和最小数 */ for (j=0; j<n; j++) printf("%4d", a[j]); printf("\n"); /* 执行完毕后， 第0个数最小 */ return 0; } |
为了让程序更具通用性，将上述代码中的 0 替换为更一般的变量 i，则程序如下所示：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | #include <stdio.h> int main(int argc, char *argv[]) { int a[8]= {70,75,69,32,88,18,16,58}; int i, j, k, t, n=8; i=0; /* 开始一轮排序 */ k=i; for(j=i+1; j<n; j++) /* 寻找最小数所在的位置*/ if (a[j]<a[k]) k=j; t=a[k]; a[k]=a[i]; a[i]=t; /* 交换a[i]和最小数 */ for (j=0; j<n; j++) printf("%4d", a[j]); printf("\n"); /* 执行完毕后， 前0..i个数最小 */ return 0; } |
如果要进行小小的优化，可以判断 k和 i 是否相等。如果相等，就不必交换。
1 | if (k!=i) { t=a[k]; a[k]=a[i]; a[i]=t; } /* 交换a[i]和最小数 */ |
待排序的范围有变量 i 来决定。当 i 从 0 遍历至 n-2，就依次使得第0个~第n-2个数有序。最后剩下一个数，就不必再排序了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | #include <stdio.h> int main(int argc, char *argv[]) { int a[8]= {70,75,69,32,88,18,16,58}; int i, j, k, t, n=8; for (i=0; i<n-1; i++) { k=i; for(j=i+1; j<n; j++) if (a[j]<a[k]) k=j; t=a[k]; a[k]=a[i]; a[i]=t; for (j=0; j<n; j++) printf("%4d", a[j]); printf("\n"); } return 0; } |
输出结果，也就是选择排序的过程
1 2 3 4 5 6 7 | 16 75 69 32 88 18 70 58 16 18 69 32 88 75 70 58 16 18 32 69 88 75 70 58 16 18 32 58 88 75 70 69 16 18 32 58 69 75 70 88 16 18 32 58 69 70 75 88 16 18 32 58 69 70 75 88 |
