1 排序算法的特点

基本排序，哪些是稳定的

排序算法稳定性，通俗地说，能包装排序前2个相等的数，在排序后 位置保持不变即可。

1.1 不稳定的经典排序

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

1.1.1 选择排序

选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，

在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n - 1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。

那么，在一趟选择，如果当前元素比一个元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。

举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，

那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。

1.1.2 快速排序

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，

然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

快速排序有两个方向，左边的i下标一直往右走，当a[i] <= a[center_index]，其中center_index是中枢元素的数组下标，一般取为数组第0个元素。

而右边的j下标一直往左走，当a[j] > a[center_index]。如果i和j都走不动了，i <= j，交换a[i]和a[j],重复上面的过程，直到i > j。

交换a[j]和a[center_index]，完成一趟快速排序。

在中枢元素和a[j]交换的时候，很有可能把前面的元素的稳定性打乱，比如序列为5 3 3 4 3 8 9 10 11，现在中枢元素5和3（第5个元素，下标从1开始计）交换就会把元素3的稳定性打乱，所以快速排序是一个不稳定的排序算法，不稳定发生在中枢元素和a[j] 交换的时刻。

快速排序由C. A. R. Hoare在1962年提出。

步骤：

1、判断参数条件，其实这是递归的出口；

2、以数组的第一个元素为哨兵元素，让其他元素和它比较大小；
   				(记住这时候第一个元素位置是口的，因为里面的值被作为哨兵元素保存起来了)

3、开始从数组尾部往前循环得到一个小于哨兵元素的  元素A ，把该  元素A  放到第一个元素位置（也就是哨兵元素位置上，因为哨兵元素位置是空的）；（这时候要记住 元素A  的位置是空的了）

4、开始从数组头部往后循环得到一个大于哨兵元素的   元素B ，把该  元素B  放在上一步中移出的  元素A  的位置上；

5、依次循环上面3、4步，直到最后一个元素为止，那么最后一个元素就存放哨兵元素了。

6、把小于哨兵元素的那一部分和大于哨兵元素的那一部分分别递归调用本函数，依次递归排序好所有元素；

时间复杂度：

 递归算法的时间复杂度公式：T[n] = aT[n/b] + f(n)  ；对于递归算法的时间复杂度这里就不展开来说了

最优:

快速排序最优 ：O( nlogn ), 最差：O( n^2 )

平均复杂度： O(nlogn)

快速排序最优的情况就是每一次取到的元素都刚好平分整个数组(很显然我上面的不是)；

   此时的时间复杂度公式则为：T[n] = 2T[n/2] + f(n)；T[n/2]

空间复杂度

     最优的情况下空间复杂度为：O(logn)  ；每一次都平分数组的情况		
    
    最差的情况下空间复杂度为：O( n )      ；退化为冒泡排序的情况

1.1.3 希尔排序(shell)

希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；

当元素基本有序了，步长很小， 插入排序对于有序的序列效率很高。

