python实现常见的排序算法_python 排序

一、冒泡排序

冒泡排序：稳定排序，最差和平均时间复杂度O(n^2)，最优情况是O(n)，即原数组是已排好序的情况，空间复杂度O(1)，即交换操作时使用的临时空间。
思路：比较相邻元素，将较小的放在前面，重复执行，直到所有元素满足正序。 

def bubble_sort(arr):
    n = len(arr)
    for i in range(0, n):  # 表示排序的轮次
        is_swap = False  # 表示是否在该轮次有交换操作
        for j in range(1, n-i):
            if arr[j] < arr[j-1]:
                arr[j], arr[j-1] = arr[j-1], arr[j]
                is_swap = True
        if not is_swap:  # 若是该轮次没有交换操作，说明所有元素已经排好序了
            return arr
    

二、插入排序

插入排序：稳定排序，最差和平均时间复杂度O(n^2)，最优是O(n)，空间复杂度O(1)，
思路：将数组分成已排好序和未排序两部分，初始时，首个元素分到已排序，剩余分到未排序部分，然后遍历未排序元素，将其与已排数元素比较，插入到适当的位置 

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        tmp = arr[i]   # 将当前要比较的未排序元素存到临时变量tmp，方便后移
        j = i - 1
        while j >= 0 and arr[j] > tmp:   # 从后往前遍历已排序元素，若是大于当tmp，就往后移一位，否则，就将tmp插到该元素后面
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = tmp 
    return arr 

三、归并排序

归并排序：稳定排序，最差和平均和最好时间复杂度O(nlogn)，空间复杂度是O(n)，即tmp和左右边界指针的空间

思路：递归方法，先将数组递进地对半分组，直到每组仅剩一个元素时，开始两两之间归并，归并操作是将两个较短的已排序的数组合并为一个较长的排序的数组。

1. 第一种实现：

def merge(arr, left, mid, right):
    """以mid为接线是两个有序数组，归并就是将两个有序数组合并为一个有序数组"""
    tmp = []
    i, j = left, mid+1
    while i <= mid and j <= right:
        if arr[i] <= arr[j]:
            tmp.append(arr[i])
            i += 1
        else:
            tmp.append(arr[j])
            j += 1
    if i <= mid: tmp.extend(arr[i:mid+1])
    if j <= right: tmp.extend(arr[j:right+1])
    arr[left:right+1] = tmp
 
def merge_sort(arr, left, right):
    if left < right:   # 划分的条件
        mid = (left+right) // 2
        merge_sort(arr, left, mid)   # 递归地划分数组
        merge_sort(arr, mid+1, right)
        merge(arr, left, mid, right)  # 划分完成后，开始归并
        
merge_sort(num, 0, len(num)-1)

2. 第二种实现：

def merge(arr, left, mid, right):
    tmp = list(arr[left: right+1])    # 将左右数组均放在临时数组tmp中
    left_start, left_end = left-left, mid-left    # 左数组在tmp中的开始结尾索引
    right_start, right_end = mid+1-left, right-left  # 右数组开始结尾索引
    i, j = left_start, right_start
    for k in range(left, right+1):
        if i > left_end:   # i大于左数组结尾索引说明左边已合并完，故而直接合并右数组
            arr[k] = tmp[j]
            j += 1
        elif j > right_end or tmp[i] <= tmp[j]:  # 右边合并完就合并左数组；两边均未合并完时，哪边小就合入哪边
            arr[k] = tmp[i]
            i += 1
        else:
            arr[k] = tmp[j]
            j += 1
 
def merge_sort(arr, left, right):
    if left >= right:
        return
    mid = (left + right) // 2
    merge_sort(arr, left, mid)
    merge_sort(arr, mid+1, right)
    merge(arr, left, mid, right)

四、快速排序

快速排序: 不稳定排序，最好和平均时间复杂度是O(nlogn)，最差时间复杂度是O(n^2)，即原数组是排好序的情况，空间复杂度是O(logn)。

