• 0

  • 475

常用排序算法总结

perpetual

python交流

2星期前

参考

1 几种简单的排序

冒泡

  • 时间复杂度: O(n2)
  • 空间复杂度: O(1)
  • 稳定性:稳定。同样的值,左边不可能被移动到右边。
  • 特点:因为冒泡排序必须要在最终位置找到之前不断交换数据项,所以它经常被认为是最低效的排序方法。但它可以在发现列表已排好时立刻结束,因此如果列表只需要几次遍历就可排好,冒泡排序就占有优势。
class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        while True:
            re = False
            for i in range(len(nums)-1):
                if nums[i] > nums[i+1]:
                    nums[i], nums[i+1] = nums[i+1], nums[i]
                    re = True
            if not re:
                break
        return nums
复制代码

选择

  • 时间复杂度: O(n2)
  • 空间复杂度: O(1)
  • 稳定性:稳定。同样的值,靠左的先被选择。

选择排序提高了冒泡排序的性能,它每遍历一次列表只交换一次数据,一次到位。不过由于每次遍历只关注“最小值”,不能像冒泡排序一样及时发现列表已经排好。

插入

  • 时间复杂度:O(n2)
  • 空间复杂度:O(1)
  • 稳定性:如果将后处理的值排到后边则有序(子表从后向前扫描)。
  • 特点:总是保持一个位置靠前的 已排好的子表,然后每一个新的数据项被 “插入” 到前边的子表里,排好的子表增加一项。
做法1:定位+列表拼接:注意边界条件!
class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        for i in range(1, len(nums)):   # 未排序序列
            target = nums[i]
            for j in range(i-1, -1, -1): 
            # 从后往前扫,找到比自己小的就插入在它后面
                if nums[j] <= target:
                    nums[j+1:i+1] = [target] + nums[j+1:i]
                    break
            else: # 如果一直没有找到比自己小的,插入头部
                nums[0:i+1] = [target] + nums[0:i]
        return nums
复制代码

拼接list这种操作也就在python里写的比较简单,而且还要考虑如果一直没有找到比自己小的,插入头部的情况。看来这种做法有待改进呀。

更好的做法2:反向冒泡
def insertionSort(alist):
    for i in range(1,len(alist)):
        currentvalue=alist[i]
        position=i
        # 相当于只针对currentvalue一个值的从右向左冒泡。
        # 区别在于,放到合适位置后不走完全程,因为该位置的左边已经有序
        while alist[position-1]>currentvalue and position>0:
            alist[position]=alist[position-1]
            position=position-1
        alist[position]=currentvalue
    return alist
复制代码

这种反向冒泡的优势在于,如果数组本来有序,只需要 O(n) 一次扫描即可!

2 分治思想

快排

  • 时间复杂度:O(nlogn).最差情况下 O(n2)
  • 空间复杂度:O(log n) 注意这是栈空间的层数。而非复制了这么多份数组。
  • 稳定性:不稳定。大跨度交换很不靠谱。
  • 特点:当数列近乎有序时,退化为O(n2)的算法。

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def work(left, right):  # 左开右闭
            if right - left <= 1: 
                return nums
            pivot = left
            c1 = pivot+1  # 下一个可以放置较小数字的位置
            for c2 in range(pivot+1, right):
                if nums[c2] < nums[pivot]:
                    nums[c1], nums[c2] = nums[c2], nums[c1]
                    c1 += 1
            nums[pivot], nums[c1-1] = nums[c1-1], nums[pivot]
            work(left,c1-1)
            work(c1,right)
        
        work(0, len(nums))  # python list 的下标切片是可以超过长度的哦~
        return nums
复制代码

这个代码是单路快排。 除此以外还有:

  • 双路快排(一个往左一个往右)
  • 三路快排(荷兰国旗问题)

归并

  • 时间复杂度:O(nlogn)
  • 空间复杂度:O(n) 需要O(n)的额外空间来临时存放归并结果。归并如果用递归做,也有O(log n)在栈上的的空间复杂度。但O(log n)< O(n)忽略不计。
  • 稳定性:不稳定。举个例子就行了。
    • [3左,3左,3左,3左] + [3左,3左,3左,3左]
    • [3左,3右,3左,3右,3左,3右,3左,3右]

