选择排序

Complexity: 算法复杂度

稳定性

选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第 n - 1 个元素，第 n 个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果当前元素比一个元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。比较拗口，举个例子，序列 5 8 5 2 9，我们知道第一遍选择第 1 个元素 5 会和 2 交换，那么原序列中 2 个 5 的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。

排序算法的稳定性意义在于其能够避免在大数据情况下过多的数据交换，并且能保证如果是在多入口排序情况下的较好的一致性体验，譬如在对 Album 进行排序时，可能先根据 Track Number 进行排序，然后根据 Album Name 进行排序，如果是稳定的算法，当我们以 Album Name 进行排序的时候，就能够保留 Track Number 的有序性。