做美女图片网站犯法吗杭州seo代理公司

各类排序算法时空复杂度、稳定性对比

序号	排序算法	平均时间复杂度	最坏时间复杂度	空间复杂度	是否稳定
1	插入排序	O(n2)	O(n2)	O(1)	是
2	冒泡排序	O(n2)	O(n2)	O(1)	是
3	选择排序	O(n2)	O(n2)	O(1)	不是
4	希尔排序	O(nlogn)	O(ns)	O(1)	不是
5	归并排序	O(nlogn)	O(nlogn)	O(n)	是
6	快速排序	O(nlogn)	O(n2)	O(logn)	不是
7	堆排序	O(nlogn)	-	O(1)	不是

1. 插入排序

原理：不断选择数字，插入到部分已经排好序的数组中。

• 时间复杂度最好的情况是已经排好序
• 时间复杂度最好$O(n)$，平均$O(n^2)$，最坏$O(n^2)$
• 空间复杂度$O(1)$

1.1 直接插入排序

# 直接插入排序
def insert_sort(nums):for i in range(1, len(nums)):cur_num = nums[i]j = i# 对已经排好的数字，从后往前，边挪边比较while j - 1 >= 0 and nums[j - 1] > cur_num:nums[j] = nums[j - 1]j -= 1nums[j] = cur_numreturn nums

1.2 折半插入排序

和直接插入排序方法类似，不过是以折半查找方式来寻找插入位置

# 折半插入排序
def half_insert_sort(nums):for i in range(1, len(nums)):cur_num = nums[i]# 折半查找，找到要插入位置(left)left, right = 0, i - 1while left <= right:mid = int((left + right) / 2)if nums[mid] > cur_num:right = mid - 1else:left = mid + 1for j in range(i, left, -1):  # 挪nums[j] = nums[j - 1]nums[left] = cur_numreturn nums

2. 冒泡排序

原理：将大的数字往后冒(交换相邻两个数字的位置)。

• 时间复杂度最好的情况是已经排好序
• 时间复杂度最好$O(n)$，平均$O(n^2)$，最坏$O(n^2)$
• 空间复杂度$O(1)$

def bubble_sort(nums):# 大的往后冒for i in range(len(nums), 0, -1):  # 最后一个不用管for j in range(i - 1):# 将大的交换到后面去if nums[j] > nums[j + 1]:nums[j], nums[j + 1] = nums[j + 1], nums[j]return nums

3. 选择排序

原理：每趟从剩余数字中找到最小的数字，放到指定位置。

• 时间复杂度最好的情况是已经排好序
• 时间复杂度最好$O(n)$，平均$O(n^2)$，最坏$O(n^2)$
• 空间复杂度$O(1)$

def select_sort(nums):"""每次把剩余最小的放在前面"""for i in range(len(nums)):min_index = i# 找剩余最小的下标for j in range(i, len(nums)):if nums[j] < nums[min_index]:min_index = j# 交换temp = nums[i]nums[i] = nums[min_index]nums[min_index] = tempreturn nums

4. 希尔排序

原理：间隔步长step的数字归为一组，组内进行插入排序，step由大变小，直到最后一趟步长为1，排序完成。

• 当增量序列为$K=2^x$时，时间复杂度为$O(n^2)$
• 当增量序列为$K=(3\ast x+1)$时，时间复杂度为$O(n^3/2)$
• 空间复杂度为$O(1)$

def shell_sort(nums):"""间隔步长step的数字为一组，组内进行插入排序，step由大到小"""length = len(nums)step = int(length / 2)while step > 0:for i in range(step, length):# 每组内部采用插入排序j = itemp = nums[i]while j - step >= 0 and nums[j - step] > temp:nums[j] = nums[j - step]j -= stepnums[j] = tempstep = int(step / 2)return nums

5. 归并排序

原理：对于给定的一组记录，利用递归与分治技术将数据序列划分成为越来越小的半子表，在对半子表排序，最后再用递归方法将排好序的半子表合并成为越来越大的有序序列

• 时间复杂度最优、平均和最差都是$O(nlogn)$
• 空间复杂度为:$O(n)$

例子

