十大排序代码实现（python）

写在前面：

参考文章：十大经典排序算法 本文的逻辑顺序基于从第一篇参考博文上借鉴过来的图，并且都是按照升序排序写的程序，程序语言采用python。

冒泡排序

思路：

冒泡排序的基本思想就是让小的数逐渐‘浮上来’。也就是说：

• 第一次冒泡：将最小的数调换到最前面；

• 第二次冒泡：将第二小的数调换到最小的数的后面，也就是数组中的第二位；

• 第三次冒泡，将第三小的数调换到数组中的第三位；

  ... ...

代码如下：

def bubble_sort(nums):
    # 让小的数一步一步‘浮’上来
    n = len(nums)
    for i in range(n-1):
        for j in range(i+1,n):
            if nums[i]>nums[j]:
                nums[i],nums[j] = nums[j],nums[i]
    return nums

时间复杂度： O(n^2)，实际上是n-1 + n-2 + n-3 + ...，所以是平方的量级。

空间复杂度： O(l)，没有借助额外空间。

快速排序

思路

快速排序的基本思路就是在一遍快排中，以基准值为基础，将比基准值小的数放到基准值的左边，比基准值大的数放在基准值的右边。然后在递归的快排基准值的左边和右边。至于基准值的取法，理论上来讲是无所谓的。

先来一个比较简单直接的吧。它的思路就是遍历一遍数组，用两个空的数组来存储比基准值大和比基准值小的数，代码如下：

def quick_sort1(nums):
    n = len(nums)
    if n ==1 or len(nums)==0:
        return nums  
    left = []
    right = []
    for i in range(1,n):
        if nums[i] <= nums[0]:
            left.append(nums[i])
        else:
            right.append(nums[i])         
    return quick_sort1(left)+[nums[0]]+quick_sort1(right)

上面的使用了额外的空间，空间复杂度比较高，下面是基于双指针的想法的代码，比较常见：

def quick_sort2(nums,left,right):
    l,r = left,right-1
    while  l < r:
        if nums[r] < nums[l]:
            nums[r], nums[l] = nums[l], nums[r]
            l += 1
            while l < r:
                if nums[l] > nums[r]:
                    nums[r],nums[l] = nums[l], nums[r]
                    r -= 1
                    break
                else:
                    l += 1
        else:
            r -= 1
    if l-left > 1:                
        quick_sort2(nums, left, l)
    if right - r > 1:
        quick_sort2(nums, l+1, right)
    return nums

简单插入排序

希尔排序

简单选择排序

堆排序

二路归并排序

多路归并排序

计数排序

桶排序

基数排序