深入理解排序算法

柔光的暖阳◎ 2022-12-28 14:13 180阅读 0赞

### 前言：什么是排序，什么是算法？ ###

**1.排序(Sort)**

*  将杂乱无章的**数据元素**，通过一定的方法按**关键字**顺序排列的过程叫做排序。目的是将一组“**无序**”的记录序列调整为“**有序**”的记录序列，比如说升序、降序、奇偶排序(奇升偶降、奇降偶升)等。

**2.算法(Algorithm)**

*  指解题方案的准确而完整的描述，是一系列解决问题的清晰**指令**。代表着用系统的方法描述解决问题的策略机制。一个算法的优劣可以用**空间复杂度**与**时间复杂度**来衡量，常用的算法有递推法、递归法、穷举法、贪心算法、分治法、动态规划法、迭代法、分支界限法、回溯法等

**3.常用排序算法**

*  ![1][]

**术语解读：**

1.  **时间复杂度**
    
    执行算法所需要的计算工作量(耗费的**时间**)，一般来说，计算机算法是问题规模n 的函数f(n)，记做T(n)=Ο(f(n))
    
     *  渐进时间复杂度：问题的规模n 越大，算法执行的时间的增长率与f(n) 的增长率正相关
     *  冒泡排序：问题规模为n，需要比较n次，所以平均时间复杂度为**O(n²)**
     *  归并排序：问题规模通过分治法消减为**logN**次，所以时间复杂度平均**O(nlogn)**
2.  **空间复杂度**  
    指执行算法所需要消耗的**内存**空间，其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示  
    ![2][]
3.  **排序方式1**
    
     *  内排(In-place):所有操作都在内存中完成。
     *  外排(Out-place):由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行。
4.  **排序方式2**
    
     *  比较排序：通过元素间相互比较确定位置得到排序结果。如冒泡排序、归并排序、快速排序、堆排序。
     *  非比较排序：通过确定每个元素位置之前，应该有多少个元素来排序，针对数组arr，计算arr\[i\]之前有多少个元素，则唯一确定了arr\[i\]在排序后数组中的位置。如计数排序、基数排序、桶排序等。![3][]
    
    1.  **小结**  
        比较排序适用大多数的场景。
        
        非比较排序时间复杂度低，但由于非比较排序需要占用空间来确定唯一位置。所以对数据规模和数据分布有一定的要求。
5.  **稳定性**
    
     *  稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的**前面**；
     *  不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的**后面**；
6.  **额外补充**
    
     *  k："桶"的个数
     *  O(log n)：算法中log级别的时间复杂度都是由于使用了分治思想，底数a由分治的复杂度决定，二分法a=2，三分法a=3，不过无论底数是什么,log级别的渐进意义是一样的。
     *  大O的定义体现的是一个极限的思想。我们先考虑O(logx(n))和O(logy(n))，x!=y，再考虑n趋于无穷的情况。求当n趋于无穷大时logx(n)/logy(n)的极限可以发现，极限等于lny/lnx，也就是一个常数，也就是说，在n趋于无穷大的时候，这两个东西仅差一个常数。所以从研究算法的角度log的底数不重要。  
        \*![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqa3dhbg_size_16_color_FFFFFF_t_70][]

**正片开始：**

1.  **\[交换排序\][冒泡排序(Bubble Sort)][Bubble Sort]**
2.  **\[交换排序\][快速排序(Quick Sort)][Quick Sort]**
3.  **\[插入排序\][普通插入排序(Insertion Sort)][Insertion Sort]**
4.  **\[插入排序\][希尔排序(Shell Sort)][Shell Sort]**
5.  **\[选择排序\][简单选择排序(Selection Sort)][Selection Sort]**
6.  **\[非比较类排序\][计数排序(Counting Sort)][Counting Sort]**

未完待续，同步更新…

**\[选择排序\]堆排序(Heap Sort)**  
**\[归并排序\]二路归并排序(Merge Sort)**  
**\[归并排序\]多路归并排序(Merge Sort)**

**\[非比较类排序\]桶排序(Bucket Sort)**  
**\[非比较类排序\]基数排序(Radix Sort)**

[1]: /images/20221120/d1350e4893464abfbee53bb989f3c9f9.png
[2]: /images/20221120/13c0a890f8cb45ce95fdd84837c9a9e4.png
[3]: /images/20221120/6355e8b7f0be466c8c0338fdc5adf183.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqa3dhbg_size_16_color_FFFFFF_t_70]: /images/20221120/c42a41446dc749e19be6309a9bdab700.png
[Bubble Sort]: https://blog.csdn.net/wjkwan/article/details/111581673
[Quick Sort]: https://blog.csdn.net/wjkwan/article/details/111588493
[Insertion Sort]: https://blog.csdn.net/wjkwan/article/details/111591072
[Shell Sort]: https://blog.csdn.net/wjkwan/article/details/111592589
[Selection Sort]: https://blog.csdn.net/wjkwan/article/details/111594080
[Counting Sort]: https://blog.csdn.net/wjkwan/article/details/111771398