[TOC]

快速排序

排序流程:

快速排序算法通过多次比较和交换来实现排序，其排序流程如下：

  1. 首先设定一个分界值，通过该分界值将数组分成左右两部分。

  2. 将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。

  3. 然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。

  4. 重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

时间复杂度和空间复杂度平均值都是O(log2n)

计数排序

它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围）,此时快于任何比较排序算法,计数排序算法是一个稳定的排序算法,快排不是

排序过程(十分巧妙运用数组):

假设输入的线性表L的长度为n，L=L1,L2,..,Ln；线性表的元素属于有限偏序集S，|S|=k且k=O(n)，S={S1,S2,..Sk}；则计数排序可以描述如下：

1、扫描整个集合S，对每一个Si∈S，找到在线性表L中小于等于Si的元素的个数T(Si)；

2、扫描整个线性表L，对L中的每一个元素Li，将Li放在输出线性表的第T(Li)个位置上，并将T(Li)减1。

举例:

​ 假设要排序的数组为 A = {1,0,3,1,0,1,1}

这里最大值为3，最小值为0，那么我们创建一个数组C，长度为4.

然后一趟扫描数组A，得到A中各个元素的总数，并保持到数组C的对应单元中。

比如0 的出现次数为2次，则 C[0] = 2;1 的出现次数为4次，则C[1] = 4, (求出现次数也不麻烦,因为值成为了下标,那对下标对应的值累计就行了) 最终c数组如图:

img

由于C 是以A的元素为下标的，所以这样一做，A中的元素在C中自然就成为有序的了，这里我们可以知道 顺序为 0,1,3 (2 的计数为0),

然后我们把这个在C中的记录按每个元素的计数展开到输出数组B中，排序就完成了。

也就是 B[0] 到 B[1] 为0 B[2] 到 B[5] 为1 这样依此类推。(累加就行)

时间复杂度为: O(nlogn)