10个常用排序算法

参考：https://sort.hust.cc/

0x01 冒泡排序

原理
比较相邻的元素。如果第一个比第二个大,就交换他们两个。 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。 针对所有的元素重复以上的步骤,除了最后一个。 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

实现代码

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

print(bubblesort([2,3,1,5,4,7,0,8,0]))

0x02 选择排序

原理
第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

实现代码

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

print(selectsort([3,2,1,5,7,6,9,0]))

0x03 插入排序

原理
从后往前逐个进行比较,找出插入位置,将该元素插入到有序数列的合适位置中。

实现代码

def insertionsort(nums):
    for i in range(len(nums)):
        a = i-1
        index = nums[i]
        while a >= 0 and nums[a] > index:
            nums[a+1] = nums[a]
            a -= 1
        nums[a+1] = index
    return nums

print(insertionsort([2,3,4,1,7,6,0,9,8,5]))

0x04 希尔排序

原理
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
一种特殊的插入排序

实现代码

def shellsort(nums):
    import math
    gap = 1
    while(gap < len(nums)/3):
        gap = gap*3+1
    while gap > 0:
        for i in range(gap,len(nums)):
            temp = nums[i]
            j = i-gap
            while j>=0 and nums[j] > temp:
                nums[j+gap] = nums[j]
                j-=gap
            nums[j+gap] = temp
        gap = int(math.floor(gap/3))
    return nums

print(shellsort([3,2,1,4,5,7,6,9,0,8]))

0x05 归并排序

原理
已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

实现代码

def mergesort(nums):
    import math
    if len(nums) < 2:
        return nums
    middle = int(math.floor(len(nums)/2))
    left,right = nums[0:middle],nums[middle:]
    return merge(mergesort(left),mergesort(right))

def merge(left,right):
    result = []
    while left and right:
        if left[0] < right[0]:
            result.append(left.pop(0));
        else:
            result.append((right.pop(0)));
    while left:
        result.append(left.pop(0));
    while right:
        result.append(right.pop(0));
    return result

print(mergesort([5,4,3,2,1,6,8,0,9,7]))

0x06 快速排序

原理
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

一趟快速排序的算法是:
(1)设置两个变量i、j，排序开始的时候：i=0，j=N-1；
(2)以第一个数组元素作为关键数据，赋值给key，即key=A[0]；
(3)从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]和A[i]的值交换；
(4)从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]的值交换；
(5)重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）

实现代码

def quicksort(nums):
    if len(nums) >= 2:
        middle = nums[(len(nums)//2)]
        left = []
        right = []
        nums.remove(middle)
        for num in nums:
            if num > middle:
                right.append(num)
            else:
                left.append(num)
        return quicksort(left)+[middle]+quicksort(right)
    else:
        return nums

print(quicksort([3,2,1,6,5,4,9,7,0,8]))

0x07 堆排序

原理
利用堆这种数据结构而设计的一种排序算法，一种选择排序

(1)根据初始数组去构造初始堆（构建一个完全二叉树，保证所有的父结点都比它的孩子结点数值大）；
(2)每次交换第一个和最后一个元素，输出最后一个元素（最大值），然后把剩下元素重新调整为大根堆；
(3)循环第二步，直到当输出完最后一个元素。

实现代码

def buildmaxheap(nums):
    import math
    for i in range(int(math.floor(len(nums)/2)),-1,-1):
        heapify(nums,i)

def heapify(nums,i):
    left = 2*i+1
    right = 2*i+2
    largest = i
    if left < numslen and nums[left] > nums[largest]:
        largest = left
    if right < numslen and nums[right] > nums[largest]:
        largest = right

    if largest != i:
        swap(nums,i,largest)
        heapify(nums,largest)

def swap(nums,i,j):
    nums[i],nums[j] = nums[j],nums[i]

def heapsort(nums):
    global numslen
    numslen = len(nums)
    buildmaxheap(nums)
    for i in range(len(nums)-1,0,-1):
        swap(nums,0,i)
        numslen -=1
        heapify(nums,0)
    return nums

print(heapsort([9,2,3,1,4,5,6,8,0,7]))

0x08 计数排序

原理
对于给定的输入序列中的每一个元素x，确定该序列中值小于等于x的元素的个数（此处并非比较各元素的大小，而是通过对元素值的计数和计数值的累加来确定）。一旦有了这个信息，就可以将x直接存放到最终的输出序列的正确位置上。

实现代码

def countsort(nums):
    lennums = len(nums)
    nums2 = [None]*lennums
    for i in range(lennums):
        p = 0
        q = 0
        for j in range(lennums):
            if nums[i] > nums[j]:
                p += 1
            elif nums[i] == nums[j]:
                q += 1
        for k in range(p,p+q):
            nums2[k] = nums[i]
    return nums2

print(countsort([1,3,2,4,5,6,8,7,3,5]))

0x09 桶排序

原理
数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。

每个桶相差为1更方便

实现代码

def bucketsort(nums):
    max_num = max(nums)
    bucket = [0]*(max_num+1)
    sort = []
    for i in nums:
        bucket[i] += 1
    for j in range(len(bucket)):
        if bucket[j] != 0:
            for k in range(bucket[j]):
                sort.append(j)
    return sort

print(bucketsort([3,2,2,1,0,3,4,7,5,7,6]))

0x10 基数排序

原理
将整数按位数切割成不同的数字，然后按每个位数分别比较。

1、首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中；
2、接下来将这些桶子中的数值按照个位数数值重新串接起来；
3、再进行一次分配，这次是根据十位数来分配；
4、接下来将这些桶子中的数值重新串接起来；
5、重复分配与串联操作，直到最高位为空。

实现代码

def radixsort(nums):
    i = 0
    max_num = max(nums)
    j = len(str(max_num))
    while i < j:
        bucket = [[] for _ in range(10)]            #这里的_可以换成其他，但是不能用已出现的字符，会产生冲突
        print("test:",_)      #会输出9
        for num in nums:
            bucket[int(num/(10**i))%10].append(num)
        nums = []
        for x in bucket:
            for y in x:
                nums.append(y)
        i += 1
    return nums

print(radixsort([22,1,4,34,76,67,54,48,0,90,78]))

• 桶排序VS计数排序VS基数排序

  桶排序：每个桶存储一定范围的数值；
  计数排序：每个桶只存储单一键值；
  基数排序：根据键值的每位数字来分配桶。