思路：随机选择一个基准，将小/大与它的元素置于其前/后，由此将数组划分成小于和大于基准的两部分，然后，递归地对子数组执行上述操作。

1、递归 

def partition(arr, low, high):   
    """
    选一个基准，将小/大于它的值分别置于其前/后部分，返回基准最终所在的位置。
    """
    # 随机选择基准，相比直接选第一个或者最后一个为基准,可以避免遇到最坏情况时超时问题
    idx = random.randint(low, high)                   
    arr[low], arr[idx] = arr[idx], arr[low] 
    pivot = arr[low]
 
    # 根据基准值分割数组，小的在前，大的在后
    left, right = low, high
    while low < high:
        while low < high and arr[high] > pivot:
            high -= 1
        arr[low] = arr[high]
        while low < high and arr[low] <= pivot:
            low += 1
        arr[high] = arr[low]
    arr[low] = pivot
    return low
 
def quickSort(arr, low, high): 
    """
    快速排序: 不稳定排序，最好和平均时间复杂度是O(nlogn)，最差时间复杂度是O(n^2)，即原数组是排好序的情况，空间复杂度是O(logn)
    """
    if low < high:
        mid = partition(arr, low, high)  # 先递归分割
        quickSort(arr, low, mid-1)  # 分割完后，开始快排
        quickSort(arr, mid+1, high) 
quickSort(num, 0, len(num)-1) 
# print(num)

2、stack 

def quick_sort(arr):
    n = len(arr)
    left, right = 0, n-1
    stack = [left, right]
    while stack:
        high = rr = stack.pop()
        low = ll = stack.pop()
        if low >= high:
            continue
 
        idx = random.randint(low, high)
        num[low], num[idx] = num[idx], num[low]
        pivot = arr[low]  # 随机选择基准值
 
        while low < high:
            while low < high and arr[high] > pivot:
                high -= 1
            arr[low] = arr[high]
            while low < high and arr[low] <= pivot:
                low += 1
            arr[high] = arr[low]
        arr[low] = pivot
 
        stack.extend([ll, low-1, low+1, rr])

3、用双指针快排

def partition(arr, low, high):   
    """
    选一个基准，将小/大于它的值分别置于其前/后部分，返回基准最终所在的位置。
    """
    # 随机选择基准，相比直接选第一个或者最后一个为基准,可以避免遇到最坏情况时超时问题
    idx = random.randint(low, high)                   
    arr[high], arr[idx] = arr[idx], arr[high] 
    # 根据基准值分割数组，小的在前，大的在后，使用双指针，指针i及之前的是小于基准的，i之后是大于基准的，然后将第i+1位和基准位交换位置，此时i+1位就是基准值。
    pivot = num[high]
    i = low - 1
    for j in range(low, high):
        if num[j] <= pivot:
            i += 1
            num[i], num[j] = num[j], num[i]
    num[i+1], num[high] = num[high], num[i+1]
    return i+1
 
def quickSort(arr, low, high): 
    if low < high:
        mid = partition(arr, low, high)  # 先递归分割
        quickSort(arr, low, mid-1)  # 分割完后，开始快排
        quickSort(arr, mid+1, high) 
quickSort(num, 0, len(num)-1) 
return num

五、选择排序

选择排序：不稳定排序，时间复杂度均为O(n^2),空间复杂度是O(1),适用于小数据。
思路：将数组分成已排好序和未排序两组，遍历未排序数组，从中找出最小值的索引，将其挪到已排好序的数组；或者理解为，每次从未排序数组中找出最小值，将其与未排序首位元素交换，直到未排序数组为空。 

def selection_sort(num):
    n = len(num)
    for i in range(0, n-1):
        minIndex = i
        for j in range(i+1, n):
            if num[j] < num[minIndex]:
                minIndex = j
        num[minIndex], num[i] = num[i], num[minIndex]
    return num

六、堆排序

