【技术分享】十大排序算法篇

排序算法分类

非线性时间比较类排序：
比较来绝定元素间的相对次序，时间复杂度不能突破O(nlogn)。
所以称非线性时间比较类排序。

线性时间非比较类排序：
不通过比较来决定元素间的相对次序。
可以突破基于比较排序的时间下界以线性时间运行，
所以称为线性时间非比较类排序。

排序算法概述

常见的有 快速排序、归并排序、堆排序以及冒泡排序 都属于比较类排序算法。
比较类排序是通过比较来决定元素间的相对次序，时间复杂度不能突破 O(nlogn)，因此也称为非线性时间比较类排序。
在冒泡排序之类的排序中，问题规模为 n，又因为需要比较 n 次，所以平均时间复杂度为 O(n²)。在归并排序、快速排序之类的排序中，问题规模通过分治法消减为 logn 次，所以时间复杂度平均 O(nlogn)。
比较类排序的优势是，适用于各种规模的数据，也不在乎数据的分布，都能进行排序。可以说，比较排序适用于一切需要排序的情况。

计数排序、基数排序、桶排序 则属于非比较类排序算法。
非比较排序不通过比较来决定元素间的相对次序，而是通过确定每个元素之前，应该有多少个元素来排序。
由于它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。
非比较排序只要确定每个元素之前的已有的元素个数即可，所有一次遍历即可解决。算法时间复杂度 O(n)。

冒泡排序 (Bubble Sort)

冒泡排序是一种简单的排序算法

算法原理：
重复地遍历待排序的序列，依次比较两个元素，
如果它们的顺序错误就把它们交换过来。
遍历序列的工作是重复地进行直到没有再需要交换为止，
此时说明该序列已经排序完成。

# 第一种
def Bubble_sort(nums):
    for j in range(len(nums)-1,0,-1):
        for i in range(j):
            if nums[i] > nums[i + 1]:
                nums[i], nums[i+1] = nums[i +1], nums[i]
array = [5,9,1,3,0,7,6]
Bubble_sort(array)
print(array)

# 第二种
array = [3,2,5,6,4,8]
for i in range(0, len(array)-1):
    for j in range(0, len(array)-1):
        if array[j] > array[j+1]:
            array[j], array[j+1] = array[j+1], array[j]
print(array)

# 第三种
array = [3,2,5,6,4,8]
res = [
    array.pop(array.index(min(array))) 
    for i in range(len(array))
]
print(res)

快速排序(Quick Sort)

算法原理：
快速排序使用分治法（Divide and conquer）策略来把一个序列分为较小和较大的 2 个子序列，然后递回地排序两个子序列。

def partition(li,left,right):  
    tmp = li[left]
    while left < right:
        while left < right and li[right] >= tmp:  #从右边找比tmp小的数
            right -= 1   #继续从右往左查找
        li[left] = li[right]  #把右边的值写到左边空位上
        
        while left < right and li[left] <= tmp:
            left += 1
        li[right] = li[left] #把左边的值写到右边空位上
      
    li[left] = tmp #把tmp归位
    return  left
def quick_sort(li,left,right):  
    if left < right :#至少两个元素
        mid = partition(li,left,right)
        quick_sort(li,left,mid-1)
        quick_sort(li,mid+1,right)
        
li = [5,7,4,6,3,1,2,9,8]
quick_sort(li,0,len(li)-1)
print(li)

选择排序(Selection Sort)

算法原理：
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
重复第 2 步，直到所有元素均排序完毕。

def selection_sort(num_list):
    length = len(num_list)
    if length <= 1:
        return num_list
    for j in range(length):
        # 假设第一个元素为最小元素
        min_num_index = j
        # 遍历未排序区域元素，以此和未排序区域的第一个元素做对比
        for i in range(j+1, length):
            if num_list[i] < num_list[min_num_index]:
                min_num_index = i
        # 交换位置
        num_list[min_num_index], num_list[j] = num_list[j], num_list[min_num_index]
    return num_list

array = [1, 3, 2, 6, 4, 12, 33, 5, 25]
print(selection_sort(array))

插入排序(Insertion Sort)

算法原理：
从第一个元素开始，该元素可以认为已经被排序；
取出下一个元素，在已经排序的元素序列中从后向前扫描；
如果该元素（已排序）大于新元素，将该元素移到下一位置；
重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置；
将新元素插入到该位置后；
重复步骤 2~5。

def insert_sort(tg):
    for i in range(1, len(tg)):
        for j in range(i, 0, -1):
            if tg[j] < tg[j-1]:
                tg[j-1], tg[j] = tg[j], tg[j-1]
            else:
                break
array = [8,7,5,4,6,3,1]
insert_sort(array)
print(array)

归并排序(Merge Sort)

