
arr = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]
def bubbleSort(arr):
    for i in range(1,len(arr)):
        for j in range(len(arr)-i):
            if arr[j] > arr[j+1]:
                arr[j],arr[j+1] = arr[j+1],arr[j]
    return arr
print(bubbleSort(arr))

二、选择排序

介绍

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

考点

时间复杂度： O(n²)
空间复杂度： O(1)
稳定性：不稳定
额外内存：不需要

思路

将第一个数设为最小数索引，与后面所有得数进行比较，遇到比它小的数，则将这个数得索引设置为新的最小数索引
将第一个数与最小索引数进行交换，第一个数进入已排序序列，将的新第一个数设为最小数索引
将未排序序列重复1-2过程，完成排序

代码


arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
def selectionSort(arr):
    for i in range(len(arr)-1):
        print(arr)
        minIndex = i
        for j in range(i+1,len(arr)):
            if arr[j] < arr[minIndex]:
                minIndex = j
        if i != minIndex:
            arr[minIndex],arr[i] = arr[i],arr[minIndex]
    return arr
print(selectionSort(arr))

三、插入排序

介绍

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

考点

时间复杂度： O(n) ~ O(n²)
空间复杂度： O(1)
稳定性：稳定
额外内存：不需要

思路

比较第一个数和第二个数，第一个数比第二个数大则交换，前两个数为已排序序列
将未排序序列的第一个数，比已排序序列从最后一个数向前依次比较
将所有已排序序列的比未排序序列的第一个数的数向后移动一位，将未排序序列的第一个数插入到这个空位中，此时未排序序列的第一个数进入已排序序列，如果没有比它小的数，则直接进入已排序序列
将未排序序列重复1-3过程，完成排序

代码


arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
def insertionSort(arr):
    for i in range(len(arr)):
        cur = arr[i]
        pre = i-1
        while pre >= 0 and cur < arr[pre]:
            arr[pre+1] = arr[pre]
            pre -= 1
        arr[pre+1] = cur
        print(i,arr)
    return arr
print(insertionSort(arr))

四、希尔排序

介绍

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本，但希尔排序是非稳定排序算法。出现最坏情况，就会退化为插入排序。

考点

时间复杂度： O(n*log₂n) ~ O(n²)
空间复杂度： O(1)
稳定性：不稳定
额外内存：不需要

思路

将增量gap设置为数组长度的一半，向下取整
设置i = gap（仅第一次），j = i，比较arr[j]与arr[j-gap]，如果arr[j-gap]大，则交换
j = j-gap，比较arr[j]与arr[j-gap]，直到j < 0
i = i+1，重复2~3的过程，直到i = len(arr)-1
增量设置为原来的一半，向下取整，重复2~4到的过程，直到增量为0，排序完成

ps:总的思路就是将数组分为增量为length/2的小部分，使用插入排序对局部数组排序，增量减半

代码


def shell_sort(array):
    length = len(array)
    gap = length // 2
    while gap > 0:
        for i in range(gap, length):# 获取当前gap所有组
            for j in range(i, 0, -gap): #对单个的组进行排序
                if array[j] < array[j - gap]:
                    array[j], array[j - gap] = array[j - gap], array[j]
                else:
                    break
        gap //= 2
    return array
array = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
print(shell_sort(array))

五、归并排序

介绍

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

考点

时间复杂度： O(n*log₂n)
空间复杂度： O(n)
稳定性：稳定
额外内存：需要

思路

按照数组长度取一半分割成左右两个数组，长度为基数的数组则左右两个数组长度相差1
将左右两个数组分别继续按照1的方法分成左右两个数组，直到分割成一个数组只有1个元素
将左右两个数组分别进行遍历，按顺序将小的数加入新的数组，则完成左右两个数组的合并
重复3的过程按照分割相反的处理方式，合并数组，直到合并完所有的数组

代码


arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
def mergeSort(arr):
    import math
    if(len(arr)<2):
        return arr
    middle = math.floor(len(arr)/2)
    left, right = arr[0:middle], arr[middle:]
    return merge(mergeSort(left), mergeSort(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
print(mergeSort(arr))

六、快速排序

介绍

快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。

快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高！

考点

时间复杂度： O(n*log₂n) ~ O(n²)
空间复杂度： O(n*log₂n)
稳定性：不稳定
额外内存：不需要

思路

存储第一个数为基准数temp，最左边的索引为left，最右边的索引为right
从右边开始，找出比left对应的数小的数，没有right就左移，找到后将right对应的数赋值给left对应的数
从左边开始，找出比right对应的数大的值，没有left就右移，找到后将left对应的数赋值给right对应的数
重复2~3的过程，直到left = right，得到mid=left=right，将temp赋值给left对应的数
将原来的数组按照mid为中间点，分割为两个数组
将分割的数组重复1~5的操作，直到无法分割，排序完成

代码


arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
# 快速排序
def partition(arr, left, right):
    tmp = arr[left]
    while left < right:
        while left < right and arr[right] >= tmp:  # 从右边找比tmp小的数
            right -= 1  # 继续从右往左查找
        arr[left] = arr[right]  # 把右边的值写到左边空位上
        while left < right and arr[left] <= tmp:
            left += 1
        arr[right] = arr[left]  # 把左边的值写到右边空位上
    arr[left] = tmp  # 把tmp归位
    return left
def quick_sort(arr, left, right):
    if left < right:  # 至少两个元素
        mid = partition(arr, left, right)
        quick_sort(arr, left, mid - 1)
        quick_sort(arr, mid + 1, right)
quick_sort(arr, 0, 14)
print(arr)

七、堆排序

介绍

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。堆又分为大顶堆和小顶堆，当需要构建递增序列时则需要用到大顶堆，递减序列则为小顶堆

考点

时间复杂度： O(n*log₂n)
空间复杂度： O(1)
稳定性：不稳定
额外内存：不需要

思路

将数组按照顺序，依次放入一个完全二叉树
将完全二叉树调整为大顶堆，即每一个节点的对应的数比它的子节点的数都要大
将根节点的数与最后一个根节点的数交换，将最后一个节点对应的数进入已排序序列，并且删除最后一个节点
重复2~3这个过程，直到删除整个完全二叉树，即得到一个对原数组排序的数组

ps：实际编程中，无需构造二叉树或者堆这种数据结果，也无需构造新的数组，因为完全二叉树所有的节点都可以与数组的索引对应起来。当一个节点的索引为i时，它的左子节点的索引为2i+1，右子节点的索引为2i+2，同时它的父节点的索引应该为ceil(i/2)-1。

代码


def heap_sort(array):
    first = len(array) // 2 - 1
    for start in range(first, -1, -1):
        # 从下到上，从右到左对每个非叶节点进行调整，循环构建成大顶堆
        big_heap(start, len(array) - 1)
    for end in range(len(array) - 1, 0, -1):
        # 交换堆顶和堆尾的数据
        array[0], array[end] = array[end], array[0]
        # 重新调整完全二叉树，构造成大顶堆
        big_heap(0, end - 1)
    return array
def big_heap(start, end):
    # 左孩子的索引
    child = start * 2 + 1
    while child <= end:
        # 节点有右子节点，并且右子节点的值大于左子节点，则将child变为右子节点的索引
        if child + 1 <= end and array[child] < array[child + 1]:
            child += 1
        if array[start] < array[child]:
            # 交换节点与子节点中较大者的值
            array[start], array[child] = array[child], array[start]
            # 交换值后，如果存在孙节点，则将root设置为子节点，继续与孙节点进行比较
            start = child
            child = start * 2 + 1
        else:
            break
array = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
print(heap_sort(array))

八、基数排序

介绍

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

考点

时间复杂度： O(n*k)
空间复杂度： O(n+k)
稳定性：稳定
额外内存：需要

思路

找出数组中最大的数的位数k
构造一个桶结构，包含十个组，编号依次为0到9
按照个位遍历数组，将个位的数字分别放入对应的桶编号中
按照桶的顺序，取出来的数放回数组中
将个位改为十位，重复2~4的过程，一直达到k位，排序完成

代码


def RadixSort(list):
    times = len(str(max(list)))
    for i in range(times):
        bucket = [[] for _ in range(10)]
        for x in list: #对每一位进行排序
            radix =int((x / (10**i)) % 10) #得到每位的基数
            bucket[radix].append(x) #将对应的数组元素加入到相 #应位基数的桶中
        j = 0
        for k in range(10):
            if len(bucket[k]) != 0: #若桶不为空
                for y in bucket[k]: #将该桶中每个元素
                    list[j] = y #放回到数组中
                    j += 1
        print(array)
        i += 1
    return  list
array = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
print(RadixSort(array))

总结

时间复杂度分析

平方阶 O(n^2) ：插入排序、选择排序、冒泡排序
线性对数阶：O(n*log2n) ：快速排序、堆排序、归并排序
线性阶 O(n) ：基数排序

空间复杂度分析

O(1)：冒泡排序、选择排序、插入排序、希尔排序、堆排序
O(n)：归并排序
O(n*log₂n)：快速排序
O(n+k)：基数排序

稳定性分析

稳定：冒泡排序、插入排序、归并排序、基数排序
不稳定：选择排序、快速排序、希尔排序、堆排序

面试考试点睛

希尔排序是基于插入排序而提出改进的，是第一个突破O(n²)的排序算法
冒泡、选择、插入三个最简单粗暴的排序算法，时间复杂度较高
序列较乱，数据量比较大的时候，快速排序都是最快的，在序列比较有序的情况下，快速排序反而比较慢

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/article/detail/55304