选择排序selection sort

LNH_Sniper

     选择排序是基本排序思想的一种，简单点说是：第 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. 
   
5. int *init_S_Sort(int size)
   
6. {
   
7.         return (int *)malloc(sizeof(int) * size);
   
8. }
   
9. 
   
10. void selection_sort(int *size, int length)
    
11. {
    
12.         int min, loop, loop_in, temp;
    
13.         for(loop = 0; loop < length; loop++)
    
14.         {
    
15.                 min = loop;
    
16.                 for(loop_in = loop + 1; loop_in < length; loop_in ++ )
    
17.                 {
    
18.                         if(size[min] > size[loop_in])
    
19.                                 min = loop_in;
    
20.                 }
    
21.                 temp = size[loop];
    
22.                 size[loop] = size[min];
    
23.                 size[min] = temp;
    
24.         }
    
25. }
    
26. 
    
27. int main(void)
    
28. {
    
29.         int len, len_buf, len_print, *arrary, *arrary_buf, *arrary_print;
    
30.         printf("The Length of Arrary:");
    
31.         scanf("%d",&len);
    
32.         len_print = len_buf = len;
    
33.         arrary = arrary_buf = arrary_print =init_S_Sort( len );
    
34.         printf("The Elemments Of Arrary:");
    
35.         while( len-- )
    
36.         {
    
37.                 scanf("%d",arrary++);
    
38.         }
    
39.         selection_sort(arrary_buf, len_buf);
    
40.         while( len_print --)
    
41.         {
    
42.                 printf("%d ",*arrary_print++);
    
43.         }
    
44.         return 0;
    
45. }
    

复制代码

在VC6.0下测试通过，代码实现了预期的功能，但细节处理的还是不够好，主函数过于繁琐，希望大家给出改正建议，多交流。           

仰望天上的光

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

回复 仰望天上的光 的帖子

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

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

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

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


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


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

仰望天上的光

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

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

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

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

仰望天上的光

我按照基于对象的方式也写个版本

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. 
    
16. //main
    
17. int main(void){
    
18.         int len;
    
19.         printf("The Length of Arrary:");
    
20.         scanf("%d",&len);
    
21.         Init(len);
    
22.         InPut();
    
23.         SelectionSort();
    
24.         OutPut();
    
25.         Destroy();
    
26.         return 0;
    
27. }
    
28. 
    
29. void Init(int size){
    
30.         pData = (int*)malloc(sizeof(int) * (length=size));
    
31. }
    
32. 
    
33. void Destroy(){
    
34.         free(pData);
    
35. }
    
36. 
    
37. void SelectionSort(){
    
38.         int min, loop, loop_in, temp;
    
39.         for(loop = 0,min =loop; loop < length; ++loop){
    
40.                 for(loop_in = loop + 1; loop_in < length; ++loop_in  ){
    
41.                         if(pData[min] > pData[loop_in]) min = loop_in;
    
42.                 }
    
43.                 swap(loop,min);
    
44.         }
    
45. }
    
46. 
    
47. void swap(int index_a, int index_b){
    
48.         int temp;
    
49.         temp = pData[index_a];
    
50.         pData[index_a] = pData[index_b];
    
51.         pData[index_b] = temp;
    
52. }
    
53. 
    
54. void OutPut(){
    
55.         int i;
    
56.         for(i=0;i<length;++i) printf("%d\n",pData[i]);
    
57. }
    
58. 
    
59. void InPut(){
    
60.         int i;
    
61.         for(i=0;i<length;++i) scanf("%d",pData+i);
    
62. }

复制代码

LNH_Sniper

回复 仰望天上的光 的帖子

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

仰望天上的光

回复 LNH_Sniper 的帖子

4#不是回复了？

□_谁_□_枫_□

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