先说说选择排序的思想:
每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。
稳定性和复杂度:
选择排序是不稳定的排序算法,时间复杂度最坏为O(n2),平均为O(n2),空间复杂度为O(1).
下面是我用C语言实现的选择排序的源代码,如果有什么不对的地方,请各位指出,谢谢。
#include <stdio.h>#include <stdlib.h>#include <assert.h>void selectSort(int array[], int size);void swap(int *value1, int *value2);void printArray(int *array, int size);int main(int argc, char const *argv[]){ int size = 0; scanf("%d", &size); assert(size > 0); int *array = (int *)calloc(size, sizeof(int)); int i = 0; for (i = 0; i < size; ++i) { scanf("%d", &array[i]); } selectSort(array, size); printArray(array, size); free(array); return 0;}void selectSort(int array[], int size){ assert(array != NULL && size > 0); int minIndex = 0; int i = 0; int j = 0; for (i = 0; i < size; ++i) { minIndex = i; for (j = i + 1; j < size; ++j) { if (array[j] < array[minIndex]) { minIndex = j; } } swap(&array[i], &array[minIndex]); }}void swap(int *value1, int *value2){ int tempValue; tempValue = *value1; *value1 = *value2; *value2 = tempValue;}void printArray(int *array, int size){ assert(array != NULL && size > 0); int i = 0; for (i = 0; i < size; ++i) { printf("%d ", array[i]); } printf("n");}
其他八种排序算法的博客:
常见的9种内部排序(C语言实现)