算法---5.选择排序

1. 选择排序
由小到大排序的过程
第一趟相当于找到最小值并放在首位   
第二趟相当于找到次小值，并放在第2的位置上    
以此类推
b. 与冒泡排序的区别
在找最小数的同时冒泡排序会交换数据，而选技排序不会交换只是查找最小数，找到了才交换
下面是冒泡的理解:
 第1个数与剩下的n-1个数比较，若有比第1个数小的就交换，让第1个数始终存本趟最小的数
  第2个数与剩下的n-2个数比较，若有比第2个数小的就交换，让第2个数始终存本趟最小的数
1.2 代码

#include <stdio.h>
#include <stdlib.h>
#define dbmsg(fmt, args ...) printf("%s:%s[%d]: "fmt"\n", __FILE__,__FUNCTION__, __LINE__,##args)
#define SWAP(x,y) (x=(x)+(y),y=(x)-(y),x=(x)-(y))

int dum_array(int* arr, int len)
{
    int i;
    for(i=0; i<len; i++)
    {
        //printf("%d=%d ", i, arr[i]);
        printf("%d  ", arr[i]);
    }
    printf("\n");
    return 0;
}

int select_min_index(int*arr, int start, int end)
{
   int i,j;
   int index = start;
   dbmsg("s=%d,e=%d", start, end);
   for(i=start+1; i<end; i++)
       if(arr[i] < arr[index])
           index = i;
   return index;
}

int select_sort(int* arr, int len)
{
    int i,j;
    int key;
    if(len <= 0)
        return 0;
    for(i=0; i<len; i++)
    {
        j = select_min_index(arr, i, len);  //在剩下的数据中选出最小的
        dbmsg("j=%d", j);                   //与剩下的数据中的第一个相比较，不同则交换
        if(i != j)
            SWAP(arr[i], arr[j]);
        dum_array(arr, len);
    }
    return 0;
}
int main ( int argc, char *argv[] )
{
    //int arr[] = {49, 38, 65, 97, 76, 13, 27, 49};
    int arr[] = {49, 38, 65, 97, 76, 13, 27, 49, 55, 4};
    int len = sizeof(arr)/sizeof(int);
    dbmsg("len=%d", len);
    dbmsg("before sort:");
    dum_array(arr, len);
    select_sort(arr, len);
    dbmsg("after sort:");
    dum_array(arr, len);
    return EXIT_SUCCESS;
}

1.3 运行结果

select.c:main[51]: before sort:
49  38  65  97  76  13  27  49  55  4  
select.c:select_min_index[22]: s=0,e=10
select.c:select_sort[38]: j=9
4  38  65  97  76  13  27  49  55  49  
select.c:select_min_index[22]: s=1,e=10
select.c:select_sort[38]: j=5
4  13  65  97  76  38  27  49  55  49  
select.c:select_min_index[22]: s=2,e=10
select.c:select_sort[38]: j=6
4  13  27  97  76  38  65  49  55  49  
select.c:select_min_index[22]: s=3,e=10
select.c:select_sort[38]: j=5
4  13  27  38  76  97  65  49  55  49  
select.c:select_min_index[22]: s=4,e=10
select.c:select_sort[38]: j=7
4  13  27  38  49  97  65  76  55  49  
select.c:select_min_index[22]: s=5,e=10
select.c:select_sort[38]: j=9
4  13  27  38  49  49  65  76  55  97  
select.c:select_min_index[22]: s=6,e=10
select.c:select_sort[38]: j=8
4  13  27  38  49  49  55  76  65  97  
select.c:select_min_index[22]: s=7,e=10
select.c:select_sort[38]: j=8
4  13  27  38  49  49  55  65  76  97  
select.c:select_min_index[22]: s=8,e=10
select.c:select_sort[38]: j=8
4  13  27  38  49  49  55  65  76  97  
select.c:select_min_index[22]: s=9,e=10
select.c:select_sort[38]: j=9
4  13  27  38  49  49  55  65  76  97  
select.c:main[54]: after sort:
4  13  27  38  49  49  55  65  76  97

1.4 性能
O(n2)
1.5 代码打包
select.rar    (下载后改名为select.tar.gz)