python实现常见的排序方法

「爱情、让人受尽委屈。」 2023-06-12 11:25 3阅读 0赞

冒泡排序

循环遍历，一次比较两个元素，如果他们循序错误就把他们交换过来，重复进行，直到没有再需要交换的。

# 实现代码
    def maopao_sort(target_list):
        for item in range(len(target_list) - 1):
            for i in range(len(target_list) - item -1):
                if target_list[i] > target_list[i+1]:
                    target_list[i],target_list[i+1] = target_list[i+1],target_list[i]
        return target_list

选择排序

假设第一个元素最小，然后与后面元素比较，如果后面的比第一个元素小，就将他们换一个位置，并且标记这个为最小元素，继续与后面比较，直到找到最小元素，这时候最小元素就在第一个，以此类推找到第二小的排在第二个位置，直到最后。

# 实现代码
    def select_sort(target_list):
        for item in range(len(target_list) - 1):
            min_element = item
            for i in range(item + 1, len(target_list)):
                if target_list[i] < target_list[min_element]:
                    min_element = i
                if item != min_element:
                    target_list[i],target_list[min_element] = target_list[min_element],target_list[i]
        return target_list

快速排序

挑出第一个元素作为基准，拿数组最后一个元素与这个数比较，如果比它大，则最后一个数不动，再拿倒数第二个数与它比较，如果比这个数小，则将倒数第二个数放到挑出这个数的索引处，这时候倒数第二个位置空出来了，然后拿前面第二个数与这个数比较，如果比它小则不动，拿第三个数与这个数比较，如果比它大，则将第三个数放到倒数第二个空位置处，以此类推，直到这个数前面的数都比它小，后面的数都比它大，然后利用递归，把小于基准元素的子数列和大于基准元素的子数列排序。

# 实现代码
    def sub_sort(low,high,target_list):
        key = target_list[low]
        while low < high:
            while low < high and target_list[high] >= key:
                high -= 1
            target_list[low] = target_list[high]
            while low < high and target_list[low] < key:
                low += 1
            target_list[high] = target_list[low]
        target_list[low] = key
        return low
    def quick_sort(low,high,target_list):
        if low <= high:
            key = sub_sort(low,high,target_list)
            quick_sort(low,key-1,target_list)
            quick_sort(key+1,high,target_list)
        return target_list

归并排序

两个有序列表，依次比较，新开一个空列表，哪一个小将哪一个元素添加到空列表里，如何实现两个有序列表？利用递归不断平分分解，直到只有两个元素，两个元素就好比两个有序数组，然后合并，如下图。

# 实现代码
    def merge(low, mid, high, target_list):
        i = low
        j = mid + 1
        tmp = []
        while i <= mid and j <= high:
            if target_list[i] < target_list[j]:
                tmp.append(target_list[i])
                i += 1
            else:
                tmp.append(target_list[j])
                j += 1
        while i <= mid:
            tmp.append(target_list[i])
            i += 1
        while j <= high:
            tmp.append(target_list[j])
            j += 1
        target_list[low:high + 1] = tmp
    def merge_sort(low, high, target_list):
        if low < high:
            mid = (low + high) // 2
            merge_sort(low, mid, target_list)
            merge_sort(mid + 1, high, target_list)
            merge(low, mid, high, target_list)
        return target_list