所以，希尔排序的时间复杂度会比O(n^2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，

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

1.1.4 堆排序

我们知道堆的结构是节点i的孩子为2 * i和2 * i + 1节点，大顶堆要求父节点大于等于其2个子节点，小顶堆要求父节点小于等于其2个子节点。

在一个长为n 的序列，堆排序的过程是从第n / 2开始和其子节点共3个值选择最大（大顶堆）或者最小（小顶堆），这3个元素之间的选择当然不会破坏稳定性。

但当为n / 2 - 1， n / 2 - 2， … 1这些个父节点选择元素时，就会破坏稳定性。

有可能第n / 2个父节点交换把后面一个元素交换过去了，而第n / 2 - 1个父节点把后面一个相同的元素没 有交换，那么这2个相同的元素之间的稳定性就被破坏了。

所以，堆排序不是稳定的排序算法。

时间复杂度

 堆排序的时间复杂度，主要在初始化堆过程和每次选取最大数后重新建堆的过程；
 
 初始化建堆过程时间：O(n)
 
 更改堆元素后重建堆时间：O(nlogn)

推算过程：

1、循环  n -1 次，每次都是从根节点往下循环查找，所以每一次时间是 logn，总时间：logn(n-1) = nlogn  - logn ；

空间

堆排序是就地排序，空间复杂度为常数：O(1)  

1.2 稳定的经典排序

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

1.2.1 冒泡排序：

无序中最大的（最小）的元素放到无序的最后面（或者说有序元素的最开始）

冒泡排序就是把小的元素往前调或者把大的元素往后调。

比较是相邻的两个元素比较，交换也发生在这两个元素之间。

所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的；如果两个相等的元素没有相邻，

那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。

步骤：

 1、外循环是遍历每个元素，每次都放置好一个元素；　　　
 2、内循环是比较相邻的两个元素，把大的元素交换到后面；
 3、等到第一步中循环好了以后也就说明全部元素排序好了；

时间复杂度:
最优

             最优的情况也就是开始就已经排序好序了，那么就可以不用交换元素了，则时间花销为：[ n(n-1) ] /  2；
			所以最优的情况时间复杂度为：O( n^2 )；

最差，逆序冒泡

 每一次排序都要交换两个元素，则时间花销为：[ 3n(n-1) ] /2；
 
     （其中比上面最优的情况所花的时间就是在于交换元素的三个步骤）；
 所以最差的情况下时间复杂度为：O( n^2 )；

空间复杂度

			O(N), 即O(1)	

1.2.2 插入排序：

插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。

当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。

比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。

如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。

1.2.3 归并排序：

快速排序的效率是非常高的，但是还有种排序算法的效率可以与之媲美，那就是归并排序

快速排序：是先把数组粗略的排序成两个子数组，然后递归再粗略分两个子数组，直到子数组里面只有一个元素，那么就自然排好序了，可以总结为先排序再递归；

归并排序：先不管其他，把数组分为两个子数组，一直递归把数组划分为两个子数组，直到数组里只有一个元素，这时候才开始排序.

让两个数组间排好序，依次按照递归的返回，把两个数组进行排好序，到最后就可以把整个数组排好序。

步骤：

 1、判断参数的有效性，也就是递归的出口；
 2、首先什么都不管，直接把数组平分成两个子数组；
 3、递归调用划分数组函数，最后划分到数组中只有一个元素，这也意味着数组是有序的了；
 4、然后调用排序函数，把两个有序的数组合并成一个有序的数组；
 5、排序函数的步骤，让两个数组的元素进行比较，把大的/小的元素存放到临时数组中，
 如果有一个数组的元素被取光了，那就直接把另一数组的元素放到临时数组中，
 然后把临时数组中的元素都复制到实际的数组中；

时间复杂度公式：

   T[n]  =  2T[n/2] + O(n)；
   T[n] = O( nlogn )

空间复杂度:

临时的数组和递归时压入栈的数据占用的空间：n + logn；所以空间复杂度为: O(n)

归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素（认为直接有序）或者2个序列（1次比较和交换）

然后把各个有序的段序列合并成一个有序的长序列，不断合并直到原序列全部排好序。

可以发现，在1个或2个元素时，1个元素不会交换，2个元素如果大小相等也没有人故意交换，这不会破坏稳定性。

那么，在短的有序序列合并的过程中，稳定是是否受到破坏？

没有，合并过程中我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结果序列的前面，这样就保证了稳定性。

所以，归并排序也是稳定的排序算法。

(6)基数排序：

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。

有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序，最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

基数排序基于分别排序，分别收集，所以其是稳定的排序算法。

1.3 稳定排序的优点：

从一个键开始排序，然后从另一个键排序，第一个键排序结果可以为第二个键排序所用

基数排序，先按低位排序，逐次按高位排序，低位相同的元素，

其顺序在高位也相同时，不会改变。 另外，如果排序算法稳定，对基于比较的排序算法而言，元素交换次数更少。

总结

	排序法       最差时间分析	平均时间复杂度	   稳定度	空间复杂度
	冒泡排序		O(n^2)	     O(n^2)	      稳定	O(1)
	快速排序		O(n^2)	      O(n*log2n)     不稳定  O(log2n)~O(n)
	选择排序		O(n^2)   	O(n^2)	不稳定	O(1)
	二叉树排序	      O(n^2)	   O(n*log2n)	不稳定	O(n)
	插入排序          O(n^2)	    O(n^2)	稳定	O(1)
	堆排序		O(n*log2n)	O(n*log2n)	不稳定	O(1)
	希尔排序	 	O		O	      不稳定	O(1)

示例1 快速排序主元

著名的快速排序算法里有一个经典的划分过程：

我们通常采用某种方法取一个元素作为主元（中值），通过交换，把比主元小的元素放到它的左边，比主元大的元素放到它的右边。

给定划分后的N个互不相同的正整数的排列，请问有多少个元素可能是划分前选取的主元？

例如给定的排列是

[1, 3, 2, 4, 5]

则：

1 的左边没有元素，右边的元素都比它大，所以它可能是主元；

尽管 3 的左边元素都比它小，但其右边的 2 比它小，所以它不能是主元；

尽管 2 的右边元素都比它大，但其左边的 3 比它大，所以它不能是主元；

类似原因，4 和 5 都可能是主元。

因此，有 3 个元素可能是主元。

输入格式:

一行数个整数的排列，由空格分隔

输出格式：

在第 1 行中输出有可能是主元的元素个数；在第 2 行中按递增顺序输出这些元素，其间以 1 个空格分隔，行首尾不得有多余空格。

输入样例：

1 3 2 4 5

输出样例：

3

1 4 5

示例2 找到第一个坏样本

现在有同一个产品的N个版本，编号为从1至N的整数；其中从某个版本之后所有版本均已损坏。

现给定一个函数isBadVersion，输入数字N可判断该版本是否损坏（若损坏将输出True）；

请找出第一个损坏的版本。

注：有时isBadVersion函数运行速度很慢，请注意优化查找方式

输入格式:

两行

第一行为整数，为产品号总数N

第二行为给定的判断函数，使用有效的Python表达式给出，可使用eval读取
输出格式：

一行数字，表示第一个损坏的版本
输入样例：

50

lambda n:n>=30

输出样例：

30

示例3 插入与归并

给出如下定义：

插入排序是迭代算法，逐一获得输入数据，逐步产生有序的输出序列。每步迭代中，算法从输入序列中取出一元素，将之插入有序序列中正确的位置。如此迭代直到全部元素有序。

归并排序进行如下迭代操作：首先将原始序列看成 N 个只包含 1 个元素的有序子序列，然后每次迭代归并两个相邻的有序子序列，直到最后只剩下 1 个有序的序列。

现给定原始序列和由某排序算法产生的中间序列，请你判断该算法究竟是哪种排序算法？

输入格式:

两行由空格分隔的数字，其对应长度相等的列表
其中第一行代表未排序的列表，第二行是排序算法过程中某一步的中间列表

输出格式：

首先在第 1 行中输出Insertion Sort表示插入排序、或Merge Sort表示归并排序；
然后在第 2 行中输出用该排序算法再迭代一轮的结果序列。
题目保证每组测试的结果是唯一的。数字间以空格分隔，且行首尾不得有多余空格

输入样例：

3 1 2 8 7 5 9 4 0 6
1 3 2 8 5 7 4 9 0 6

输出样例：

Merge Sort

1 2 3 8 4 5 7 9 0 6

输入样例2：

3 1 2 8 7 5 9 4 6 0

1 2 3 7 8 5 9 4 6 0

输出样例2：

Insertion Sort

1 2 3 5 7 8 9 4 6 0

示例4 列表出现最频繁的元素

给定一个列表与数字K，按出现次数倒序输出列表中前K个出现最频繁的元素；若少于K个元素则返回所有元素

输入格式:

输入为两行
第一行为给定列表，以合法的Python表达式给出
第二行为数字K

输出格式：

不多于K个数字，以空格分隔

输入样例：

[1,1,1,2,2,3] 
2

输出样例：

1 2 

示例5 字符串中所有重排子串

给定一个字符串s与待查找字符串p，请给出使得s[i:i+len§]是p的一个字母重排的所有下标i
保证字符串p非空

输入格式:

两行字符串，第一行为s，第二行为p

输出格式：

所有满足条件的下标从小到大排列，以空格分隔输出
若无对应下标，则输出"none"

输入样例：

cbaebabacd

abc

输出样例：

0 6 

示例 6 散列表

给定一个指定大小N的散列表，并输入一系列数字：若找到空槽，则插入该数字，并返回槽位置；若该数字在散列表中存在，则直接输出其位置。

注：使用下标增加的二次探测法解决散列冲突

注2：散列表实际大小应确定为不小于用户输入N的最小质数

输入格式:

两行

第一行为用户指定散列表大小N

第二行为一系列数字，以空格分隔

输出格式：

逐个输出对应数字在散列表中位置，以空格分隔
若该数字无法插入，则输出“-”

输入样例：

4
10 6 4 10 15

输出样例：

 0 1 4 0