10
注：本帖均已升序排列为例@AC君
由于作者忙于学业以及一些事，堆排与接下来的三个排序方法将在暑假更新（也可能提前）
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
第一种：冒泡排序
冒泡排序的基本思想：冒泡排序就是通过多趟“冒泡”逐步将最小值移动到数组的前端，之后将已排好的数字移出排序范围，重复操作。最后逐步把序列排好
这里我们用如下图表式（这里以无序序列4,3,1,24,3,1,24,3,1,2为例，有点抽象，还请见谅）：
我们先比较最后两个数：
很明显，1比2小，所以不做任何交换。
接下来，我们比较3和1：
1比3小，所以我们让更小的1与3交换，使1到3的左边：
然后在比较一下1和4,1比四小，所以我们把更小的1挪到4的左边：
这样第一轮交换就结束了。我们把排好的数字移出范围，接着比较2和3……：
重复上述操作，最后冒泡排序完成：
代码实现：
冒泡排序的时间复杂度为O(N2)O(N^2)O(N2)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
第二种，选择排序，这里也以无序序列4,3,1,24,3,1,24,3,1,2为例：
选择排序的基本思想：通过遍历找到序列中的最小值，然后将最小值移动到序列最前端，把排好的数移出范围，重复上述操作，排序完成。
同样以图画为例：
首先遍历序列：
找到最小值1：
将最小值1移到最前边：
将排好的数移出排序范围，并重复上述操作：
……↓
代码：
选择排序时间复杂度为O(N2)O(N^2)O(N2)，与冒泡排序相同。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
第三种，插入排序，实例同上：
插入排序思路：这里把插入数据与原有数据相比较，大于往右移，找到合适的位置；小于则向左移，找到合适的位置，之后插入进去。
首先插入数字“2”并标记为已排序：
接下来插入数字“1”并找到合适的位置。1比2小，放到2的左边一位：
继续插入……
排序完成。
代码：
时间复杂度与上述相同，均为O(N2)O(N^2)O(N2)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
第四种，SORT排序：
SORT有三个参数分别为排序起始位置，排序结束的位置以及比较函数（可省略，省略后默认升序）。比较函数(CMP)是BOOL 类型。在定义参数是是这样定义的BOOL CMP(M A,M B)，这里M指要排序的类型，如果是结构体就写BOOL CMP(结构体名 A,结构体名 B)。升序就写RETURN A<B，降序就写RETURN A>B。
代码：
降序：
升序（这里比较函数可以省略）：
时间复杂度为O(NLOGN)O(N\LOG{N})O(NLOGN)
SORT排序主要是快速排序，但因为快排的最坏复杂度是O(N2)O(N^2)O(N2)，所以为了维持O(NLOGN)O(N\LOG{N})O(NLOGN)的复杂度，加入了堆排序（O(NLOGN)O(N\LOG{N})O(NLOGN)）和插入排序（O(N2)O(N^2)O(N2)）。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
第六种，桶排序：
桶排序的主要思想：我们可以设计出有限的桶，之后将所需排序的值放入桶中。桶内元素大于0是就输出桶的编号。里面有几就输出几次。
下面我们还是用图来描述：
这里我们用1,2,3,4,41,2,3,4,41,2,3,4,4，序列中最大值为4，我们就设立从1到4个桶， 读取第一个元素放入桶中（一号桶元素加一）：
读取第二，三个元素（过程跳过），接下来读取两个“4”，由于有两个相同元素，所以我们在4号桶里放两个：
接下来进行输出，先输出前三个数：
最后，4号桶里元素为2，我们就输出两个四，排序完成：
代码实现（这里稍微优化了一下）：
时间复杂度：O(MAX(SZ1,SZ2…SZA))O(\MAX(SZ_1,SZ_2…SZ_A))O(MAX(SZ1 ,SZ2 …SZA ))，由于桶排的时间复杂度（本代码）是由序列中最大的元素决定的，所以如果序列中元素较大，就不要使用桶排序。优化前是O(N)O(N)O(N)其中N是题目中所给的SZISZ_ISZI 的最大值。像这样：SZI<=1000SZ_I<=1000SZI <=1000。且桶排序不能处理序列中元素为负数的情况
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
第六种（重点），归并排序：
归并排序的思想：归并排序就是把一个无序序列进行分割，之后进行合并的排序算法。听着是不是很简单？实际一点也不简单。这里还是用序列4,3,1,24,3,1,24,3,1,2来模拟。
首先我们把数据往下分（这里以二分为例），不需要管什么顺序：
再分：
现在我们已经分完了，接下来就是合并了。首先我们合并4与3，因为3比4小，所以先上3，右半边（既3所在处）没有数了，我们就把左半边（4所在处）的所有数拿上来：
接下来合并1和2，1比2小，先上1，左半边没有数了，把右半边所有数拿上去：
在合并序列3,4与序列1,2。1比3小，先拿1，并将比较箭头向后移：
比较3和2,2比三小，上二，并将箭头向后移：
此时右半边已经没有数了，我们就直接上左半边，排序完成：
代码实现：
首先对序列进行分割，每次分为左半边（L，MID）和右半边（MID+1，R），并进行递归，直到不能在分为止。既L==R：
接下来合并。一次比较连边的数，小的放入临时数组（TEMP）中，并将下标右移一位。当其中一个半边全部拿完时，把另一边的所有数上移：
最后将分割与合并合并，排序完直接输出：
时间复杂度：O(NLOGN)O(N\LOG{N})O(NLOGN)且稳定。归并排序适合处理数据量较大的时候（例如N==109N==10^9N==109）。同时，归并把一个大问题分为了许多个子问题，这种思想也叫分治\COLOR{RED}分治分治。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
第七种，快速排序：
快排的思想。与归并一样，都运用了分治\COLOR{RED}分治分治的思想。快排主要是把序列分成[比基准值小的部分][基准值][比基准值大的部分]\COLOR{GOLD}[比基准值小的部分]{ }[基准值]{ }[比基准值大的部分][比基准值小的部分][基准值][比基准值大的部分]（基准值也可叫枢轴）。之后将左右两个部分继续执行同样的操作。直到排序完成。接下来用序列1,3,12,5,21,3,12,5,21,3,12,5,2来演示快排的过程。
首先选择基准值，这里随机选择了5。
然后将数分别插入，1比5小，把1放在5的左边：
接下来比较2和5,2比5小，放到5的左边。注意，这里不需要看顺序，否则就变成了插入排序。
插入数字12，比5大，放在5的右边
插入数字3，比5小，放在5的左边。第一轮快排完成：
接下来我们把基准值5先提出来，这样就分成了左右两个部分。我们先来排左边：这里以2为基准值，3比2小，放到2的右边；1比2小，放到2的右边：
这样左边就排好了。接下来排右边，右边只有1个数，所以无序排序。插入基准值5，排序结束：
代码实现（忘了从哪盗的模板了）：
重复执行把大于基准值的数一道右边，把小于基准值的数移到左边，并用递归继续执行：
整体代码：
时间复杂度：O(NLOGN)O(N\LOG{N})O(NLOGN)，但如果每一次都选择了最小的基准值，那么快排就退化成了选择排序或不引入随机化的话，时间复杂度就可能会指数级升高，最坏复杂度为O(N2)O(N^2)O(N2)。同时，在数据规模较大时，最好食用归并，快排容易崩。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
第八种，堆排序：
整体思路：堆排序是利用了堆的特点，即为取出最小元素的时间复杂度为O(1)O(1)O(1)。
首先还是以图片为例。这里以序列123651210312 36 5 12 10 31236512103为例（之前图片太丑了，稍稍优化了一下）：
按升序构建一个堆（之后就用圆圈代替了）：
取出堆的第一个元素，并重新构建堆（这里不多讲了哈）：
继续取出元素并重构堆……排序完成：
代码实现（呃不会写用AI了）：
先写一个构建堆的代码：
取出堆中元素：
组合起来即可。整体代码：
懒人代码（堆排版，直接用STL容器+内置函数）：
时间复杂度分析：构建堆的时间复杂度为O(NLOGN)O(N\LOG{N})O(NLOGN)，优化后为O(N)O(N)O(N)。每次重构堆的时间复杂度为O(LOGN)O(\LOG{N})O(LOGN)。复杂度为为O(N+NLOGN)O(N+N\LOG{N})O(N+NLOGN)，整体为为O(NLOGN)O(N\LOG{N})O(NLOGN)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
后期打算继续更新：希尔排序（SHELL SORT），基数排序 以及双向冒泡。敬请期待。
有帮助，赞一个