大学计算机类数据结构原理排序期末考研必会【排序稳定性】

大学计算机类数据结构原理排序期末考研必会【排序稳定性】

首先要记住一个口诀：猫插鸡龟稳。（冒泡排序、直接插入排序、基数排序、归并排序是稳定的）
稳定性判断如下。
排序前6，5，4，8，4*，2，1
排序后1，2，4，4*，5，6，8----稳定的
排序后1，2，4*，4，5，6，8----不稳定的
直接插入排序
逐个比较，若是条件判断语句为A[i] 若是条件判断语句为A[i]<=A[i-1]则交换，则不稳定（出现几率几乎为0）；
希尔排序
初始：65，49，49*
d=2： 49*，49，65
d=1： 49*，49，65—不稳定
冒泡排序
逐个比较，所以稳定性原理与直接插入同。
快速排序
初始29，29*，2
划分，29与2交换得：2，29*，29----不稳定。
简单选择
初始：29，29*，2
第一趟：2，29*，29----不稳定
堆排序
29，29*，2
调成大根堆：29，29*，2
第一趟：29*，2，29
第二趟：2，29*，29----不稳定
归并排序
块内逐个比较，所以稳定性原理与直接插入同。
基数排序
队列先入先出原理，所以序列稳定。