选择排序

选择排序和冒泡排序差不多，只是冒泡排序在发现比它小的时候就交换，而选择排序是只有在确定了最小的数据之后，才会发生交换。选择排序的基本思想：第i趟简单选择排序是指通过n-i次关键字的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录进行交换。先临时记录其位置，只有在一趟循环完以后确定了最小的数据，才会发生交换。
即进行比较操作的时间复杂度为O(n2)

和冒泡排序交换相连数据不一样的是，选择排序只有在确定了最小的数据之后，才会发生交换。怎么交换呢？我们可以以下面一组数据作为测试：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;  
    }  
}

 

    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);  
} 

总结：
    1）其实测试的方法很多，打印就是比较不错的方式，不过只适合测试用例比较少的情形
    2）算法可以先在草稿纸上验证一遍，然后开始编程