【代码】排序算法python全实现（冒泡、插入、选择、睡眠...）

旧城等待， 2022-04-10 06:26 168阅读 0赞

[Github][]

### 文章目录 ###

*  冒泡排序
 *  插入排序
 *  选择排序
 *  归并排序
 *  快速排序
 *  计数排序

# 冒泡排序 #

import time
    
    
    def bubble_sort(array):
        length = len(array)
        if length <= 1:
            return
    
        for i in range(length):
            made_swap = False
            for j in range(length - 1 - i):
                if array[j] > array[j + 1]:
                    array[j], array[j + 1] = array[j + 1], array[j]
                    made_swap = True
            if not made_swap:
                break
    
    
    if __name__ == '__main__':
        array = [5, 6, -1, 4, 2, 8, 10, 7, 6]
        start = time.clock()
        bubble_sort(array)
        print(array)
        end = time.clock()
        print('用时：', str(end - start))

# 插入排序 #

import time
    
    
    def insertion_sort(array):
        length = len(array)
        if length <= 1:
            return
            
        for i in range(1, length):
            value = array[i]
            j = i - 1
            while j >= 0 and array[j] > value:
                array[j + 1] = array[j]
                j -= 1
            array[j + 1] = value
    
    
    if __name__ == '__main__':
        array = [5, 6, -1, 4, 2, 8, 10, 7, 6]
        start = time.clock()
        insertion_sort(array)
        print(array)
        end = time.clock()
        print('用时：', str(end - start))

# 选择排序 #

import time
    
    
    def insertion_sort(array):
        length = len(array)
        if length <= 1:
            return
    
        for i in range(length):
            min_index = i
            min_val = array[i]
            for j in range(i, length):
                if array[j] < min_val:
                    min_val = array[j]
                    min_index = j
            array[i], array[min_index] = array[min_index], array[i]
    
    
    if __name__ == '__main__':
        array = [5, 6, -1, 4, 2, 8, 10, 7, 6]
        start = time.clock()
        insertion_sort(array)
        print(array)
        end = time.clock()
        print('用时：', str(end - start))

# 归并排序 #

import time
    
    
    def merge_sort(array):
        merge_out(array, 0, len(array) - 1)
    
    
    def merge_out(array, low, high):
        if low < high:
            mid = low + (high - low) // 2
            merge_out(array, low, mid)
            merge_out(array, mid + 1, high)
            merge_in(array, low, mid, high)
    
    
    def merge_in(array, low, mid, high):
        # a[low:mid], a[mid+1, high] are sorted.
        i, j = low, mid + 1
        tmp = []
        while i <= mid and j <= high:
            if array[i] <= array[j]:
                tmp.append(array[i])
                i += 1
            else:
                tmp.append(array[j])
                j += 1
        # 将超出索引未添加进tmp的添加进去
        if i <= mid:  # 如果mid右边已添加，则需补充mid左边部分
            start, end = i, mid
        else:
            start, end = j, high
        tmp.extend(array[start:end + 1])  # 常规+1
        array[low:high + 1] = tmp
    
    
    if __name__ == '__main__':
        array = [5, 6, -1, 4, 2, 8, 10, 7, 6]
        start = time.clock()
        merge_sort(array)
        print(array)
        end = time.clock()
        print('用时：', str(end - start))

# 快速排序 #

import time
    import random
    
    def quick_sort(array):
        quick_out(array, 0, len(array) - 1)
    
    
    def quick_out(array, low, high):
        if low < high:
            k = random.randint(low, high)
            array[low], array[k] = array[k], array[low] # 将分区点换到首位，避免了K的传参
            m = partition(array, low, high) 
            quick_out(array, low, m - 1)
            quick_out(array, m + 1, high)
    
    # 返回pivot正确的位置索引（它的左边是比它小的，右边是比它大的）
    def partition(array, low, high):
        pivot, j = array[low], low  # j指向pivot在的位置
        for i in range(low + 1, high + 1):  # i指向待比较元素的位置，从pivot后一位开始，因为pivot在首位
            if array[i] <= pivot:
                j += 1  # 此时j指向pivot应该在的位置
                array[j], array[i] = array[i], array[j]  # 先让待比较的元素交换位置
        array[low], array[j] = array[j], array[low]  # 真实交换pivot到它正确的位置
        return j
    
    
    
    if __name__ == '__main__':
        array = [5, 6, -1, 4, 2, 8, 10, 7, 6]
        start = time.clock()
        quick_sort(array)
        print(array)
        end = time.clock()
        print('用时：', str(end - start))

# 计数排序 #

import time
    
    
    def counting_sort(array):
        if len(array) <= 1:
            return
    
        counts = [0] * (max(array) + 1)
        for num in array:
            counts[num] += 1
    
        # 临时数组，储存排序之后的结果
        array_sorted = []
        for i in range(max(array) + 1):
            array_sorted += [i] * counts[i]
        array[:] = array_sorted
    
    
    if __name__ == '__main__':
        array = [5, 6, 1, 4, 2, 8, 10, 7, 6]
        start = time.clock()
        counting_sort(array)
        print(array)
        end = time.clock()
        print('用时：', str(end - start))

[Github]: https://github.com/yzy1996/Python-Code/tree/master/Algorithm/Optimization-Algorithm