排序算法

我们通常所说的排序算法是指内部排序算法，即数据记录在内存中进行排序。

排序算法大致分为两种：

一种是比较排序，时间复杂度O(nlogn) ~ O(n^2)，主要有：冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序等。

另一种是非比较排序，时间复杂度可以达到O(n)，主要有：计数排序，基数排序，桶排序等

算法的稳定性：冒泡，直接插入，归并

算法的稳定性是指若Ai=Aj,在排序之前的相对顺序是Ai在Aj之前，那么进行排序之后Ai还应该在Aj之前，即算法是稳定的

内部排序算法：

1.冒泡排序

核心思想：

1.比较相邻元素，如果前一个比后一个大，就把它们两个调换位置。

对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

2.针对所有的元素重复以上的步骤，除了最后一个。

3.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

简单优化冒泡排序：

2.选择排序

核心算法：选择排序也是一种简单直观的排序算法。（以从小到大的排序为例。）

1、初始时在序列中找到最小元素，放到序列的起始位置作为已排序序列；

2、然后，再从剩余未排序元素中继续寻找最小元素，放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

选择排序示意图

3.插入排序

插入算法用于满足一定条件时，可以提前结束，所以插入排序对于近似有序的序列来说，效率很高。插入算法通常与其他排序算法进行组合，从而减少运行时间

核心思想：1.将元素拿出来

                   2.将符合条件的元素后移

4.希尔排序

希尔排序是对插入排序的一个改进，首先引入分组的思想，从而将算法的时间复杂度降低到O（nlogn）

希尔排序示意图

5.快速排序

核心思想：

对于一个无序list，取index为0的元素作为中间数，然后执行分区函数，让比中间数小的点都在中间数左边，比中间数大的点都在中间数右边。此时得到了一个看似有序其实无序的list：

有序体现在此时list分成了两个区域，左边的都比中间数小，右边的都比中间数大。

无序体现在，而这两个区域，又都是无序的list

算法步骤：

1.基准点选取：快速排序首先需要先选择一个值作为基准点，一般选择是arr[0]，但是当数据出现近乎有序时，则比较复杂。因此基准点一般是随机选取一个值，在数学上会以很大的概率使算法的复杂度接近（O(nlogn)），极小的概率为O(n^2)

2.我们对这两个无序的list再次调用分区函数，此时会得到四个看似有序而又无序的list，接着调用分区函数，直到最终list长度为2时，再调用一次分区函数，那么一定是左边有序并且小于右边，因此此时所有的子列表都是有序的，那么此时一整个list也就是一个有序的list了。

左边的无序区域为nums[first:index-1]

右边的无序区域为nums[index+1,last]

代码如下：

6.归并排序：

最易于理解的白话：首先考虑下如何将将二个有序数列合并

1、这个非常简单，只要从比较二个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。

2、然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。

比如，13跟24678合并。

1跟2比较，1小于2，那么list.append(1)。

3跟2比较，2小于3，那么list.append(2)

3跟4比较，3小于4，那么list.append(3)

left数列已经为空，那么就把right的数列都append到list中。

核心思想：

那么归并排序呢，一样的道理。但是不一样的地方就是，一开始不是两个有序list，而是是一整个无序list，为了满足“两个，有序”的要求，我们分两步：

1、先把list分成left和right两个无序的部分

2、把这两个无序的部分，调用函数排成两个有序的部分

这里的两个无序的部分怎么排序成有序的部分呢。就是递归调用归并排序函数了。

3、对两个有序的部分，进行上面的merge操作即可。

其中递归的地方就是，上面的第二步中，上面的