排序算法

一.按时间复杂度划分

• 时间复杂度为o(n^2)

1. 冒泡排序：从第一个数与后面数对比，比后一位数大则调换位置，小于等于不用换位置。

2. 选择排序：从所有数中选出最小的数放在头部置上，再从剩余数选出最小放在开头位置。

3. 插入排序（老是忘记）：前面数比后面数小则与后面数换位置。

• 时间复杂度为o(nlgn)

1. 归并排序：（推测是稳定的）

2. 快速排序：

3. 堆排序：

4. 希尔排序：

• 时间复杂度为o(n)的排序算法

1. 计数排序

2. 基数排序

二.按空间复杂度分：

空间复杂度为o(1):

冒泡排序、选择排序、插入排序、堆排序、希尔排序

1. 空间复杂度为o(logN)-o(N)的：

   快速排序

2. 空间复杂度为o(N):

   归并排序

3. 空间复杂度为o(M):

   M为桶的数量

三.排序算法的稳定性分析

1. 稳定排序算法为：

   冒泡排序，插入排序，归并排序，计数排序，基数排序，桶排序

2. 不稳定的排序算法为：

   选择排序:2，2，2，1（第一次时，最前面的2和最后面的1交换位置）
   快速排序:4，2，2，2（以中间的2来划分，两个二要么被划分到左边位置，要么被划分到右边位置。）
   希尔排序: 4,2,2,1(步长为2时)
   堆排序:5，5，5（建立大根堆后，最大元素与顶部元素交换）

四.各种排序算法最坏情况下复杂度分析

错题整理：

在选择排序中，以下什么情况下选择排序会更快执行：
A.数据已按升序排列
B.数据已按升降序排列
C.两者花费时间相同。

记忆：堆选归基与初始序列无关，堆选快希不稳定。

已知数组元素基本有序情况下，下面采用哪个算法对数组排序时间复杂度最低
A.直接

深入理解各种排序专题：

一.堆排序

1.必备知识：

大根堆：对于n个元素的序列
小根堆：