# 合并左右两个子数组
def merge(arr, left, mid, right):"""相当于有两个递增的子数组，合并成一个递增的数组"""n1 = mid - left + 1n2 = right - mid# 创建临时数组L = [0] * (n1)R = [0] * (n2)# 将左右子数组拷贝数据到临时数组 L[] 和 R[]for i in range(0, n1):L[i] = arr[left + i]for j in range(0, n2):R[j] = arr[mid + 1 + j]# 归并临时数组到 arr[l..r]i = 0  # 初始化第一个子数组的索引j = 0  # 初始化第二个子数组的索引k = left  # 初始归并子数组的索引while i < n1 and j < n2:if L[i] <= R[j]:arr[k] = L[i]i += 1else:arr[k] = R[j]j += 1k += 1# 拷贝 L[] 的保留元素while i < n1:arr[k] = L[i]i += 1k += 1# 拷贝 R[] 的保留元素while j < n2:arr[k] = R[j]j += 1k += 1# 递归归并排序
def merge_sort(nums, left, right):""""""if left < right:mid = int((left + (right - 1)) / 2)merge_sort(nums, left, mid)merge_sort(nums, mid + 1, right)merge(nums, left, mid, right)

6. 快速排序

原理：每一趟将第一个数字作为基准，先从后往前遍历，比基准大的放到前面，比基准小的放到后面。

• 最优情况是每次划分正好平分数组
• 最差情况是每次划分落到最边缘，退化为冒泡排序
• 时间复杂度最优$O(nlogn)$，平均$O(nlogn)$，最坏$O(n^2)$
• 空间复杂度最优$O(logn)$，平均$O(logn)$，最差$O(n)$

例子：

def quick_sort(nums, low, high):"""最优情况是每次划分正好平分数组，最差情况是每次划分落到最边缘，退化为冒泡排序"""if low >= high:returni, j = low, highpivot = nums[low]  # 以第一个元素作为基准while i < j:while i < j and nums[j] > pivot:j -= 1nums[i] = nums[j]while i < j and nums[i] <= pivot:i += 1nums[j] = nums[i]nums[i] = pivotquick_sort(nums, low, i - 1)  # 对低位进行递归快排quick_sort(nums, i + 1, high)  # 对高位进行递归快排

7. 堆排序

原理：堆看成是二叉树结构，大顶堆要求父节点元素要大于等于其子节点。那么每次弹出大顶堆的根节点，就能从大到小进行排序。

• 时间复杂度$O(nlogn)$
  • 初始化堆：$O(n)$
  • 更改堆元素后重建堆时间：$O(nlogn)$
• 空间复杂度$O(1)$

例子

def heapify(nums, n, i):largest = i  # 最大值下标暂时记录为 ileft = 2 * i + 1right = 2 * i + 2if left < n and nums[largest] < nums[left]:largest = leftif right < n and nums[largest] < nums[right]:largest = rightif i != largest:nums[i], nums[largest] = nums[largest], nums[i]# 子结点递归交换heapify(nums, n, largest)def heap_sort(nums):n = len(nums)# 构造大顶堆for i in range(n - 1, -1, -1):heapify(nums, n, i)# 从堆顶一个一个弹出for j in range(n - 1, -1, -1):nums[0], nums[j] = nums[j], nums[0]heapify(nums, j, 0)

完整测试代码

