排序算法大集合上

1. 插入排序

  1. 时间复杂度:最好是n-1,最坏是n(n-1)/2,平均为O(n^2)。
  2. 空间复杂度: O(1)
  3. 多作为快排的补充,适用于少量的数据排序。
  4. 该算法是稳定的,依赖初始排序顺序。

过程:

  1. 以第一个数为已经排好的队列,将第二个数从队列的右向左比较。
  2. 如果比它大,那么,该队列里的元素就往右边移动一位,接着比较该元素左边的元素;比它小,那么,就把他存入该队列里的元素的右边一位。
  3. 形成一个新的队列,再走1,2。
    更多
# 插入排序
def insert(nums):
    for i in range(1, len(nums)):
        temp = nums[i]
        # 是否找到一个合适的位置插入
        label = False
        for j in range(i-1,-1,-1):
            # 找到位置了,插入
            if nums[j] < temp:
                nums[j+1] = temp
                label = True
                break
            else:
                # 右移一位
                nums[j+1] = nums[j]
                
        if not label:
            nums[0] = temp

nums = [2,3,4,5,1,9,3,0,2,1]
insert(nums)
print(nums)

感觉上面这个方法有些复杂了,改进了一下:

def insert(nums):
    for i in range(1, len(nums)):
        j = i
        while j > 0:
            if nums[j] < nums[j - 1]:
                nums[j], nums[j - 1] = nums[j - 1], nums[j]
                j -= 1
            else:
                break

2. 二分插入排序

  1. 时间复杂度:最好情况下:O(nlogn);最坏情况下:O(n^2)
    分析:最外层有n次循环;最内侧分为两个部分,一个是二叉搜索(logn),一个是for循环(n);所以,最好的情况是元素所在的位置就是插入位置(nlogn);最坏情况和平均的情况就是不断在查找,即为:n(logn+n)->n^2。
  2. 空间复杂度维O(1)。
  3. 是稳定的, 依赖初始排序顺序。

过程:

  1. 在插入第i个元素时,对前面的0~i-1元素进行折半,
  2. 先跟他们中间的那个元素比,如果小,则对前半再进行折半。
  3. 否则对后半进行折半。回归2
  4. 直到left(左边缘)>right(右边缘),再把第i个元素前1位与目标位置之间的所有元素后移。
  5. 最后,把第i个元素放在目标位置上。
def insert_2_sort(nums):
    for i in range(1, len(nums)):
        left = 0
        right = i - 1
        key = nums[i]

        while left <= right:
            middle = (left+right)//2
            if key > nums[middle]:
                left = middle + 1
            else:
                right = middle - 1

        for j in range(i, left, -1):
            nums[j] = nums[j-1]

        nums[left] = key

a = [2,3,4,5,1,9,7,6,2,0,6]
insert_2_sort(a)

3. 希尔排序

  1. 空间复杂度为O(1)
  2. 时间复杂度则由增量(步长)而定。
    只要最终步长为1任何步长序列都可以工作。
    一个好的步长序列评价时间复杂度可以达到O(n^1.5)
  3. shell排序是非稳定排序
  4. 提高效率的思想:
    因为插入排序的时间复杂度依赖初始序列的顺序,所以通过大步长的排序(时间复杂度低),使序列部分有序,这样当进行小步长排序时,时间复杂度也低。

过程

  1. 把记录按下标的一定增量分组
  2. 对每组使用直接插入排序算法排序。
  3. 减小增量n,若n > 0,进入1;反之,算法终止
def shell(nums):
    gaps = 3
    for gap in range(1, gaps+1):
        for i in range(gap, len(nums)):
            key = nums[i]
            pointer = i - gap
            while key < nums[pointer] and pointer >= 0:
                nums[pointer+gap] = nums[pointer]
                pointer -= gap

            nums[pointer+gap] = key

4. 选择排序

  1. 空间复杂度为O(1)
  2. 时间复杂度为O(n^2)
  3. 对比冒泡排序,它少了很多的交换步骤。
  4. 不稳定的排序方式

过程:

  1. 从待排序的数据元素中选出最小(或最大)的一个元素。
  2. 存放在序列的起始位置,直到全部待排序的数据元素排完。
    类似冒泡排序。
def selection_sort(nums):
    for i in range(0, len(nums)):
        lowest = i
        for j in range(i, len(nums)):
            if nums[j] < nums[lowest]:
                lowest = j
        nums[lowest], nums[i] = nums[i], nums[lowest]

5. 冒泡排序

  1. 时间复杂度为O(n^2)
  2. 空间复杂度为O(1)
  3. 稳定的排序方法
  4. 优化:
    如果一个forloop没有发生一次交换,说明已经排好了,可以停止了后面的循环了。
    在一次loop中记录最后一次交换的位置,那么该位置后面数一定都是排好了的。所以这一部分就不用参与下面的比较了。

过程:

  1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
  2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
  3. 针对所有的元素重复以上的步骤,除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较
    ------百度百科
def bubble_sort(nums):
    for i in range(1, len(nums)):
        for j in range(0, len(nums)-i):
            if nums[j+1] < nums[j]:
                nums[j+1], nums[j] = nums[j], nums[j+1]

a = [9,3,2,7,1,8,0,4,10,6]
bubble_sort(a)
print(a)

6. 鸡尾酒排序/双向冒泡排序

  1. 空间复杂度为:O(1)
  2. 平均和最差的时间复杂度为O(n^2),但如果序列在一开始已经大部分排序过的话,趋近于O(n)。
    原因:双向排序可以避免大量小的数在最右边而小数移动缓慢的情况(升序)

过程:

  1. 传统冒泡气泡排序的双向进行,先让气泡排序由左向右进行
  2. 再来让气泡排序由右往左进行,如此完成一次排序的动作
  3. 使用left与right两个旗标来记录左右两端已排序的元素位置:
    当left = right时:结束
    否则:继续1
def bubble_sort(nums):
    left = 1
    right = len(nums)
    while left < right:
        for i in range(0, len(nums)-left):
            if nums[i+1] < nums[i]:
                nums[i+1], nums[i] = nums[i], nums[i+1]
        left += 1
        for j in range(len(nums)-1, len(nums)-right, -1):
            if nums[j] < nums[j-1]:
                nums[j], nums[j-1] = nums[j-1], nums[j]
        right -= 1

你可能感兴趣的