堆排序：不稳定排序，平均时间复杂度是O(nlogn)，空间复杂度O(1);它是利用堆设计的一种排序算法，堆积是一个近似二叉树的结构，并满足堆积性质，即子节点索引大于（小于）父节点的。

大顶堆：每个节点值大于等于其子节点值，用于堆排序中的升序：key[i]>=key[2i+1]，key[i]>=key[2i+2];

小顶堆：每个节点值小于等于其子节点值，用于堆排序中的降序：key[i]<=key[2i+1]，key[i]<=key[2i+2];

堆是一个完全二叉树，所以，假设某一节点序号为i，则其右节点是2i+1，左节点是2i+2，i从0开始；最后一个非叶子结点的序号是 n//2-1 (若n为偶数，最后一个非叶子结点只有左节点n-1，该非叶子结点是n//2-1；同理，若n为奇数，最后一个非叶子结点为(n-1-2)//2=n//2-1，向下取整)。

思路：1）建堆，初始化待排序数组为大顶堆；2）交换堆顶和最后一个元素；3）除过最后一个元素，对新堆顶元素堆化；4）重复上述步骤，直到堆中只剩一个元素。

def build_heap(arr, i, end):  # 建堆（大顶堆）
    dad = i
    son = 2*dad+1
    while son < end:
        if son+1 < end and arr[son+1] > arr[son]:
            son = son + 1 
        if arr[dad] >= arr[son]:
            return
        arr[dad], arr[son] = arr[son], arr[dad]
        dad = son 
        son = 2*dad+1
 
def heap_sort(arr):
    n = len(arr)
    # 从最后一个非叶子节点开始往上遍历，构建大顶堆，其中最后一个非叶子结点序号为n//2-1
    for i in range(n//2-1, -1, -1): 
        build_heap(arr, i, n)
    for i in range(n-1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        build_heap(arr, 0, i)
heap_sort(num)
# print num

七、希尔排序

希尔排序：不稳定排序，时间复杂度O(n^(1.3~2))，空间复杂度O(1)，是对时间上优化了的插入排序。

思路：1)显示设定一个增量gap，2)然后对相距gap的元素进行插入排序，3)缩小增量；4）重复步骤2、3，直到gap不大于0。

def shell_sort(arr):
    n = len(arr)
    gap = 1 
    while gap < n/3:
        gap = 3 * gap + 1 
    while gap > 0:
        for i in range(gap, n): 
            tmp = arr[i]
            j = i - gap 
            while j >= 0 and arr[j] > tmp:
                arr[j+gap] = arr[j]
                j -= gap 
            arr[j+gap] = tmp 
        gap = gap // 3
    return arr

八、计数排序

计算排序，稳定排序，时间复杂度是O(n+k)，空间复杂度是O(n+k)，n表示原数组长度，k表示原数组的数据范围，该算法不涉及比较操作。

思路：1）获取数组的最小最大值，确定计数范围；2）用一个数组counter存储原数组中元素的计数，counter的索引对应于原数组元素值；3）遍历counter，根据计数值和索引，填充原数组。

1. 非稳定

def counting_sort(arr):
    n = len(arr)
    # 获取数组值范围
    minv= maxv = arr[0]
    for i in range(1, n): 
        if arr[i] < minv: minv = arr[i]
        if arr[i] > maxv: maxv = arr[i]
    # 用新建list存放arr中每个元素出现的次数
    counter = [0] * (maxv-minv+1)
    for i in arr:
        counter[i-minv] += 1
    # 根据计数，填充arr，如果元素k的个数为counter[k-minv]，那么
    k = 0 
    for i in range(0, maxv-minv+1):
        for j in range(counter[i]):
            arr[k] = i + minv
            k += 1
    return arr 

2.  稳定 

