插入排序与希尔排序

基础算法复习:插入排序与希尔排序。

插入排序

基本思路

  插入排序(Insertion-Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

  操作步骤:

  1. 将第一待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列。
  2. 从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面)。

  示例,动图演示:

16-1

Python 实现
1
2
3
4
5
6
7
8
9
def insertion_sort(nums):
for i in range(len(nums)):
tmp = nums[i]
index = i
while index > 0 and nums[index-1] > tmp:
nums[index] = nums[index-1]
index -= 1
nums[index] = tmp
print(nums)
时间复杂度
  • 平均时间复杂度:O(n**2)。
  • 最优时间复杂度:O(n)。
  • 最坏时间复杂度:O(n**2)。
  • 空间复杂度:O(1)。
  • 稳定性:稳定。

希尔排序

基本思路

  递减增量排序算法,对插入排序的改进,实质是分组插入排序,又叫缩小增量排序希尔排序提升排序的奥秘就在于数据元素越有序,使用插入排序效率越高

  操作步骤:

  1. 先将待排数列分割成若干子序列(增量为m)。
  2. 对每个子序列使用插入排序
  3. 减小增量,再排序。
  4. 对全体元素做一次插入排序

  示例,动图演示:

16-2

Python 实现
1
2
3
4
5
6
7
8
9
10
def shell_sort(nums):
step = len(nums) // 2
while step:
for i in range(step, len(nums)):
print(i)
while i >= step and nums[i - step] > nums[i]: # 子序列执行插入排序
nums[i], nums[i - step] = nums[i - step], nums[i]
i -= step
step = step // 2
return nums
时间复杂度
  • 最优时间复杂度:O(nlogn)。
  • 最坏时间复杂度:O(nlogn)。
  • 平均时间复杂度:O(nlogn)。
  • 空间复杂度:O(1)。
  • 稳定性:不稳定。
坚持原创技术分享,您的支持将鼓励我继续创作!