# !usr/bin/env python
# -*- coding: utf-8 -*-
"""
@Author: ywm_up
@File: sort_methods.py
@Time: 2021/8/15 10:55
"""# 1. 插入排序
def insert_sort(nums):for i in range(1, len(nums)):cur_num = nums[i]j = i# 对已经拍好的数字，从后往前，边挪边比较while j - 1 >= 0 and nums[j - 1] > cur_num:nums[j] = nums[j - 1]j -= 1nums[j] = cur_numreturn nums# 2. 折半插入排序
def half_insert_sort(nums):# 和插入排序方法类似，不过是以折半查找方式来寻找插入位置for i in range(1, len(nums)):cur_num = nums[i]# 折半查找，找到要插入位置(left)left, right = 0, i - 1while left <= right:mid = int((left + right) / 2)if nums[mid] > cur_num:right = mid - 1else:left = mid + 1for j in range(i, left, -1):  # 挪nums[j] = nums[j - 1]nums[left] = cur_numreturn nums# 3. 冒泡排序
def bubble_sort(nums):# 大的往后冒for i in range(len(nums), 0, -1):  # 最后一个不用管for j in range(i - 1):# 将大的交换到后面去if nums[j] > nums[j + 1]:temp = nums[j]nums[j] = nums[j + 1]nums[j + 1] = tempreturn nums# 4. 选择排序
def select_sort(nums):"""每次把剩余最小的放在前面"""for i in range(len(nums)):min_index = i# 找剩余最小的下标for j in range(i, len(nums)):if nums[j] < nums[min_index]:min_index = j# 交换temp = nums[i]nums[i] = nums[min_index]nums[min_index] = tempreturn nums# 5. 希尔排序
def shell_sort(nums):"""间隔步长step的数字为一组，组内进行插入排序，step由大到小"""length = len(nums)step = int(length / 2)while step > 0:for i in range(step, length):# 每组内部采用插入排序j = itemp = nums[i]while j - step >= 0 and nums[j - step] > temp:nums[j] = nums[j - step]j -= stepnums[j] = tempstep = int(step / 2)return nums# 6. 归并排序
# 合并左右两个子数组
def merge(arr, left, mid, right):"""相当于有两个递增的子数组，合并成一个递增的数组"""n1 = mid - left + 1n2 = right - mid# 创建临时数组L = [0] * (n1)R = [0] * (n2)# 将左右子数组拷贝数据到临时数组 L[] 和 R[]for i in range(0, n1):L[i] = arr[left + i]for j in range(0, n2):R[j] = arr[mid + 1 + j]# 归并临时数组到 arr[l..r]i = 0  # 初始化第一个子数组的索引j = 0  # 初始化第二个子数组的索引k = left  # 初始归并子数组的索引while i < n1 and j < n2:if L[i] <= R[j]:arr[k] = L[i]i += 1else:arr[k] = R[j]j += 1k += 1# 拷贝 L[] 的保留元素while i < n1:arr[k] = L[i]i += 1k += 1# 拷贝 R[] 的保留元素while j < n2:arr[k] = R[j]j += 1k += 1# 递归归并排序
def merge_sort(nums, left, right):""""""if left < right:mid = int((left + (right - 1)) / 2)merge_sort(nums, left, mid)merge_sort(nums, mid + 1, right)merge(nums, left, mid, right)# 7. 快速排序
def quick_sort(nums, low, high):"""最优情况是每次划分正好平分数组，最差情况是每次划分落到最边缘，退化为冒泡排序"""if low >= high:returni, j = low, highpivot = nums[low]  # 以第一个元素作为基准while i < j:while i < j and nums[j] > pivot:j -= 1nums[i] = nums[j]while i < j and nums[i] <= pivot:i += 1nums[j] = nums[i]nums[i] = pivotquick_sort(nums, low, i - 1)  # 对低位进行递归快排quick_sort(nums, i + 1, high)  # 对高位进行递归快排# 8. 堆排序
def heapify(nums, n, i):largest = i  # 最大值下标暂时记录为 ileft = 2 * i + 1right = 2 * i + 2if left < n and nums[largest] < nums[left]:largest = leftif right < n and nums[largest] < nums[right]:largest = rightif i != largest:nums[i], nums[largest] = nums[largest], nums[i]# 子结点递归交换heapify(nums, n, largest)def heap_sort(nums):n = len(nums)# 构造大顶堆for i in range(n - 1, -1, -1):heapify(nums, n, i)# 从堆顶一个一个弹出for j in range(n - 1, -1, -1):nums[0], nums[j] = nums[j], nums[0]heapify(nums, j, 0)def mytest():# 以下排序都只实现了递增print("1. 插入排序")nums = [2, 3, 0, 1, 5, 4]print(insert_sort(nums))print("2. 折半插入排序")nums = [2, 3, 0, 1, 5, 4]print(half_insert_sort(nums))print("3. 冒泡排序")nums = [2, 3, 0, 1, 5, 4]print(bubble_sort(nums))print("4. 选择排序")nums = [2, 3, 0, 1, 5, 4]print(select_sort(nums))print("5. 希尔排序")nums = [2, 3, 0, 1, 5, 4]print(shell_sort(nums))print("6. 归并排序")nums = [2, 3, 0, 1, 5, 4]merge_sort(nums, 0, len(nums) - 1)print(nums)print("7. 快速排序")nums = [2, 3, 0, 1, 5, 4]quick_sort(nums, 0, len(nums) - 1)print(nums)print("8. 堆排序")nums = [2, 3, 0, 1, 5, 4]heap_sort(nums)print(nums)if __name__ == '__main__':mytest()