选择排序算法稳定性

选择排序算法稳定性

选择排序是一种简单直观的排序算法，它的核心思想是从未排序的数据中选择最小的一个元素，放到已排序的末尾。通过不断重复这个过程，最终实现整个序列的排序。虽然选择排序的时间复杂度较高，但是它是一种不占用额外空间的原址排序算法。

在选择排序中，相同元素之间的顺序会发生改变，因此称其为不稳定的排序算法。下面我们通过代码示例来进行分析。

首先看一下选择排序的核心代码：

void selection_sort(int arr[], int len) {
  int i, j, min_idx;
  for (i = 0; i < len-1; i++) {
    min_idx = i;
    for (j = i+1; j < len; j++) {
      if (arr[j] < arr[min_idx]) {
        min_idx = j;
      }
    }
    swap(&arr[min_idx], &arr[i]);
  }
}

这段代码使用了嵌套循环来实现选择排序。外层循环控制当前最小值的索引，内层循环从当前最小值的下一个元素开始，循环查找最小值的索引。当内层循环结束时，我们将当前最小值与未排序部分的起始元素进行交换。

那么，为什么选择排序不稳定呢？其实，选择排序不稳定的原因就是在查找最小值的过程中，我们并没有保证相同元素之间的顺序。下面我们通过示例来验证这个结论：

void selection_sort_stable(int arr[], int len) {
  int i, j, min_idx;
  for (i = 0; i < len-1; i++) {
    min_idx = i;
    for (j = i+1; j < len; j++) {
      if (arr[j] < arr[min_idx] || (arr[j] == arr[min_idx] && j < min_idx)) {
        min_idx = j;
      }
    }
    swap(&arr[min_idx], &arr[i]);
  }
}

这段代码是一个选择排序的稳定版本。在查找最小值时，我们增加了一个额外的条件判断：如果有相同元素，我们选择索引