Question

假设关键字序列为｛9，3，5，1，2，6，4，7，8｝,用直接选择排序算法对关键字进行排序

代码写全，能够运行并有main测试函数
改一下，直接插入算法

Answer 1

直接选择排序的基本思想是：第一次从R［0］～R［n－1］中选取最小值，与R［0］交换，第二次从R［1］～R［n－1］中选取最小值，与R［1］交换，．．．．．，第n－1次从R［n－2］～R［n－1］中选取最小值，与R［n－2］交换，总共通过n－1次，得到一个按排序码从小到大排列的有序序列。因此：

初始状态｛9，3，5，1，2，6，4，7，8｝

第一次：9与1换，｛1，3，5，9，2，6，4，7，8｝

第二次：3与2换，｛1，2，5，9，3，6，4，7，8｝

第三次：5与3换，｛1，2，3，9，5，6，4，7，8｝

第四次：9与4换，｛1，2，3，4，5，6，9，7，8｝

第五次：9与7换，｛1，2，3，4，5，6，7，9，8｝

第六次：9与8换，｛1，2，3，4，5，6，7，8，9｝

排序完成，最终结果为六次，｛1，2，3，4，5，6，7，8，9｝。

扩展资料：

在直接选择排序中，共需要进行n-1次选择和交换，每次选择需要进行 n-i 次比较 (1<=i<=n-1),而每次交换最多需要3次移动，因此，总的比较次数C=(n*n - n)/2,总的移动次数 3(n-1)。

由此可知，直接选择排序的时间复杂度为 O(n2) ，所以当记录占用字节数较多时，通常比直接插入排序的执行速度快些。

由于在直接选择排序中存在着不相邻元素之间的互换，因此，直接选择排序是一种不稳定的排序方法。

Answer 2

/*

排序前:
9 3 5 1 2 6 4 7 8

排序后:
1 2 3 4 5 6 7 8 9

Press any key to continue
*/
#include <stdio.h>

void insert_sort(int *x, int n) { // 插入排序
int i, j, t;
for (i = 1; i < n; i++) {
t = *(x + i);
for (j = i - 1; j >= 0 && t < *(x + j); j--)
*(x + j + 1) = *(x + j);
*(x + j + 1) = t;
}
}

int main() {
int i,n;
int a[] = {9,3,5,1,2,6,4,7,8};
n = sizeof(a)/sizeof(a[0]);
printf("\n排序前:\n");
for(i = 0 ; i < n ; i++) printf("%5d",a[i]);
printf("\n");
insert_sort(a,n);
printf("\n排序后:\n");
for(i = 0 ; i < n ; i++) printf("%5d",a[i]);
printf("\n\n");
return 0;
}