算法原理：
如果输入内只有一个元素，则直接返回，否则将长度为 n 的输入序列分成两个长度为 n/2 的子列；
分别对这两个子序列进行归并排序，使子序列变为有序状态；
设定两个指针，分别指向两个已经排序子序列的起始位置；
比较两个指针所指向的元素，选择相对小的元素放入到合并空间（用于存放排序结果），并移动指针到下一位置；
重复步骤 3 ~4 直到某一指针达到序列尾；
将另一序列剩下的所有元素直接复制到合并序列尾

def merge(left, right):
    # 合并两个有序列表
    res = []
    while len(left) > 0 and len(right) > 0:
        if left[0] < right[0]:
            res.append(left.pop(0))
        else:
            res.append(right.pop(0))
    if left:
        res.extend(left)
    if right:
        res.extend(right)
    return res

def mergeSort(arr):
    # 归并函数
    n = len(arr)
    if n < 2:
        return arr
    middle = n // 2
    left = arr[:middle] # 取序列左边部分
    right = arr[middle:]# 取序列右边部分
    # 对左边部分序列递归调用归并函数
    left_sort = mergeSort(left) 
    # 对右边部分序列递归调用归并函数
    right_sort = mergeSort(right)
    # 
    return merge(left_sort, right_sort)

array = [8,7,5,4,6,3,1]
print(mergeSort(array))

