算法原理

直接选择排序的基本思想：n个记录的直接选择排序可经过 n-1 趟直接选择排序得到有序结果。

初始状态：无序区为 A[1...n]，有序区为空。

第 1 趟排序：在无序区 A[1...n] 中选出最小的记录A[k]，将它与无序区的第 1 个记录 A[1] 交换，使 A[1…1] 和 A[2...n] 分别变为记录个数增加1的新有序区和记录个数减少1 的新无序区。

第 i 趟排序：第 i 趟排序开始时，当前有序区和无序区分别为 A[1… i-1] 和 A[i.. n](1 ≤ i ≤ n-1)。该趟排序从当前无序区中选出关键字最小的记录A[k]，将它与无序区的第1 个记录A[i] 交换，使 A[1…i] 和 A[i+ 1...n] 分别变为记录个数增加 1 的新有序区和记录个数减少 1 的新无序区。

这样，n个记录的文件的直接选择排序可经过 n-1 趟直接选择排序得到有序结果。直接选择排序是不稳定的。

算法草稿

三角列表示本轮排序后的结果

代码实现

#include #include #define SUCCESS0#define PARAM_ERR-1 int getMinPoS(int * array, int low, int high){if(NULL == array || low > high){printf("%s para error", __func__);return PARAM_ERR;}int i = 0;int minPoS = low;int min = array[low]; /*千万注意这里是 <= high, 因为数组的最后一个是high (n-1)*/for(i = low; i <= high; i++){if(array[i] < min ){minPoS = i;min = array[i];}} return minPoS;} int SelectSort(int * array, int size){if(NULL == array){printf("%s para error", __func__);return PARAM_ERR;} int i = 0, j = 0;int minPoS = 0; /*当前无序区最小值的位置*/int temp = 0;#ifdef DEBUGint k = 0;#endif for(i = 0; i < size; i++){ /* 无序区域起始位置逐步向后 *//*无序区处理，此时 i 还属于无序区，无序区为 [i,.... n-1], 找到无序区最小位置minPoS*//*升序*/minPoS = getMinPoS(array, i, size - 1); /* 交换最小值到i，通过i++, 将i并入有序区域 */if(minPoS != i){temp = array[minPoS];array[minPoS] = array[i];array[i] = temp;} #ifdef DEBUGprintf("i = %d min = %d", i, temp);printf("[");/*有序区域*/for(k =0; k < i+1; k++){printf(" %d ", array[k]);}printf("] "); /*无序区域*/printf("[");for(k = i+1; k < size; k++){printf(" %d ", array[k]);}printf("]");printf("");#endif} return SUCCESS;} int main(int argc, char ** argv){int array[10] = {7,3,5,8,0,9,1,2,4,6};int i = 0; printf("Before sort: ");for(i = 0; i < 10; i++){printf(" %d ", array[i]);}printf(""); SelectSort(array, 10); printf("after sort: ");for(i = 0; i < 10; i++){printf(" %d ", array[i]);}printf("");return 0;}

调试编译

gcc SelectSort.c -DDEBUG

调试输出

Before sort: 7 3 5 8 0 9 1 2 4 6i = 0 min = 0[ 0 ] [ 3 5 8 7 9 1 2 4 6 ] i = 1 min = 1[ 0 1 ] [ 5 8 7 9 3 2 4 6 ] i = 2 min = 2[ 0 1 2 ] [ 8 7 9 3 5 4 6 ] i = 3 min = 3[ 0 1 2 3 ] [ 7 9 8 5 4 6 ] i = 4 min = 4[ 0 1 2 3 4 ] [ 9 8 5 7 6 ] i = 5 min = 5[ 0 1 2 3 4 5 ] [ 8 9 7 6 ] i = 6 min = 6[ 0 1 2 3 4 5 6 ] [ 9 7 8 ] i = 7 min = 7[ 0 1 2 3 4 5 6 7 ] [ 9 8 ] i = 8 min = 8[ 0 1 2 3 4 5 6 7 8 ] [ 9 ] i = 9 min = 8[ 0 1 2 3 4 5 6 7 8 9 ] [] after sort: 0 1 2 3 4 5 6 7 8 9

总结

以上是生活随笔为你收集整理的c语言对n个数选择排序_选择排序法 -- C语言的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。