LNH_Sniper 发表于 2011-5-15 16:43:50

选择排序selection sort

   选择排序是基本排序思想的一种，简单点说是：第 i 次排序从序列的后n - i + 1个元素中选择一个最小的元素，与该
n - i + 1个元素的最前面那个元素进行位置交换。
    直观来说就是：每次的排序都是从未排好的序列中选择一个最小的元素，与未排序的元素的第一个进行交换。
    用图来解释下：
                                  3         6            4               2                   11               10      进行排序
    第一次
由于整个序列都是未排序的 所以，
            选出最小的元素      “2”         6               4            3                   11                   10
      第二次 在后续的为排序的元素
          中选出最小的元素      “2         3”            4             6                   11                   10      
同理进行若干次，直到最后结果
                              “2         3                4             6                   11                   10 ”

   对于选择排序来说，包含 n 个元素的数据序列需要 n - 1 次的排序   

这就是基本的原理啦。#include "stdio.h"
#include "malloc.h"
#include "stdlib.h"

int *init_S_Sort(int size)
{
        return (int *)malloc(sizeof(int) * size);
}

void selection_sort(int *size, int length)
{
        int min, loop, loop_in, temp;
        for(loop = 0; loop < length; loop++)
        {
                min = loop;
                for(loop_in = loop + 1; loop_in < length; loop_in ++ )
                {
                        if(size > size)
                                min = loop_in;
                }
                temp = size;
                size = size;
                size = temp;
        }
}

int main(void)
{
        int len, len_buf, len_print, *arrary, *arrary_buf, *arrary_print;
        printf("The Length of Arrary:");
        scanf("%d",&len);
        len_print = len_buf = len;
        arrary = arrary_buf = arrary_print =init_S_Sort( len );
        printf("The Elemments Of Arrary:");
        while( len-- )
        {
                scanf("%d",arrary++);
        }
        selection_sort(arrary_buf, len_buf);
        while( len_print --)
        {
                printf("%d ",*arrary_print++);
        }
        return 0;
}
在VC6.0下测试通过，代码实现了预期的功能，但细节处理的还是不够好，主函数过于繁琐，希望大家给出改正建议，多交流。         

仰望天上的光 发表于 2011-5-22 16:45:34

LZ，既然写了
int *init_S_Sort(int size);动态分配了空间，就应该相应有个
void destroy_S_Sort(int*);函数释放动态空间。
LZ的程序内存泄漏。

void selection_sort(int *size
这个参数名字叫size?是在误导使用者？
主函数中*arrary, *arrary_buf, *arrary_print;
这3个只要使用1个就可以了，因为值传递的关系，selection_sort函数不会改变实参的值

同理int len, len_buf, len_print这3个变量只要使用1个就可以了。

LNH_Sniper 发表于 2011-5-22 21:03:23

回复 仰望天上的光 的帖子

关于你提到的变量只需要一个，我解释下，我写的时候，因为用的是指针的操作来进行输入的，也就是输入后，指针不再指向头位置，所以定义了多个。

至于定义一个的操作，只需要将录入的形式更改为，数组下标的形式就好。

关于内存泄漏的问题，这是我没有想到的。我会再之后的程序中加以注意。

同时请教一个问题，我动态的开辟出一个空间，和定义一个足够大空间的数组。为什么前者会造成内存的泄露。


最后是关于参数的问题，谢谢提醒。我会注意的。


问题多交流，总之很感谢你提出的问题。谢谢

仰望天上的光 发表于 2011-5-22 22:48:41

关于你提到的变量只需要一个，我解释下，我写的时候，因为用的是指针的操作来进行输入的，也就是输入后，指针不再指向头位置，所以定义了多个。

呵呵，不好意思，看太快没注意到。

同时请教一个问题，我动态的开辟出一个空间，和定义一个足够大空间的数组。为什么前者会造成内存的泄露。

前者空间是在堆上分配的，malloc的空间数量可以是变量，也就是说具体分配多少空间在编译时刻编译器不知道，所以用这种方式内存管理（分配和释放）都要程序员自己做。
后者空间是在堆栈(局部数组)或静态数据区(全局数组)分配的，按照C90标准，数组在编译时期必须知道数组空间的大小，即十足大小不能是变量。这样做的坏出是不灵活，好处是内存管理(内存的分配和释放)不需要程序员来处理。

仰望天上的光 发表于 2011-5-22 23:08:42

我按照基于对象的方式也写个版本#include "stdio.h"
#include "malloc.h"
#include "stdlib.h"
//数据
static int* pData;
static int length;
//接口函数
void Init(int size);
void Destroy();
void InPut();
void OutPut();
void SelectionSort();
//私有函数
static void swap(int index_a, int index_b);

//main
int main(void){
        int len;
        printf("The Length of Arrary:");
        scanf("%d",&len);
        Init(len);
        InPut();
        SelectionSort();
        OutPut();
        Destroy();
        return 0;
}

void Init(int size){
        pData = (int*)malloc(sizeof(int) * (length=size));
}

void Destroy(){
        free(pData);
}

void SelectionSort(){
        int min, loop, loop_in, temp;
        for(loop = 0,min =loop; loop < length; ++loop){
                for(loop_in = loop + 1; loop_in < length; ++loop_in){
                        if(pData > pData) min = loop_in;
                }
                swap(loop,min);
        }
}

void swap(int index_a, int index_b){
        int temp;
        temp = pData;
        pData = pData;
        pData = temp;
}

void OutPut(){
        int i;
        for(i=0;i<length;++i) printf("%d\n",pData);
}

void InPut(){
        int i;
        for(i=0;i<length;++i) scanf("%d",pData+i);
}

LNH_Sniper 发表于 2011-5-23 21:38:57

回复 仰望天上的光 的帖子

回答一下我提出的问题 谢谢

仰望天上的光 发表于 2011-5-23 23:14:24

回复 LNH_Sniper 的帖子

4#不是回复了？

□_谁_□_枫_□ 发表于 2013-4-1 11:34:26

回答一下我提出的问题 谢谢
页: [1]
查看完整版本: 选择排序selection sort