计数排序(Counting Sort）

算法原理：
找出数组中的最大值 max、最小值 min；
创建一个新数组 C，其长度是 max-min+1，其元素默认值都为 0；
遍历原数组 A 中的元素 A[i]，以 A[i]-min 作为 C 数组的索引，以 A[i] 的值在 A 中元素出
现次数作为 C[A[i]-min] 的值；
对 C 数组变形，新元素的值是该元素与前一个元素值的和，即当 i>1 时 C[i] = C[i] + C[i-1]；
创建结果数组 R，长度和原始数组一样。
从后向前遍历原始数组 A 中的元素 A[i]，使用 A[i] 减去最小值 min 作为索引，在计数数组
C 中找到对应的值 C[A[i]-min]，C[A[i]-min]-1 就是 A[i] 在结果数组 R 中的位置，做完上
述这些操作，将 count[A[i]-min] 减小 1。

def count_sort(nums):
    # 最大值-最小值+1的数组,初始值为0
    bucket = [0] * (max(nums) - min(nums) + 1)
    # 统计原数组中每个元素出现的个数,存储在新开辟的数组中
    for num in nums:
        bucket[num - min(nums)] += 1
    # nums的下标
    i = 0
    # 根据每个元素出现的次数,按照新开辟数组的元素从小到大依次填充到原来的数组中
    for j in range(len(bucket)):
        while bucket[j] > 0:
            nums[i] = j + min(nums)
            bucket[j] -= 1
            i += 1
    return nums

array = [8,7,5,4,6,3,1]
print(count_sort(array))

桶排序(Bucket Sort)

设置一个 BucketSize，作为每个桶所能放置多少个不同数值；
遍历输入数据，并且把数据依次映射到对应的桶里去；
对每个非空的桶进行排序，可以使用其它排序方法，也可以递归使用桶排序；
从非空桶里把排好序的数据拼接起来。

def bucketSort(nums):
    # 选择一个最大的数
    max_num = max(nums)
    # 创建一个元素全是0的列表, 当做桶
    bucket = [0] * (max_num + 1)
    # 把所有元素放入桶中, 即把对应元素个数加一
    for i in nums:
        bucket[i] += 1
    # 存储排序好的元素
    sort_nums = []
    # 取出桶中的元素
    for j in range(len(bucket)):
        if bucket[j] != 0:
            for y in range(bucket[j]):
                sort_nums.append(j)
    return sort_nums

array = [8,7,5,4,6,3,1]
print(bucketSort(array))

基数排序(Radix Sort)

算法原理：
取得数组中的最大数，并取得位数，即为迭代次数 N（例如：数组中最大数值为 1000，则 N=4）；
A 为原始数组，从最低位开始取每个位组成 radix 数组；
对 radix 进行计数排序（利用计数排序适用于小范围数的特点）；
将 radix 依次赋值给原数组；
重复 2~4 步骤 N 次

def radix_sort(s):
    i = 0 # 记录当前正在排拿一位，最低位为1
    max_num = max(s)  # 最大值
    j = len(str(max_num))  # 记录最大值的位数
    while i < j:
        bucket_list =[[] for _ in range(10)] #初始化桶数组
        for x in s:
            bucket_list[int(x / (10**i)) % 10].append(x) # 找到位置放入桶数组
        s.clear()
        for x in bucket_list:   # 放回原序列
            for y in x:
                s.append(y)
        i += 1

array = [8,7,5,4,6,3,1]
radix_sort(array)
print(array)

希尔排序(Shell Sort)

算法原理：
选择一个增量序列 {t1, t2, …, tk}，其中 (ti>tj, i<j, tk=1)；
按增量序列个数 k，对序列进行 k 趟排序；
每趟排序，根据对应的增量 t，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行
直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

def ShellSort(nums):
    step = len(nums)//2 #初始化增量为数组长度的一半
    while step > 0: #增量必须是大于0的整数
        for i in range(step,len(nums)): #遍历需要进行插入排序的数
            ind = i
            while ind >= step and nums[ind] < nums[ind-step]: #对每组进行插入排序
                nums[ind],nums[ind-step] = nums[ind-step],nums[ind]
                ind -= step
        step //= 2 #增量缩小一半
    return nums

array = [8,7,5,4,6,3,1]
ShellSort(array)
print(array)

堆排序(Heapsort)

创建一个堆 H[0……n-1]；
把堆首（最大值）和堆尾互换；
把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
重复步骤 2，直到堆的尺寸为 1。

import math

def buildMaxHeap(arr):
    for i in range(math.floor(len(arr)/2),-1,-1):
        heapify(arr,i)

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

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

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

def heapSort(arr):
    global arrLen
    arrLen = len(arr)
    buildMaxHeap(arr)
    for i in range(len(arr)-1,0,-1):
        swap(arr,0,i)
        arrLen -=1
        heapify(arr, 0)
    return arr
  
array = [8,7,5,4,6,3,1]
print(heapSort(array))

以下排序不在内

TimSort

def binary_search(lst, item, start, end):
    if start == end:
        return start if lst[start] > item else start + 1
    if start > end:
        return start

    mid = (start + end) // 2
    if lst[mid] < item:
        return binary_search(lst, item, mid + 1, end)
    elif lst[mid] > item:
        return binary_search(lst, item, start, mid - 1)
    else:
        return mid


def insertion_sort(lst):
    length = len(lst)

    for index in range(1, length):
        value = lst[index]
        pos = binary_search(lst, value, 0, index - 1)
        lst = lst[:pos] + [value] + lst[pos:index] + lst[index + 1 :]

    return lst


def merge(left, right):
    if not left:
        return right

    if not right:
        return left

    if left[0] < right[0]:
        return [left[0]] + merge(left[1:], right)

    return [right[0]] + merge(left, right[1:])


def tim_sort(lst):
    """
    >>> tim_sort("Python")
    ['P', 'h', 'n', 'o', 't', 'y']
    >>> tim_sort((1.1, 1, 0, -1, -1.1))
    [-1.1, -1, 0, 1, 1.1]
    >>> tim_sort(list(reversed(list(range(7)))))
    [0, 1, 2, 3, 4, 5, 6]
    >>> tim_sort([3, 2, 1]) == insertion_sort([3, 2, 1])
    True
    >>> tim_sort([3, 2, 1]) == sorted([3, 2, 1])
    True
    """
    length = len(lst)
    runs, sorted_runs = [], []
    new_run = [lst[0]]
    sorted_array = []
    i = 1
    while i < length:
        if lst[i] < lst[i - 1]:
            runs.append(new_run)
            new_run = [lst[i]]
        else:
            new_run.append(lst[i])
        i += 1
    runs.append(new_run)

    for run in runs:
        sorted_runs.append(insertion_sort(run))
    for run in sorted_runs:
        sorted_array = merge(sorted_array, run)

    return sorted_array


def main():
    lst = [5, 9, 10, 3, -4, 5, 178, 92, 46, -18, 0, 7]
    sorted_lst = tim_sort(lst)
    print(sorted_lst)


if __name__ == "__main__":
    main()

Stoogesort

def stooge_sort(arr):
    """
    Examples:
    >>> stooge_sort([18.1, 0, -7.1, -1, 2, 2])
    [-7.1, -1, 0, 2, 2, 18.1]

    >>> stooge_sort([])
    []
    """
    stooge(arr, 0, len(arr) - 1)
    return arr


def stooge(arr, i, h):

    if i >= h:
        return

    # If first element is smaller than the last then swap them
    if arr[i] > arr[h]:
        arr[i], arr[h] = arr[h], arr[i]

    # If there are more than 2 elements in the array
    if h - i + 1 > 2:
        t = (int)((h - i + 1) / 3)

        # Recursively sort first 2/3 elements
        stooge(arr, i, (h - t))

        # Recursively sort last 2/3 elements
        stooge(arr, i + t, (h))

        # Recursively sort first 2/3 elements
        stooge(arr, i, (h - t))


if __name__ == "__main__":
    user_input = input("Enter numbers separated by a comma:\n").strip()
    unsorted = [int(item) for item in user_input.split(",")]
    print(stooge_sort(unsorted))