简单介绍几种经典的排序算法

排序算法的几个方面

• 排序算法的执行效率

  一般会从三个方面去分析排序算法的执行效率。

  最好时间复杂度，最坏时间复杂度和平均时间复杂度。

  时间复杂度的系数，常数和低阶。

  比较次数和交换（或移动）次数 （比较操作的耗时少于交换和移动的操作耗时）

• 排序算法的内存消耗

  空间复杂度衡量内存消耗。又分为原地排序算法（在原数据存储空间上完成排序操作），非原地排序算法（需要额外的非常量级的数据存储空间才能完成排序）

  需要注意的一个排序算法是原地排序算法，但他的空间复杂度可能并不是O(1),但是一个排序算法的空间复杂度是O(1)，那么他肯定是原地排序算法。

• 排序算法的稳定性

  根据稳定性，又分为稳定排序算法和不稳定排序算法。

  如果待排序的数据中存在值相等的元素，经过排序算法排序后，相等元素之间原有的先后顺序不变，则为稳定排序算法，反之则为不稳定排序算法。

1. 冒泡排序

• 整个冒泡排序过程包含多次冒泡操作。每一次冒泡操作都会遍历整个数组，依次对数组中相邻的元素进行比较，看看是否满足大小关系要求，如果不满足，就将他们互换位置。一次冒泡操作会至少让一个元素移动到它应该再的位置，重复n次就完成了n个数据的排序工作。

2. 插入排序

• 将数组中的数据分为两个区间：已排序区和未排序区。初始已排序区间只有一个元素，就是数组中的第一个元素。插入算法的核心思想就是取未排序区间中的数据，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中的元素为空，则算法结束。

3. 选择排序

• 选择排序的思路也是将整个数组划分为已排序区和未排序区。每次从未排序区中找到最小的元素，将其放在已排序区间的末尾。

4. 快速排序

• 快速排序利用了分治算法的思想。在要排序的数组中下标p到r的数据。我们则选择p到r的之间的任意一个数据作为pivot（分区点），然后遍历p到r的数据，将小于pivot的放在左边，将大于或等于pivot的放在右边，将pivot放在中间。经过这一步骤的操作后，就将p到r的数据分成了3个部分。假设pivot的坐标为q，则p到q-1的下标的数据都小于pivot，中间是pivot，q+1到r的数据都大于或等于pivot。将分割开的两个数据继续用这样的操作进行分区，直到待排序区间大小为1，则数据中所有的数据都有序了。

5. 归并排序

• 归并排序利用了分治算法的思想。将待排序的数组从中间分解成前后两个部分，然后再对前后两个部分从中间分解成前后两个部分，重复这样的操作，直到分解的两个部分为1个元素。然后再将相邻的两个部分合并为有序数组。重复这样的操作，直到合并为一整个数组，排序就结束了。

6. 桶排序

• 桶排序的核心思想就是先定义几个有序的桶，其实就是定义不同的数据范围，将要排序的数据根据所属的范围分到这几个桶里面，再对每个桶里的数据单独进行排序，再把每个桶里的数据按照顺序依次去除，组成的序列就是有序的了。

7. 计数排序

• 计数排序是桶排序的一种特殊情况。当要排序的n个数据所处的范围并不大时，如最大值为k，则将数据划成k个桶，将数据放入到对应的桶中，则每个桶内的数据都是相等的。

8. 基数排序

• 基数排序的数据需要能划分高低位，且位之间有递进关系，每一位的数据范围不能太大。核心思路就是将数据划分高低位，内部再通过桶排序或者计数排序的思路去完成每一位的排序工作。

图表对比

排序算法	是原地排序	是稳定排序	平均时间复杂度	空间复杂度
冒泡排序	是	是	O(n²)	O(1)
插入排序	是	是	O(n²)	O(1)
选择排序	是	否	O(n²)	O(1)
快速排序	是	否	O(nlogn)	O(logn)
归并排序	否	是	O(nlogn)	O(n)
桶排序	否	是	O(n+k),k表示数据范围	O(n+k)
计数排序	否	是	O(n)	O(n+k)
基数排序	否	是	O(dn),d表示数据纬度	O(n+k)