C语言基本功-选择排序法

再温习一下第二种排序法，也是一种基本的排序法，选择排序法：

算法原理（来源于网络，息懒得码字了，原理这东西理解就好^_^）:

顾名思意,就是直接从待排序数组里选择一个最小(或最大)的数字,每次都拿一个最小数字出来,

顺序放入新数组,直到全部拿完

再简单点,对着一群数组说,你们谁最小出列,站到最后边

然后继续对剩余的无序数组说,你们谁最小出列,站到最后边

再继续刚才的操作,一直到最后一个,继续站到最后边,现在数组有序了,从小到大

举例

先说看每步的状态变化,后边介绍细节,现有无序数组[6 2 4 1 5 9]

第一趟找到最小数1,放到最前边(与首位数字交换)

交换前:| 6 | 2 | 4 | 1 | 5 | 9 |

交换后:| 1 | 2 | 4 | 6 | 5 | 9 |

第二趟找到余下数字[2 4 6 5 9]里的最小数2,与当前数组的首位数字进行交换,实际没有交换,本来就在首位

交换前:| 1 | 2 | 4 | 6 | 5 | 9 |

交换后:| 1 | 2 | 4 | 6 | 5 | 9 |

第三趟继续找到剩余[4 6 5 9]数字里的最小数4,实际没有交换,4待首位置无须交换

第四趟从剩余的[6 5 9]里找到最小数5,与首位数字6交换位置

交换前:| 1 | 2 | 4 | 6 | 5 | 9 |

交换后:| 1 | 2 | 4 | 5 | 6 | 9 |

第五趟从剩余的[6 9]里找到最小数6,发现它待在正确的位置,没有交换

排序完毕输出正确结果[1 2 4 5 6 9]

第一趟找到最小数1的细节

当前数组是| 6 | 2 | 4 | 1 | 5 | 9 |

先把6取出来,让它扮演最小数

当前最小数6与其它数一一进行比较,发现更小数就交换角色

当前最小数6与2比较,发现更小数,交换角色,此时最小数是2,接下来2与剩余数字比较

当前最小数2与4比较,不动

当前最小数2与1比较,发现更小数,交换角色,此时最小数是1,接下来1与剩余数字比较

当前最小数1与5比较,不动

当前最小数1与9比较,不动,到达末尾

当前最小数1与当前首位数字进行位置交换,如下所示

交换前:| 6 | 2 | 4 | 1 | 5 | 9 |

交换后:| 1 | 2 | 4 | 6 | 5 | 9 |

完成一趟排序,其余步骤类似

下面是用C完成的实验，编译环境：Dev C++ 4.9.9.2, 编程语言：C

/*
  基本思想：每一趟在n-i+1（i=1，2，…n-1）个记录中选取关键字最小的记录作为有序序列中第i个记录。
 基于此思想的算法主要有简单选择排序、树型选择排序和堆排序
 
 就是直接从待排序数组里选择一个最小(或最大)的数字,每次都拿一个最小数字出来,
*/
#include <stdio.h>
#include <stdlib.h>
      
int test_tab[] = {0,4,9,5,7,1,3,9,6,4,5,6,7,7,8,8,1,0,3,2};

// 选择排序法
void Selection_Sort(int *dat, int len)
{
     int i=0,j=0,temp=0;
     int index = 0;
     int n = 0;
    
     for(i=0;i<len;i++)
     {            
       index = i;
       for(j=0;j<len;j++)
       {
         if(dat[index]<dat[j])
           index = j;
          
         if(index != i)
         {
           temp   = dat[i];
           dat[i] = dat[index];
           dat[index] = temp;        
         }
         n++;  
       }
                        
     }
    
     printf("总的循环次数是： %d \r\n",n);
}

// 主程序入口
int main(int argc, char *argv[])
{
  int i = 0;
  int len = sizeof(test_tab)/sizeof(test_tab[0]);
 
  Selection_Sort(test_tab,sizeof(test_tab)/sizeof(test_tab[0]));
  for(i=0;i<len;i++)
    printf("%d ",test_tab[i]);
   
  system("PAUSE"); 
  return 0;
}

/////////////////////////////////////////////////////////////////////////////////////////////////

这个算法理解起来也不是太难，主要是要懂原理

最后，吼一下俺的口号：

每天进步一点点，开心多一点^_^