鱼C论坛

 找回密码
 立即注册
查看: 3786|回复: 7

[技术交流] 选择排序selection sort

[复制链接]
发表于 2011-5-15 16:43:50 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
     选择排序是基本排序思想的一种,简单点说是:第 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 次的排序   

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

  4. int *init_S_Sort(int size)
  5. {
  6.         return (int *)malloc(sizeof(int) * size);
  7. }

  8. void selection_sort(int *size, int length)
  9. {
  10.         int min, loop, loop_in, temp;
  11.         for(loop = 0; loop < length; loop++)
  12.         {
  13.                 min = loop;
  14.                 for(loop_in = loop + 1; loop_in < length; loop_in ++ )
  15.                 {
  16.                         if(size[min] > size[loop_in])
  17.                                 min = loop_in;
  18.                 }
  19.                 temp = size[loop];
  20.                 size[loop] = size[min];
  21.                 size[min] = temp;
  22.         }
  23. }

  24. int main(void)
  25. {
  26.         int len, len_buf, len_print, *arrary, *arrary_buf, *arrary_print;
  27.         printf("The Length of Arrary:");
  28.         scanf("%d",&len);
  29.         len_print = len_buf = len;
  30.         arrary = arrary_buf = arrary_print =init_S_Sort( len );
  31.         printf("The Elemments Of Arrary:");
  32.         while( len-- )
  33.         {
  34.                 scanf("%d",arrary++);
  35.         }
  36.         selection_sort(arrary_buf, len_buf);
  37.         while( len_print --)
  38.         {
  39.                 printf("%d ",*arrary_print++);
  40.         }
  41.         return 0;
  42. }
复制代码
在VC6.0下测试通过,代码实现了预期的功能,但细节处理的还是不够好,主函数过于繁琐,希望大家给出改正建议,多交流。           
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 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个就可以了。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
 楼主| 发表于 2011-5-22 21:03:23 | 显示全部楼层
回复 仰望天上的光 的帖子

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

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

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

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


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


问题多交流,总之很感谢你提出的问题。谢谢
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-5-22 22:48:41 | 显示全部楼层
关于你提到的变量只需要一个,我解释下,我写的时候,因为用的是指针的操作来进行输入的,也就是输入后,指针不再指向头位置,所以定义了多个。

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

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

前者空间是在堆上分配的,malloc的空间数量可以是变量,也就是说具体分配多少空间在编译时刻编译器不知道,所以用这种方式内存管理(分配和释放)都要程序员自己做。
后者空间是在堆栈(局部数组)或静态数据区(全局数组)分配的,按照C90标准,数组在编译时期必须知道数组空间的大小,即十足大小不能是变量。这样做的坏出是不灵活,好处是内存管理(内存的分配和释放)不需要程序员来处理。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-5-22 23:08:42 | 显示全部楼层
我按照基于对象的方式也写个版本
  1. #include "stdio.h"
  2. #include "malloc.h"
  3. #include "stdlib.h"
  4. //数据
  5. static int* pData;
  6. static int length;
  7. //接口函数
  8. void Init(int size);
  9. void Destroy();
  10. void InPut();
  11. void OutPut();
  12. void SelectionSort();
  13. //私有函数
  14. static void swap(int index_a, int index_b);

  15. //main
  16. int main(void){
  17.         int len;
  18.         printf("The Length of Arrary:");
  19.         scanf("%d",&len);
  20.         Init(len);
  21.         InPut();
  22.         SelectionSort();
  23.         OutPut();
  24.         Destroy();
  25.         return 0;
  26. }

  27. void Init(int size){
  28.         pData = (int*)malloc(sizeof(int) * (length=size));
  29. }

  30. void Destroy(){
  31.         free(pData);
  32. }

  33. void SelectionSort(){
  34.         int min, loop, loop_in, temp;
  35.         for(loop = 0,min =loop; loop < length; ++loop){
  36.                 for(loop_in = loop + 1; loop_in < length; ++loop_in  ){
  37.                         if(pData[min] > pData[loop_in]) min = loop_in;
  38.                 }
  39.                 swap(loop,min);
  40.         }
  41. }

  42. void swap(int index_a, int index_b){
  43.         int temp;
  44.         temp = pData[index_a];
  45.         pData[index_a] = pData[index_b];
  46.         pData[index_b] = temp;
  47. }

  48. void OutPut(){
  49.         int i;
  50.         for(i=0;i<length;++i) printf("%d\n",pData[i]);
  51. }

  52. void InPut(){
  53.         int i;
  54.         for(i=0;i<length;++i) scanf("%d",pData+i);
  55. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
 楼主| 发表于 2011-5-23 21:38:57 | 显示全部楼层
回复 仰望天上的光 的帖子

回答一下我提出的问题 谢谢
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-5-23 23:14:24 | 显示全部楼层
回复 LNH_Sniper 的帖子

4#不是回复了?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2013-4-1 11:34:26 | 显示全部楼层
回答一下我提出的问题 谢谢
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 20:43

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表