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

真相只有一个 lv.1

发布时间：2023-09-20 06:00:26 283

相关标签：

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

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）算法可以先在草稿纸上验证一遍，然后开始编程

文章来源： https://blog.51cto.com/u_15888909/5880542

特别声明：以上内容（图片及文字）均为互联网收集或者用户上传发布，本站仅提供信息存储服务！如有侵权或有涉及法律问题请联系我们。