本文主要是介绍算法#11--用简单的思维理解归并排序和三向切分快速排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
归并排序
1.原理
归并操作（merge），也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。
步骤：
- 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
- 设定两个指针，最初位置分别为两个已经排序序列的起始位置
- 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
- 重复步骤3直到某一指针到达序列尾
- 将另一序列剩下的所有元素直接复制到合并序列尾
2.特点
它能够保证将任意长度为N的数组排序时间和NlogN成正比，它的主要缺点是它所需的额外空间和N成正比。
3.代码
详细代码下载地址：
https://github.com/tclxspy/Articles/blob/master/algorithm/Code/MergeSort.java
《算法第四版》里对代码逻辑作了很好的解释：
4.复杂度
最差时间复杂度 О(nlogn)最优时间复杂度 О(n)平均时间复杂度 О(nlogn)最差空间复杂度 总共О(n)
动态图：
以及，
快速排序
1.原理
快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。它可能是应用最广泛的排序算法了。
步骤为：
- 从数列中挑出一个元素，称为”基准”（pivot）。
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
2.特点
实现简单，适用于各种不同的输入数据且在一般应用中比其他排序算法都要快很多。
原地排序（只需要一哥很小的辅助栈），且将长度为N的数组排序所需的时间和NlgN成正比。其他排序算法都无法将这两个优点结合起来。
内循环比大多数排序算法都要短小，这意味着它无论在理论上海是在实际中都要快。
但是，它有一个潜在的缺点：在切分不平衡时这个程序会极为低效。例如，如果第一次从最小的元素切分，第二次从第二小的元素切分，如此这般，每次调用只会移除一个元素。这会导致一个大子数组需要切分很多次。我们要在快速排序前将数组随机排序的主要原因就是要避免这种情况。
3.代码
在实际应用中经常会出现含有大量重复元素的数组。所以我们用“三向切分”，切分为小于、等于和大于三部分。
详细代码下载地址：
https://github.com/tclxspy/Articles/blob/master/algorithm/Code/Quick3Way.java
《算法第四版》里对代码逻辑作了很好的解释：
4.复杂度
最差时间复杂度 О(n^2)最优时间复杂度 О(nlogn)平均时间复杂度 О(nlogn)最差空间复杂度 根据实现的方式不同而不同
动态图：
这篇关于算法#11--用简单的思维理解归并排序和三向切分快速排序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
