本文共 960 字，大约阅读时间需要 3 分钟。

排序算法稳定性的概念：

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

基数排序：

我们对329,457,，657,839,436,720进行排序：

首先对个位数进行排序之后的结果是：

720，355，436，457，657，329，839

在第一步基础上继续进行排序：

720，329，436，839，355，457，657

在第二步基础上继续进行排序：

329，355，436，457，657，720，839

不是说第二步重新对原始数列进行排序，所以第一步的排序等于白排了，而是第二步排序在第一步排好的基础上进行排序

这样可以保证如果是十位相同的情况下，那么按照个位的顺序进行排序。

这是时间复杂度最小的一种排序方法。

同时，对于两个相同的数字，不会在这个过程中改变顺序，所以这也是一种稳定的排序。

时间复杂度是O(n)

选择排序：

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

插入排序：

插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。

时间复杂度也是O(N2)

转载地址：http://qgfab.baihongyu.com/