递归肯定是好写的,所以这里复制粘贴一份自底向上的方法叭~

# 自底向上的归并算法
def mergeBU(alist):
    n = len(alist)
    size = 1
    while size <= n:
        for i in range(0, n-size, size+size):	
        # 这样每个归并块一定有两个小块。不够的话说明已经排好序不用管了~
       	    merge(alist, i, i+size-1, min(i+size+size-1, n-1))
        size += size
    return alist

def merge(alist, start, mid, end):
    blist = alist[start:end+1]  # 复制一份. blist是辅助空间。最终的排序结果放进alist中。
    l = start
    k = mid + 1
    pos = start
    
    while pos <= end:
        if (l > mid):
            alist[pos] = blist[k-start]
            k += 1
        elif (k > end):
            alist[pos] = blist[l-start]
            l += 1
        elif blist[l-start] <= blist[k-start]:
            alist[pos] = blist[l-start]
            l += 1
        else:
            alist[pos] = blist[k-start]
            k += 1
        pos += 1
复制代码

3 利用数据结构

堆排序

  • 时间复杂度:O(nlogn)
  • 空间复杂度:O(1) 原地操作当然是O(1)啦
  • 稳定性: 肯定不稳定呀~想想所有值都相等的情况
  • 完全二叉树:除最后一层节点外,其他层节点都有两个子节点,并且最后一层节点都要左排列。(满二叉树勾掉最右边几个叶子)在树的顺序存储法中不浪费存储空间,故得名完全二叉树。
菜狗写法
class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def heaplify(i):
            # 以i处为堆顶,调整小顶堆
            left,right = 2*i +1, 2*i+2
            if left < len(nums) and nums[left]<nums[i]:   # len(num)可能会发生改变
                nums[left],nums[i] = nums[i],nums[left]
                heaplify(left)
            if right < len(nums) and nums[right]<nums[i]:
                nums[right],nums[i]=nums[i],nums[right]
                heaplify(right)

        for i in range( len(nums)//2 - 1, -1, -1):
            heaplify(i)

        ans = []
        while nums:
            ans.append(nums[0]) 
            nums[0] = nums[-1]
            nums.pop()
            if nums:
                heaplify(0)
        return ans
复制代码
  • 改进点1:heaplify里直接和最小的交换就可以了。目前的写法可能出现两次交换,增大计算量。
  • 改进点2:可以使用大顶堆 + 从后向前排序。不使用额外空间~
class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def heaplify(i, size): # 更改后的大顶堆
            left,right = 2*i +1, 2*i+2
            j = i
            if left < size and nums[left] >nums[i]:    j = left
            if right < size and nums[right] >nums[j]:  j = right
            if j==i: return
            else: 
                nums[i], nums[j] = nums[j], nums[i]
                heaplify(j, size)	# 顶多只有一个递归分支
        
        for i in range( len(nums)//2 - 1, -1, -1):
            heaplify(i, len(nums))
            
        for i in range(len(nums)-1, 0, -1):   # start, end, step
            #i: 下一个要排序的地方
            nums[i], nums[0] = nums[0], nums[i]
            heaplify(0, i)
            print('{}{}'.format(nums[0:i], nums[i:]))
        
        return nums
        
Inputs:
[0,1,2,3,5,6,7,8,9]
Stdout:
[8, 5, 7, 2, 0, 3, 6, 1][9]
[7, 5, 6, 2, 0, 3, 1][8, 9]
[6, 5, 3, 2, 0, 1][7, 8, 9]
[5, 2, 3, 1, 0][6, 7, 8, 9]
[3, 2, 0, 1][5, 6, 7, 8, 9]
[2, 1, 0][3, 5, 6, 7, 8, 9]
[1, 0][2, 3, 5, 6, 7, 8, 9]
[0][1, 2, 3, 5, 6, 7, 8, 9]
复制代码

资料

www.bigocheatsheet.com/ 这个网站很好~

免责声明:文章版权归原作者所有,其内容与观点不代表Unitimes立场,亦不构成任何投资意见或建议。

Python

475

相关文章推荐

未登录头像

暂无评论