六大排序算法图解以及python实现

[TOC]

冒泡排序——名字好听的排序

大学最先接触的一种排序算法，听名字就很萌的感觉，也是比较简单的一种，算法图示如下：

上图为第一次进行比较的图示：
- 从第一个开始每次都比较相邻的两个数，如果发现顺序不对，就把两个数交换一下，直到最后一个。这个时候，最大的数自然而然就跑到最后一位上面去了。
- 第二次的时候，也从第一个开始，不过只需要循环到n-2处就行了（因为n-1处经过第一次洗礼已经时最大了嘛。）
  
  。。。。。。依此类推，循环n次，整个数组就会变成有序的了。

实现代码如下：

def bubble(nums):
    for i in range(len(nums)):
        for j in range(len(nums)-i-1):
            if nums[j+1] > nums[j]:
                nums[j+1], nums[j] = nums[j], nums[j+1]

选择排序——简单粗暴的排序

选择排序大概是所有排序中最好理解，最简单粗暴的排序了。算法图示如下：

如图所示：
1. 在第一次遍历中，从最开始到最后。找到最大的数，并于最后一个交换。
2. 在第二次中，从最开始到倒数第二个。找到最大的数，并于倒数第二个交换。
  
  。。。。以此类推，循环n次。完成没有任何技术含量，所以效率几乎也是所有排序中最低的，强烈不推荐。

算法实现

def select_sort(nums):
    for i in range(len(nums)):
        flag = i
        for j in range(i, len(nums)):
            if nums[j] > nums[flag]:
                flag = j
        nums[i], nums[flag] = nums[flag], nums[i]

插入排序——优雅不要污

也是很简单的一种算法，同时也是后面的希尔排序的基础。如下图流程所示：

基本思想：
1. 首先明确，第一个数肯定是有序的呀（一个数难道还能无序吗？），然后从第二个开始，从后往前扫描，把这个数插入到合适的位置，比第二个数大的一次往后面移动。
2. 第二个数移动正确的位置之后，前两个数就是有序的，依次把后面的数按照刚才的方法插入到合适的位置，整个数组就变成有序的了。

代码实现：

def insert_sort(nums):
    for i in range(1, len(nums)):
        temp = nums[i]
        last = 0
        for j in range(i-1, -1, -1):
            if nums[j] > temp:
                nums[j + 1] = nums[j]
            else:
                last = j + 1
                break
        nums[last] = temp

希尔排序——插入排序的升级版

希尔排序是插入排序的优化版，虽然表面上看起来并没有什么优化，相对于插入排序引入了步长的概念

如图所示：上图就表示step为4的场景。这时候整数数组的数据按照步长分为如上四组，对每一组都分别进行插入排序。
- 当完成第一轮插入排序之后，step的步长减半，进行第二轮插入排序。
  
  。。。。以此类推，直到步长step=1的那一轮排序完成，整个数组就可以变为有序了。
不过问题来了：这最后一轮不和插入排序一毛一样么？这能提高效率：

回答是：当然可以！其实每一次我们排序的时候整体都在逐渐趋于有序，都在不断的降低最后一步时的时间复杂度。在step合适的情况下，时间复杂度可以达到O（n^1.3），虽然我也不知道怎么算出来的，估计得问问数学家了。

快速排序——名字最牛逼的排序

大名鼎鼎的快排，听名字就无意中透漏着我是最屌的感觉。
快排的基本思想就是先找到一个数作为patition，将数组中比patition小的数放在其左边，比patition大的数放在其右边，然后对其每一边再分别进行相同的操作（递归实现）。

上图是具体实现的思路：
1. 我们一般已第一个数为partition，然后由两个标兵分别指向开始和结尾。
2. 由最右边的橙色箭头开始往前扫描，直到扫描到比partition小的数字停下来，然后再由蓝色箭头向后扫描，直到遇见比partition大的数字停下来。然后交换停下来的两个数字。
3. 就这样按照顺序，一直扫描。知道橙蓝两个箭头相遇，将相遇时的数字与partition交换就行了。

编程实现：


def quick_sort(nums, start, end):
    if end < start:
        return 0
    flag = nums[start]
    left = start
    right = end
    while start < end:
        while nums[end] > flag and end > start:
            end -= 1
        while nums[start] <= flag and end > start:
            start += 1
        nums[end], nums[start] = nums[start], nums[end]
    nums[left], nums[end] = nums[end], nums[left]
    quick_sort(nums, left, end - 1)
    quick_sort(nums, end + 1, right)  
def main():
    nums = [6, 3, 10, 5, 1, 9, 2, 7, 23, 4, 14]
    quick_sort(nums, 0, len(nums) - 1)
    print(nums)

归并排序——分治法的完美践行者

归并排序是一种利用分治思想实现的排序，也是一种效率很高的排序。其排序流程具体如下：

如图所示：
- 在归并排序的时候，我们将数组不断的拆分为两半，直到数据只剩一个的时候，然后再按照大小顺序把他们拼装起来。
编码实现：

def merge_sort(nums):
    if len(nums) == 1:
        return nums
    mid = len(nums) // 2
    left = merge_sort(nums[:mid])
    right = merge_sort(nums[mid:])
    return merge(left, right)
def merge(left, right):
    temp = []
    left_p, right_p = 0, 0
    while left_p < len(left) and right_p < len(right):
        if left[left_p] < right[right_p]:
            temp.append(left[left_p])
            left_p += 1
        else:
            temp.append(right[right_p])
            right_p += 1
    temp += (left[left_p:])
    temp += (right[right_p:])
    return temp
def main():
    numbers = [6, 3, 10, 5, 45, 9, 2, 7, 23, 4, 14]
    numbers = merge_sort(numbers)
    print(numbers)

代码好像比之前的都要多一点，不过思路还是很简单的。主要是多了一个merge的过程：

对于分别有序的两个数组，通过每次取出一个数据比较，将较小的那个放到新的数组中，较大的那个等待下次继续比较，就这样一直取，比较，取，比较，直到两个数组的数都放在了新的数组中。返回新的数组。
大体的流程还是通过递归实现的，其实大部分分治的算法都是通过递归搞定的，方便理解。
- 就效率而言，归并排序是六种排序中时间复杂度最好的，即使是最差情况，都是O(nlogn)，不过由于归并排序需要额外的空间，所以也是一种拿空间换时间的策略。

六大算法的效率比较

排序

| 排序法 | 平均时间复杂度 | 最差情形 | 稳定度 | 额外空间 | 备注 |
| ——- | ——– | ———– | —- | ——– | ——— |
| 冒泡排序 | O(n2) | O(n2) | 稳定 | O(1) | n小时较好 |
| 选择排序 | O(n2) | O(n2) | 不稳定 | O(1) | n小时较好 |
| 插入排序 | O(n2) | O(n2) | 稳定 | O(1) | 大部分已排序时较好 |
| Shell排序 | O(nlogn) | O(ns) 1<s<2 | 不稳定 | O(1) | s是所选分组 |
| 快速排序 | O(nlogn) | O(n2) | 不稳定 | O(nlogn) | n大时较好 |
| 归并排序 | O(nlogn) | O(nlogn) | 稳定 | O(1) | n大时较好 |