[数据结构与算法]Python四种排序（冒泡排序、快速排序、希尔排序、插入排序）

冒泡排序：

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

'''冒泡排序：重复地走访过要排序的元素列，依次比较两个相邻的元素，
如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元
素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已
经排序完成。'''

快速排序：

快速排序算法通过多次比较和交换来实现排序：

首先设定一个分界值，通过该分界值将数组分成左右两部分。

将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。?

然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。

可以使用递归来实现

def quickSort(data):
    if len(data)>=2: #设置递归的出口
        mid=arr[len(data)//2]#设置中间值
        left,right=[],[]#设置左右两个空列表
        data.remove(mid)#删去中间值
        for num in data:
            if num>=mid:
                right.append(num)
            else:
                left.append(num)
        return quickSort(left)+[mid]+quickSort(right)#递归 并返回中间值
    else:
        return data

s=[5,6,7,8,33,45,2,54,9]
print(quickSort(s))

插入排序

插入排序的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。

通过循环语句可以实现。

def insertionSort(arr):
    for i in range(len(arr)):
        while arr[i-1]>arr[i] and i>=1:
            arr[i-1],arr[i]=arr[i],arr[i-1]
            i-=1
    return arr

希尔排序：

不稳定。

先分组，初始选择增量gap=len(arr)//2，并将他们分组。

如图：增量为三，分为了三组。

?分别比较每一组中的两个数，对它们进行排序。然后依次缩小增量? gap//2。直至gap=1，得到所需值。

def shellSort(arr):
    gap=len(arr)//2
    while gap>0:
        for i in range(gap,len(arr)):
            while i >=gap and arr[i-gap]>arr[i]:
                arr[i-gap],arr[i]=arr[i],arr[i-gap]
                i-=gap
        gap//=2
    return arr