目录

一 基本思想二 例子三 时间复杂度

一 基本思想

简单选择排序就是通过 n-i-1 次关键字间的比较， 从 n-i 个记录中选出关键字最小的记录， 并和第 i 个记录交换。

二 例子

private int[] array = new int[10] {4,5,6,3,2,1,7,8,9,0}; private void SelectSort() { int min = 0; for (int i = 0; i < array.Length; i++) { min = i; for (int j = i + 1; j < array.Length; j++) { if (array[min] > array[j]) { min = j; } } if (min != i) { int temp = array[i]; array[i] = array[min]; array[min] = temp; } } }

三 时间复杂度

简单选择排序的最大特点就是移动数据的次数相当少， 每轮比较最多移动一次数据。无论是最好还是最坏情况， 比较次数都是一样多。i = 0 时，需要比较 n - 1 次， i= 1时， 需要比较 n - 2 次 …, 也就是总的比较次数是 n(n-1) / 2。因此， 比较操作的时间复杂度是O(n²)。对于移动次数而言， 最好的情况需要移动0次， 最坏的情况需要移动 n-1次，因此移动操作的时间复杂度是O(n)。如果排序记录是随机的， 平均比较次数约等于(n²/2)， 平均移动次数约等于(n/2)。最终的排序时间是比较和移动次数的总和， 因此， 总的时间复杂度是 O(n²)。