稳定排序算法

A. 那些哪些排序算法是稳定的内在的

希尔排序、堆排序: 就地的不稳定排序
快速排序: 非就地的不稳定排序
选择排序: 不稳定排序
插入排序: 稳定排序

B. 下列排序算法中，（）是稳定的 a.插入，希尔 b.冒泡，快速 c.选择，堆排序 d.基数，归并

另外一个答案不靠谱啊
正确答案应该是D

对基数排序：
A least significant digit (LSD) radix sort is a fast stable sorting algorithm which can be used to sort keys in integer representation order.
对归并排序：
In computer science, merge sort (also commonly spelled mergesort) is an O(n log n) comparison-based sorting algorithm. Most implementations proce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output.

来源Wiki

C. 排序算法的稳定性有什么意义

当然是稳定的好。。

稳定意思是说原本键值一样的元素排序后相对位置不变

学习的时候，可能编的程序里面要排序的元素都是简单类型，实际上真正使用的时候，可能是对一个复杂类型的数组排序，而排序的键实际上只是这个元素中的一个属性，对于一个简单类型，数字值就是其全部意义，即使交换了也看不出什么不同。。。但是对于复杂的类型，交换的话可能就会使原本不应该交换的元素交换了。。

比如，一个“学生”数组，按照年龄排序，“学生”这个对象不仅含有“年龄”，还有其他很多属性，稳定的排序会保证比较时，如果两个学生年龄相同，一定不交换。

D. 排序算法稳定性的判断方法

对于不稳定的排序算法，只要举出一个实例，即可说明它的不稳定性；而对于稳定的排序算法，必须对算法进行分析从而得到稳定的特性。需要注意的是，排序算法是否为稳定的是由具体算法决定的，不稳定的算法在某种条件下可以变为稳定的算法，而稳定的算法在某种条件下也可以变为不稳定的算法。
例如，对于如下起泡排序算法，原本是稳定的排序算法，如果将记录交换的条件改成r[j]>=r[j+1]，则两个相等的记录就会交换位置，从而变成不稳定的算法。
void BubbleSort(int r[ ], int n){
exchange=n; //第一趟起泡排序的范围是r[1]到r[n]
while (exchange) //仅当上一趟排序有记录交换才进行本趟排序
{
bound=exchange; exchange=0；
for (j=1; j if (r[j]>r[j+1]) {
r[j]←→r[j+1]；
exchange=j； //记录每一次发生记录交换的位置
}
}
}
再如，快速排序原本是不稳定的排序方法，但若待排序记录中只有一组具有相同关键码的记录，而选择的轴值恰好是这组相同关键码中的一个，此时的快速排序就是稳定的。

E. 关于排序算法的稳定性

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

即可说明它的不稳定性；而对于稳定的排序算法，必须对算法进行分析从而得到稳定的特性。需要注意的是，排序算法是否为稳定的是由具体算法决定的，不稳定的算法在某种条件下可以变为稳定的算法，而稳定的算法在某种条件下也可以变为不稳定的算法。

(5)稳定排序算法扩展阅读：

基数排序按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的。

先按低优先级排序，再按高优 先级排序，最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以其是稳定的排序算法。

F. 稳定的排序算法有哪些

1.稳定的排序
冒泡排序（bubble sort） — O(n2)
鸡尾酒排序 (Cocktail sort, 双向的冒泡排序) — O(n2)
插入排序 （insertion sort）— O(n2)
桶排序 （bucket sort）— O(n); 需要 O(k) 额外 记忆体
计数排序 (counting sort) — O(n+k); 需要 O(n+k) 额外 记忆体
归并排序 （merge sort）— O(n log n); 需要 O(n) 额外记忆体
原地归并排序 — O(n2)
二叉树排序 （Binary tree sort） — O(n log n); 需要 O(n) 额外记忆体
鸽巢排序 (Pigeonhole sort) — O(n+k); 需要 O(k) 额外记忆体
基数排序 （radix sort）— O(n·k); 需要 O(n) 额外记忆体
Gnome sort — O(n2)
Library sort — O(n log n) with high probability, 需要 (1+ε)n 额外记忆体
2.不稳定的排序
选择排序 （selection sort）— O(n2)
希尔排序 （shell sort）— O(n log n) 如果使用最佳的现在版本
Comb sort — O(n log n)
堆排序 （heapsort）— O(n log n)
Smoothsort — O(n log n)
快速排序 （quicksort）— O(n log n) 期望时间, O(n2) 最坏情况; 对于大的、乱数串行一般相信是最快的已知排序
Introsort — O(n log n)
Patience sorting — O(n log n + k) 最外情况时间, 需要 额外的 O(n + k) 空间, 也需要找到最长的递增子序列（longest increasing subsequence）

G. 什么是稳定的排序方法

所谓稳定的排序算法就是你排序之后相同大小的数值没有发生变化，比如： 2 4 4 1 6 3 排序之后第二4的位置依然在一个4之后就是他们两个没有发生位置变化;称之为稳定；

H. 排序算法的稳定性

常用的几种排序算法中，稳定的排序有，冒泡排序，插入排序，归并排序，不稳定的排序有选择排序希尔排序，快速排序，堆排序，二叉排序树排序，等等。

I. 下列排序算法中,其中()是稳定的

A,堆不稳定
B,快速
C,选择不一定
选D