一步一步写算法（之选择排序）

【 声明：版权所有，欢迎转载，请勿用于商业用途。  联系信箱：feixiaoxing @163.com】

    选择排序是和冒泡排序差不多的一种排序。和冒泡排序交换相连数据不一样的是，选择排序只有在确定了最小的数据之后，才会发生交换。怎么交换呢？我们可以以下面一组数据作为测试：

    2，1，5，4，9

    第一次排序：1，2，5，4，9

   第二次排序：1，2，5，4，9

    第三次排序：1，2，4，5，9

    第四次排序：1，2，4，5，9

    a）算法步骤

    那么从上面的排序步骤可以看到，选择排序应该是这样的：

    （1）每次排序的时候都需要寻找第n小的数据，并且和array[n-1]发生交换

    （2）等到n个数据都排序好，那么选择排序结束。

    b）排序代码

void select_sort(int array[], int length) 

{ 

    int inner, outer, index, value, median; 

    if(NULL == array || 0 == length) 

        return; 

    for(outer = 0; outer < length - 1; outer ++) 

    { 

        value = array[outer]; 

        index = outer; 

        for(inner = outer +1; inner < length; inner ++){ 

            if(array[inner] < value){ 

                value = array[inner]; 

                index = inner; 

            } 

        } 

        if(index == outer) 

            continue; 

        median = array[index]; 

        array[index] = array[outer]; 

        array[outer] = median; 

    } 

} 

void select_sort(int array[], int length)

{

       int inner, outer, index, value, median;

       if(NULL == array || 0 == length)

              return;

       for(outer = 0; outer < length - 1; outer ++)

       {

              value = array[outer];

              index = outer;

              for(inner = outer +1; inner < length; inner ++){

                     if(array[inner] < value){

                            value = array[inner];

                            index = inner;

                     }

              }

              if(index == outer)

                     continue;

              median = array[index];

              array[index] = array[outer];

              array[outer] = median;

       }

}

    c） 测试用例

void print(int array[], int length) 

{ 

    int index; 

    if(NULL == array || 0 == length) 

        return; 

    for(index = 0; index < length; index++) 

        printf("%d", array[index]); 

} 

void test() 

{ 

    int data[] = {2, 1, 5, 4, 9}; 

    int size = sizeof(data)/sizeof(int); 

    select_sort(data, size); 

    print(data, size); 

} 

void print(int array[], int length)

{

       int index;

       if(NULL == array || 0 == length)

              return;

       for(index = 0; index < length; index++)

              printf("%d", array[index]);

}

void test()

{

       int data[] = {2, 1, 5, 4, 9};

       int size = sizeof(data)/sizeof(int);

       select_sort(data, size);

       print(data, size);

}

总结：

    1）其实测试的方法很多，打印就是比较不错的方式，不过只适合测试用例比较少的情形

    2）算法可以先在草稿纸上验证一遍，然后开始编程