简单的选择排序原理为比较剩余未排序的记录,找到一个最小的与当前关键字互换位置。显然选择排序算法的性能优劣主要取决于选择最小关键字的位置,下面实现的是逐个查找其它关键字记录。当然,也可以使用前面我们所学习的其它查找算法,例如折半查找。
#include <stdio.h> #define SIZE (10) //找到最小值 int min_ind(int *array, int size, int start) { int index = -1; int t = -1; for (int i = start; i < size; i++) { if (i == start) { t = array[i]; index = i; } //找到最小值并记录其位置 if (array[i] < t) { t = array[i]; index = i; } } return index; } //选择排序 void select_sort(int array[], int size) { for (int i = 0; i < size; i++) { int ind = min_ind(array, size, i); //如果当前关键字小于最小值 if (array[ind] < array[i]) { //互换位置 int t = array[i]; array[i] = array[ind]; array[ind] = t; } } } //显示数组 void display(int *array, int size) { for (int i = 0; i < size; i++) { printf("%d ", array[i]); } printf("\n"); } int main(int argc, char **args) { int array[SIZE] = { 5, 3, 7, 2, 9, 8, 1, 0, 6, 4 }; display(array, SIZE); select_sort(array, SIZE); display(array, SIZE); return 0; }
运行结果:
5 3 7 2 9 8 1 0 6 4 0 1 2 3 4 5 6 7 8 9
本例代码:
code path chapter.08/e.g.8.5/ https https://github.com/magicworldos/datastructure.git git git@github.com:magicworldos/datastructure.git subverion https://github.com/magicworldos/datastructure
Copyright © 2015-2023 问渠网 辽ICP备15013245号