C语言选择排序法

发布网友 发布时间：2022-03-30 03:33

我来回答

共16个回答

懂视网 时间：2022-03-30 07:55

以下用JAVA举一个例子，选择排序代码方法如下：

　　

　　算法描述：对于给定的一组记录，经过第一轮比较后得到最小的记录，然后将该记录与第一个记录的位置进行交换；接着对不包括第一个记录以外的其他记录进行第二轮比较，得到最小的记录并与第二个记录进行位置交换；重复该过程，直到进行比较的记录只有一个时为止。

　　

　　

热心网友 时间：2022-03-30 05:03

这是选择排序。先用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！

热心网友 时间：2022-03-30 06:21

选择排序（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);//交换最小元素到当前起始位置。
    }
}

热心网友 时间：2022-03-30 07:55

选择排序与冒泡排序算法类似。
首先假定第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这步？

热心网友 时间：2022-03-30 09:47

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

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

热心网友 时间：2022-03-30 11:55

每次从未排序的数字中选择最小的,与未排序的第一个交换,直到剩一个为止例子:(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) 只剩一个了,结束

热心网友 时间：2022-03-30 14:19

我来试试，看看对不对了楼主的胃口

这儿按升序

选择排序是每次从剩下的数中选出最小的数，放在前面

   for(i=0;i<n-1;i++) //这儿为什么是n-1的原因是，因为，每一个数要与后面剩下的数比较，最后只剩下一个数，所以不需要比较了
 for(j=i+1;j<n;j++) //这儿从i+1开始，就是为了和i后面的每一个数进行比较，选出最小的
 
 以第一层为例
 a[0]先与a[1]比较，如果，a[0] < a[1], 那么a[0]和a[2]比较，如果a[0] > a[1], 那么此时k != 0, 而是等于1了，然后a[k] 与 a[2]比较

热心网友 时间：2022-03-30 17:01

你好，很小的错误，看下注释的地方

public class Outfile {
public static void main(String[] args) {
int a[] = { 20, 29, 21, 45, 68, 15, 3, 5 };
for (int i = 0; i < a.length - 1; i++) {
int min = i;
for (int j = i + 1; j < a.length; j++) {
if (a[j] < a[min]) {
min = j;
}
}
if (min != i) {//这一段从上面内层的for拿了出来
int b = a[min];
a[min] = a[i];
a[i] = b;
}
}
for (int c = 0; c < a.length; c++) {
System.out.println(a[c]);
}
}
}

运行结果：
3
5
15
20
21
29
45
68

热心网友 时间：2022-03-30 19:59

　　选择排序的基本思想是:每一趟在n-i+1(i=1，2，…n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。基于此思想的算法主要有简单选择排序、树型选择排序和堆排序。
　　简单选择排序的基本思想:第1趟，在待排序记录r[1]~r[n]中选出最小的记录，将它与r[1]交换;第2趟，在待排序记录r[2]~r[n]中选出最小的记录，将它与r[2]交换;以此类推，第i趟在待排序记录r[i]~r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到全部排序完毕。

热心网友 时间：2022-03-30 23:13

这就是所谓的c语言中经典的两种排序方法，上面的叫做选择排序法，下面的叫做冒泡排序法，仔细分析下你应该可以看出他们的算法是不一样的，选择排序法是选择一个数为基准，和其它的数一个一个依次比较，然后调换位置。冒泡排序法是一个数和它相邻的数比较大小，然后调换位置。

热心网友 时间：2022-03-31 02:45

就像这样啊～输入10个数进行排序
main()

{int*p,i,a[10];

p=a;

for(i=0;i<10;i++)

scanf("%d",p++);

p=a

sort(p,10);

for(p=a,i=0;i<10;i++)

{printf("%d",*p);p++;}

}

sort(int x[ ],int n)

{int i,,j,k,t;

for(i=0;i<n-1;i++)

{k=i;

for(j=i+1;j<n;j++)

if(x[j]>x[k]) k=j;

if(k!=i)

{t=x[i];x[i]=x[k];x[k]=t;}

}

}

热心网友 时间：2022-03-31 06:33

这是我用C写的，包含5个常用排序算法，你可以参考参考。
http://wenku.baidu.com/view/9ba4bab84ae45c3b358cbb.html
如果看完还不明白，我可以帮你找下我学习时的视频发给你，视频里面讲得非常清楚。

热心网友 时间：2022-03-31 10:37

你看看,咱俩的有啥不同呢!
既然是选择排序,就先把最小的选择出来,然后拿出来再交换阿
public class SpiralNumber {

/**
* @param args
*/
public static void main(String[] args) {
int a[] = { 20, 29, 21, 45, 68, 15, 3, 5 };
for (int i = 0; i < a.length - 1; i++) {
int min = i;
for (int j = i + 1; j < a.length; j++) {
if (a[j] < a[min]) {
min = j;
}
}
//这里要移到内循环外!再进行交换
if (min != i) {
int b;
b = a[min];
a[min] = a[i];
a[i] = b;
}
}
for (int c = 0; c < a.length; c++) {
System.out.println(a[c]);
}
}
}

热心网友 时间：2022-03-31 14:59

我来试试，看看对不对了楼主的胃口
这儿按升序
选择排序是每次从剩下的数中选出最小的数，放在前面
for(i=0;i
a[1], 那么此时k != 0, 而是等于1了，然后a[k] 与 a[2]比较

热心网友 时间：2022-03-31 19:37

#include<stdio.h>
void sorted(int a[],int n){ //选择法排序
    int i,j,k,t;
    for(i=0;i<n-1;i++){
        k=i;
        for(j=i+1;j<n;j++){
            if(a[k]>a[j])k=j;} 
        if(k!=i){t=a[k];a[k]=a[i];a[i]=t;}}
}
int main(){
    int n,i,a[255];
    printf("请输入数据总量n(1-254)：");scanf("%d",&n);    
    printf("请输入%d个数：",n);
    for(i=0;i<n;i++)scanf("%d",&a[i]);
    printf("排序前的数组：");
    for(i=0;i<n;i++)printf("%d ",a[i]);printf("\n");      
    sorted(a,n);printf("排序后的数组：");
    for(i=0;i<n;i++)printf("%d ",a[i]);printf("\n");    
    return 0;
}

热心网友 时间：2022-04-01 00:31

每次选择没有排序元素中最小的排到前面
时间复杂度O(n^2)
空间复杂度O(n)