C语言选择排序法

Question

#include<stdio.h>
void main()
{
void sort(int array[],int n);
int a[10],i;
printf("enter the array\n");
for(i=0;i<10;i++)
scanf("%d",&a[i]);
sort(a,10);
printf("the sorted array:\n");
for(i=0;i<10;i++)
printf("%5d",a[i]);
printf("\n");
}
void sort(int array[],int n)
{
int i,j,k,t;
for(i=0;i<n-1;i++)
{
k=i;
for(j=i+1;j<n;j++)
if(array[j]<array[k])
k=j;
t=array[k];array[k]=array[i];array[i]=t;

}
}
代码如上，我的问题是，第一次执行时，用a【0】和a【1】比较，如果满足a【0】<a【1】则交换两者位置，第二次是比较a【0】和a【2】还是比较a【1】和a【2】。k在第一次比较完后因为倒数第二行代码不是已经变成K=1了吗，也就是以后再也不会让a【0】和后面的数字相比较了，但是如果这样就实现不了选择排序的功能啊，很纠结

Answer 1

这是选择排序。先用a[0]与a[1]比较，当a[0]<a[1]时并不交换，而用k记下来现在a[0]最小……这样一趟比较完后a[k]就是整个数组中最小的元素，把它与a[0]交换；第二趟，从a[1]开始重复前面的操作，那么最后a[1]就是剩下的n-1个元素中最小的……看a[0]、a[1]已经由小到大排好了，当做完n-1趟时不就把整个数组都排好了吗？注意：t=array[k];array[k]=array[i];array[i]=t;不是for(j=i+1;j<n;j++)的循环体，要等它循环完了后才执行一次。

追问

恍然大悟，原来交换值要内循环完一次才进行。内循环只是在记录最小的。谢谢

追答

追问的理解OK！

Answer 2

选择排序（Selection sort）是一种简单直观的排序算法。工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。 

以下是一个实现选择排序的例子：

#define SWAP(x, y, t)  ((t) = (x), (x) = (y), (y) = (t))
 //将list中的n个数据，通过选择排序算法排序。
void selete_sort(int list[], int n)
{
    int i, j, min, temp;
    for (i = 0; i < n - 1; i++){
        min = i;
        for (j = i + 1; j < n; j++)//找出最小元素的下标。
            if (list[j] < list[min])
                min = j;
        SWAP(list[i], list[min], temp);//交换最小元素到当前起始位置。
    }
}

Answer 3

选择排序与冒泡排序算法类似。
首先假定第i个元素最小(或最大--增排序)，并用k记录，内循环j从第i + 1个元素开始逐个与第k个元素比较，如果满足array[j] < array[k]，则执行k = j，k始终保存最小元素的下标，j循环结束后，再进行k与i比较，如果满足i == k，则原先假定正确，不需要交换，否则，假定是错的，则需要交换，这样就确保第i轮循环结束后，array[i]是最小的。
这么说显得枯燥，你可以取用只有几个元素的数组手工模拟排序，理解原理后就很容易记住选择排序的代码啦。

追问

我不懂的是如果第一次比较后a0小于a1，k＝j＝1，下一次内循环就只能用a1和a2比，a0再也不参与比较了，

其实就是内循环第一次之后是否还执行k＝i这步？

Answer 4

这是简单选择排序。但你图中的是未经优化的，因为移动次数和比较次数的时间复杂度都是O(n²)，而优化了的选择排序的移动次数的时间复杂度最优可以达到O(n)
如下图参考自《数据结构(C语言版)》——清华大学出版社

如图，如有疑问或不明白请追问哦！

Answer 5

每次从未排序的数字中选择最小的,与未排序的第一个交换,直到剩一个为止例子:(3 5 4 1 2 ) 选择最小为1,与3交换1 (5 4 3 2) 从剩余的选择最小为2 ,与5交换1 2 (4 3 5) 选择最小为3 与4交换1 2 3 (4 5)选择最小为4 ,它就是未排序第一个,不交换1 2 3 4 (5) 只剩一个了,结束