排序算法比较表

「爱情、让人受尽委屈。」 2022-12-02 15:02 98阅读 0赞

辅助记忆  
**时间复杂度记忆-**  
**冒泡、选择、直接 排序**需要两个for循环，每次只关注一个元素，平均时间复杂度为O（n2）O（n2）（一遍找元素O(n)O(n)，一遍找位置O(n)O(n)）  
\*\*快速、归并、希尔、堆基于二分思想，\*\*log以2为底，平均时间复杂度为O(nlogn)O(nlogn)（一遍找元素O(n)O(n)，一遍找位置O(logn)O(logn)）  
**稳定性记忆-“快希选堆”（快牺牲稳定性）**  
排序算法的稳定性：排序前后相同元素的相对位置不变，则称排序算法是稳定的；否则排序算法是不稳定的。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzAzMTg1_size_16_color_FFFFFF_t_70_pic_center]

不想记口诀就自己理解吧，也不难。

**1、直接插入排序**，因为该排序算法是先让左边有序，然后从右边依次选择数据放到左边，并使左边有序，那么最好的情况就是原序列本身就是升序，每次只需从右边往左边添加数据，不需要对左边已经排好序的数据进行排序，那么一共只需添加n次；最坏的情况是序列本身是降序的，那么每次从右边往左边添加数据的时候都要与左边的数据进行对比移动，第n次需要移动（n-1）次，则一共需要移动1,+2+3+…+(n-1)=n(n-1)/2次，故时间复杂度范围为O（n）~O(n2)。平均复杂度为O(n2)。

**2.希尔排序**，希尔排序是对直接插入排序算法的改进，即选取增量序列做一次直接插入排序，然后缩小增量，直到最后一个增量为1。我上网查了一下，感觉希尔排序的复杂度比较麻烦，没什么参考资料，这里就直接给出答案，O（n）~O(n2)，我就把它当做直接插入排序记了。\*\*ps：好像有人说最好的情况是O（n1.3）（O（n^1+ξ），ξ就是间隔GAP）\*\*  
**3.选择排序**，选择排序每次选择最大的数据放在数组的后面。每趟都需要对数组进行遍历找出最大的放在后面 ，因此最好的情况一共需要访问1+2+3+…+n-1= n(n-1)/2次，故时间复杂对为O(n2)。平均时间复杂度为O(n2)。

**4.堆排序**，比较好记，堆排序要先构造初始堆，时间复杂度为O（n）,然后排序重建堆的时间复杂度为O（nlog2n）,所以复杂度为O（n）+ O（nlog2n）= O（nlog2n）,堆排序的好坏情况都是一样的，时间复杂度为O（nlog2n）。平均时间复杂度O（nlog2n）。

\*\*5.冒泡排序，\*\*冒泡排序是每次从左边选择一个数据一次与右边数据比较，如果比右边大就交换位置，继续往后比较，那么最好的情况就是序列本身就是升序的，一趟下来比较了n-1次不需要交换结束排序，时间复杂度为O（n）；最坏的情况序列本身降序，那么第一次就需要交换n-1次，第二次排序需要交换n-2次，最后一共需要交换(n-1)+(n-2)+(n-3)+….+1= n(n-1)/2，所以时间复杂度为O（n2）。故时间复杂度为O（n）~O(n2)。平均复杂度为O(n^2)。

**6.快速排序**，快排的原理就是每次从当前数组中选出一个pivot元素，并依此元素遍历数组，将数组划分成两部分:小于pivot的元素和大于pivot的元素。然后在两个子数组中分别递归地进行这个\*\*\*作。因为是2分，所以一共需要划分log2n次，每次遍历一遍数组，复杂度nlog2n。最坏的情况是每次选出的pivot都是当前数组中最大或最小的元素，此时只能划分出一个子数组(另一个没有元素)。那么一共需要划分n次，每次遍历一遍，时间复杂度为O(n^2)。故时间复杂度为O（nlog2n）~ O(n^2)。平均负载度为O（nlog2n）。

**7.归并排序**，由于是从序列中间对半分，分治排序，因此不管情况好还都要进行划分log2n次，每次遍历一遍数组，时间复杂度O（nlog2n）。平均复杂度为O（nlog2n）。

**8.基数排序**，

空间复杂度的话，前五个都是O(1),后面快速排序的空间复杂度为O（nlog2n）,归并排序是O（n）,不想推就记一下吧，比好好记。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzAzMTg1_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/86a8ae0564e5441a86635c69adcd4325.png