基础排序算法总结_若排序序列的数量级为n

稳定性概念

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

选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法，

冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。

一、冒泡排序

冒泡排序的普通思路：

         比较相邻的两个元素，交换元素使得小元素在前、大元素在后。

         第一次排序将对n个元素进行n-1次比较，将最大的元素放到了数组的最后边；

         第二次排序将剩下的n-1个元素进行n-2次比较，将第二大的数放在数组的倒数第二个位置；

         依次进行该过程；

         第n-1趟则所有元素都是有序的，即完成了排序。

改进的冒泡排序：

        设置一个标志用来记录某次遍历数组中，有没有发生元素的交换；如果发生了元素的交换，说明数组还没有完全有序；如果没发生元素交换，说明整个数组已经有序，则排序结束。

       通过设置这个标志可以减少元素的比较次数。

二、插入排序

思路：

        每次将数组右边一个待排序的数据插入到数组左边已经排序的序列中，直到整个数组都是有序的。

        某次排序，将数组分为已排序序列A（数组左边部分）和未排序序列B（数组右边部分）；每次排序依次从B序列中取一个元素b，让其依次与A序列的元素比较（依次从A序列的最右一个元素向左开始比较），为数b在A序列中寻找一个合适的插入位置，将b插入A。

        由于每次都是将大于b的元素右移动，然后将b放在该位置，因此不会发生相同元素的交换，因此是稳定的。

三、希尔排序

思路：

        将数组分割为若干个子序列，每个序列中的元素都是由相隔某个增量的元素组成。

        对每个子序列分别进行插入排序；然后依次缩减增量，再次重复上述排序。

        直到增量为1后，进行依次排序，这时整个数组就是有序的，排序结束。

希尔排序是对相隔若干距离的数据进行直接插入排序的。

        一次插入排序是稳定的，不会改变相同元 素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。

四、选择排序

思路（假设非递减排序）：

        类似于插入排序，将序列分为了有序的和无序的子序列，不过这里不是依次选择一个未排序的元素插入已排序序列；而是找出未排序序列中最小的元素，将其与已经排序的序列紧邻的那个元素交换（初始已排序序列为0）。

例如5，8，5，2，9序列的第一趟排序是将第一个5与2交换，那么，两个5的次序就交换了，所以选择排序不稳定。

五、归并排序

思路：

         当一个数组的左部分有序、右部分也有序时，只要将这两部分合并即可完成排序。而如何使得左、右部分分别有序呢？递归使用归并排序即可。

        在归并的过程中，主要的操作是合并两个有序的序列，在合并中，如果两个元素相等，不会对它们交换，因此稳定。

六、快速排序

         上述链接的文章中给出了详细的思路和过程。

         快速排序被认为是所有同数量级(O(nlogn))排序方法中，平均性能最好的。

时间复杂度：

        但是，如果初始记录序列有序时，以左侧元素为枢纽的快速排序算法将退化为冒泡排序，其时间复杂度为O(n ^ 2)；在初始序列有序或逆序情况下，每次排序需要n * n次比较，因此算法复杂度为O(n ^ 2)。

空间复杂度：

       快速排序需要一个栈空间来实现递归（即使是非递归算法，它也需要一个辅助栈来保存下次带排序数组的下标范围）。若每一趟排序都将记录序列均匀分割为长度接近相等的两个子序列，则平均情况下栈的最大深度为logn + 1（包括最外层参数进栈），但是若每趟排序后，枢纽位置均偏向子序列的一端（初始序列有序或逆序），则为最坏情况，栈的最大深度为n。

七、堆排序

         如果要按照非递减顺序排序，那么要使用大根堆；按照非递增顺序排序，要使用小根堆。

假设按照非递减顺序排列，那么排序的思路是：

         首先建立一个大根堆；

         删除大根堆的根元素（说是删除，其实是利用了堆最后的那个空间来存储该元素，即将根元素与堆尾部元素交换，这样当堆删除完后，那么存储空间就是有序的了）；

         每次交换的根元素和尾元素后要进行下滤操作，使得满足大根堆。

         排序过程就是删除根元素并上滤的过程，上滤中可能会让相等元素位置改变，因此不稳定。

八、线性时间排序

以上将的都是基于比较的排序，时间复杂度上界为O(n ^ 2)， 下界为O(nlogn)。下面介绍几种线性排序：

1、基数排序

        基数排序是按照低位先排序，然后收集；再按照次低位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优 先级排序，最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，它在每一位排序中依赖于一个稳定的排序算法，所以基数排序是稳定的排序算法。

        给定n个d位数，其中每个数位有k个可能的取值。那么需要d轮排序，所以基数排序耗时为d(n + k)，而d为常数，所以基数排序复杂度为O(n + k)。

2、计数排序

假设n个输入元素中每个都是在0到k区间的整数(k是某个整数)。当k = O(n)时，排序的运行时间为O(n)。

3、桶排序

        假设输入数据服从均匀分布，平均情况下其时间代价为O(n)。和计数排序类似，计数排序假设数据都是一个小区间内的整数，桶排序则假定输入由一个随机过程产生，该过程将元素均匀、独立地分布在[0,1)区间内。

        桶排序将[0,1)区间划分为n个相同大小的子区间，称为桶；然后，将n个数分别放入到各个桶中，因为输入数据是均匀分布的，所以不会出现很多数落在一个桶内的情况。为了得到输出结果，先对每个桶中数进行排序（例如，利用插入排序），然后遍历每个桶，按照次序把各个桶内的元素列出来即可。