python实现几种常见的排序算法

以下排序算法均按照从小到大排序N个元素：

'''
1、冒泡排序
基本思想：
遍历元素列表，比较相邻的元素，如果第一个比第二个大，则交换其位置，经过第一轮比较，最大的元素将恰好被放置到最后一个；
第二轮不再比较最后的元素，只比较前面的N-1个元素，则经过第二轮比较之后，我们可以确定第二大的元素；
依次类推，第i轮比较能够确定第i大的元素，可知经过N-1轮比较后我们能够确定所有元素的位置（为什么不是N轮比较?——因为前N-1个大的元素确定了，还剩最后一个，自然就是最小的，无需再比较）
'''


def bubble_sort(nums):
    if nums is not None:  # 注意判空,不要用=或者!=判空
        for i in range(1, len(nums)):  # 一共进行1到N-1轮比较，N即列表长度len(nums)
            is_sorted = True  # 用来判断是否已经排好序
            for j in range(len(nums) - i):  # 第i轮比较中需要比较第0,1,…,(N-i-1)个元素与其后面一个位置上的元素的大小
                if nums[j] > nums[j + 1]:
                    is_sorted = False  # 如果没有发生交换，则说明已经排好序，无需进行下一轮比较
                    nums[j], nums[j + 1] = nums[j + 1], nums[j]

            if is_sorted:
                break
    return nums


'''
2、选择排序
基本思想：
遍历元素，记录下最小的元素所在的位置，然后把最小的元素和位置0上的元素互换；
一共进行N-1轮遍历：
第一轮确定第1小的元素，放在位置0；
第二轮确定第2小的元素，放在位置1；x
…
第i轮确定第i小的元素，放在位置i；
N-1轮遍历之后可以确定所有元素的正确位置。
'''


def select_sort(nums):
    if nums is not None:  # 注意判空

        for i in range(0, len(nums) - 1):  # 一共进行0到N-2共N-1轮选择，N即列表长度len(nums)
            min_index = i  # 先初始化每轮选择中最小的元素的位置为每轮遍历的第一个元素
            for j in range(i + 1, len(nums)):  # 从第一个元素的下一个位置开始与记录的最小元素做比较
                if nums[j] < nums[min_index]:
                    min_index = j

            if i != min_index:
                nums[i], nums[min_index] = nums[min_index], nums[i]


'''
3、快速排序
基本思想：采用分而治之的思想，选取nums中的一个数作为基准点，把要排序的数据分成两部分，一部分比基准点小，一部分比基准点大；
然后再对这两部分数据分别采用分而治之的方法进行排序；
最后再把这几部分数据连接到一起。
'''


def quick_sort(nums):

    if len(nums) <= 1:
        return nums

    pivot = nums[len(nums) // 2]
    left = [x for x in nums if x < pivot]
    middle = [x for x in nums if x == pivot]
    right = [x for x in nums if x > pivot]

    return quick_sort(left) + middle + quick_sort(right)


'''
4、插入排序
基本思想：插入排序的原理类似于打扑克牌，把待排序数据分成两部分，一部分是已排好序的有序数据，一部分是乱序数据，
开始时默认第一个数有序，然后再将后面的数逐个插入，插入操作具体包括：
1、与有序数据比较，确定插入位置，
2、在每次比较中将比待插入数据大的数据后移，给待插入数据腾位置
'''


def insert_sort(nums):
    for i in range(len(nums)):
        preIndex = i-1  # 0到i-1的数据为已经排好序的有序数据
        curnum = nums[i]  # 记录下一个要插入到有序数据中的数

        # 遍历有序数据，找到curnum应插入的位置
        while preIndex >= 0 and nums[preIndex] > curnum:  # 注意不要漏掉preIndex等于0
            nums[preIndex+1] = nums[preIndex]  # 比curnum大的数往后挪
            preIndex -= 1

        nums[preIndex+1] = curnum

    return nums


l = [-1, 5, 3, 8, 1, -8]
insert_sort(l)
print(l)

'''
5、希尔排序
基本思想：希尔排序是直接插入排序的升级版，减少插入排序的移动次数
插入排序在每次插入一个数据的过程中，凑要大量移动数据，

希尔排序将序列按固定间隔划分为多个子序列，在子序列中简单插入排序，先做远距离移动使序列基本有序；
逐渐缩小间隔重复操作，最后间隔为1时即简单插入排序。
'''


def shell_insert(nums, d):
    n = len(nums)
    for i in range(d, n):
        j = i - d
        temp = nums[i]  # 记录要插入的数
        while j >= 0 and nums[j] > temp:  # 从后向前，找到比其小的数的位置
            nums[j + d] = nums[j]  # 向后挪动
            j -= d
        if j != i - d:
            nums[j + d] = temp


def shell_sort(nums):

    n = len(nums)
    if n <= 1:
        return nums
    d = n//2
    while d >= 1:
        shell_insert(nums, d)
        d = d//2
    return nums


'''
6、归并排序
基本思想：归并排序运用分治递归思想：将大问题分为较小的子问题，分而治之；递归调用同样的方法解决子问题。
最终将序列的排序问题分治为一个数的排序问题，关键在于如何将子问题答案合并为问题答案。

两个有序序列合并为一个有序序列，借助一个暂存数组（列表），两个序列元素依次比较填入暂存列表，形成一个有序序列。
归并排序划分子问题采用二分法，共需O(logn)次划分，当然需要相当次合并；每次合并遍历比较O(n)。时间复杂度O(nlogn)。

'''


def merge_sort(nums):
    import math
    if len(nums) < 2:
        return nums
    middle = math.floor(len(nums)/2)
    left, right = nums[0:middle], nums[middle:]
    return merge(merge_sort(left), merge_sort(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

参考：
https://blog.csdn.net/aiya_aiya_/article/details/79846380#1.%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F
https://www.cnblogs.com/wuxinyan/p/8615127.html