def counting_sort(arr):
    # 只计算数组最大值，最小值默认为0，建立计数数组
    m = max(arr)
    counter = [0] * (m+1)
    for a in arr:
        counter[a] += 1
    # 计算累加和，此时counter[i]-1代表的是i元素在排序后的数组存放的最后一个位置（同一元素可能存在多个）
    for i in range(1, m+1):
        counter[i] += counter[i-1]
    # 建立一个与原数组同size的数组res，倒序遍历原数组，将每个元素根据上述所说放入适当的位置
    n = len(arr)
    res = [0] * n
    for i in range(n-1, -1, -1):
        a = arr[i]
        res[counter[a]-1] = a  # counter[i]-1代表的是i元素在排序后的数组存放的最后一个位置（同一元素可能存在多个）
        counter[a] -= 1  # 当放了一个元素后，该元素对应的counter值要减一，对应该元素下次出现时的位置
    # 将排序后的数组放回原数组
    for i in range(n):
        arr[i] = res[i]

九、桶排序

桶排序：其稳定性视使用的桶内排序算法而异，平均时间复杂度O(n+k)，空间复杂度是O(n+k)，其中，n是数组长度，k是桶数。

思路：将数组元素划分到不同值范围的桶中，单个桶中的元素进行排序，然后将各个桶的元素合并。

步骤：1）获取数组最大最小值，确定数组值范围，并且设定一个桶size；2）根据值范围和桶size，计算需要的桶数量；3）将元素放进桶中，对于每个元素v，(v-minv)//桶size 就是其对应的桶索引；4）桶内元素排序；5）将各个桶元素按顺序合并。

        def sort(arr):  # 桶内部排序，数据量小，适合选适用于小数据集的排序算法
            n = len(arr)
            for i in range(1, n):
                j = i - 1
                tmp = arr[i]
                while j >= 0 and arr[j] > tmp:
                    arr[j+1] = arr[j]
                    j -= 1
                arr[j+1] = tmp
    
        def bucket_sort(arr):
            n = len(arr)
            # 获取数组值范围
            minv= maxv = arr[0]
            for i in range(1, n): 
                if arr[i] < minv: minv = arr[i]
                if arr[i] > maxv: maxv = arr[i]
           
            # 构建桶，将arr中元素放到不同的桶中
            bucket_size = 100   # 设定桶大小
            bucket_num = (maxv - minv) // bucket_size + 1   # 获取需要的桶的数量
            bucket = [[] for _ in range(bucket_num)]
            for i in arr:
                idx = (i-minv) // bucket_size
                bucket[idx].append(i)
 
            # 对每个桶中元素排序
            for i in range(bucket_num):
                sort(bucket[i])
 
            # 将桶中元素填充回arr
            k = 0 
            for tmp in bucket:
                for i in tmp:
                    arr[k] = i 
                    k += 1
            return arr 
        bucket_sort(num)
        return num

十、基数排序

基数排序：稳定排序，时间复杂度是0(d(n+k))，空间复杂度是O(n+k)，其中n是数组长度，k是值范围长度，d是最大位数，相当于进行了d次计数排序。

思路：1）获取数组最大值，确定数值最大位数；2）从低位到高位，对数组各个元素的相同位进行桶size为1的桶排序（即计数排序）。

def digit(num, exp):
    # 获取数字的第k位，其中exp=10**(k-1)
    return (num // exp) % 10
 
def counting_sort_digit(nums, n, exp):
    # 根据数组每一元素的第k位计数排序
    counter = [0] * 10
    for num in nums:
        d = digit(num, exp)
        counter[d] += 1
    for i in range(1, 10):
        counter[i] += counter[i-1]
    res = [0] * n
    for i in range(n-1, -1, -1):
        d = digit(nums[i], exp)
        res[counter[d]-1] = nums[i]
        counter[d] -= 1
    for i in range(n):
        nums[i] = res[i]
 
def radix_sort(nums):
    # 从低位到高位，对数组每一元素计数排序
    n = len(nums)
    m = max(nums)
    exp = 1  # 10**(1-1)
    while exp <= m:
        counting_sort_digit(nums, n, exp)
        exp *= 10