选择排序法算法

发布网友发布时间：2024-09-27 06:49

共1个回答

热心网友时间：2024-09-29 07:11

简单选择排序算法详解：在排序过程中，简单选择排序的优点在于移动记录次数相对较少。在理想状态下，当待排序数组已按正序排列时，无需移动记录。而在最坏情况下，逆序排列需要最多移动n-1次记录。比较次数与数组初始状态无关，初始时，第一轮需要n-1次，第二轮n-2次，以此类推，总共n(n-1)/2次，因此其时间复杂度为O(n^2)。

选择排序是对冒泡排序的一种优化。以10个数存于数组a[0]至a[9]为例，冒泡排序通过从大到小逐个比较并交换，如a[9]始终存储最小值。但在选择排序中，首先记录一个最大值的位置k，然后与后面的元素比较，无需实际交换，只需更新k。这样，一轮下来，a[k]即为当前最大值，然后进入下一轮。与冒泡排序相比，虽然比较次数相同，但交换次数减少。

以下是两个示例的代码实现：

对于由大到小排序：

main() {
int a[10], i, j, t, k;
for (i = 0; i < 10; i++) scanf("%d", &a[i]);
for (i = 0; i < 9; i++) {
k = i;
for (j = i + 1; j < 10; j++) {
if (a[k] < a[j]) k = j;
}
if (k != i) {
t = a[i]; a[i] = a[k]; a[k] = t;
}
}
for (i = 0; i < 10; i++) printf("%4d", a[i]);
}

对于由小到大排序：

main() {
int a[10], i, j, t, k;
for (i = 0; i < 10; i++) scanf("%d", &a[i]);
for (i = 0; i < 9; i++) {
k = i;
for (j = i + 1; j < 10; j++) {
if (a[k] > a[j]) k = j;
}
if (k != i) {
t = a[i]; a[i] = a[k]; a[k] = t;
}
}
for (i = 9; i >= 0; i--) printf("%4d", a[i]);
}

以上是Java选择排序的简单实现，通过循环比较和交换元素，达到排序的目的。