排序算法_牛客博客

总觉得，如果说什么是算法的起点，那就是排序算法，所以今天打算记录下跟排序算法相关的内容。
排序算法有太多类了，但最容易入门的，经典的，自然是冒泡排序。

冒泡排序

冒泡这个词很形象，就是大的或者小的，往单向传递：

A(1)>A(2),则两者交换位置，从A(2)继续，直到A(n)是最大的。
再从A(1)开始，直到A(n-1)是第二轮最大的。
...

import numpy as np
import random
class Solution:
    def bubbleSort(self,arr):
        print('UnSortedArr',arr)
        n = len(arr)
        for i in range(n-1):
            for j in range(n-i-1):
                if arr[j]>arr[j+1]:
                    arr[j],arr[j+1]=arr[j+1],arr[j]
        print('SortedArr:',arr)
        return arr

f = Solution()
arr = list(np.random.randint(low=0,high=101,size=10))
f.bubbleSort(arr)

UnSortedArr [20 37 24 30 40 3 79 51 87 71]
SortedArr: [ 3 20 24 30 37 40 51 71 79 87]

这里的两个print用于初次引用函数时，对内部的数据进行简单监视，后面的按照自己的需求来。

归并排序

核心：分而治之
先看整体，如果一个数列，被砍成了两半，然后left,right中都是排好序了，那么把它们再合并成一个整体，过程就是不停对比left[0],right[0],谁小谁先放。
而left，right可以利用递归，按照相同的办法进行排序。
值得注意的是，Python内置的sorted算法就是归并算法，只是利用了底层实现，省却了很多开销，比我们用python编写的要快很多。

class Solution:
    def mergeSort(self,arr):
        if len(arr)<2:return arr

        middle = int(len(arr)/2)    # 砍成两部分
        left = self.mergeSort(arr[:middle])  # 调用递归
        right = self.mergeSort(arr[middle:])

        result = []  # 合并
        while left and right:
            result.append(left.pop(0) if left[0]<right[0] else right.pop(0))
        result.extend(left if left else right)

        return result

快速排序

20世纪最伟大的十大算法之一登场
核心思想：分而治之
随机取一个数，然后把比这个数小的都放left，大的都放right，然后对左右做同样的事。

class Solution:
    def quickSort(self,arr):
        if len(arr)<=1:return arr
        pivot = arr[0]  # 选取的轴心
        left = [x for x in arr[1:] if x<=pivot] # 这个等号不能漏，否则漏数
        right = [x for x in arr[1:] if x>pivot ]
        return self.quickSort(left)+[pivot]+self.quickSort(right)

基排序

对于数字来说，就说简单的正数吧，是由基构成的，789的基就是个位，十位，百位，基有3个，分别按照各个基来放进去就OK了，这个排序办法很符合人类对各个数的判断。先从高位判断和先从低位判断不影响最终结果。

class Solution:
    def baseSort(self,arr):
        arrStr= [str(x) for x in arr]
        maxN = max(arrStr,key=len)

        for i in range(1,len(maxN)+1):
            bracket = [[] for _ in range(10)]
            for x in arrStr:
                bracket[0].append(x) if len(x)<i else bracket[int(x[-i])].append(x)

            arrStr=[]
            for x in bracket:
                arrStr+=x
        return [int(x) for x in arrStr]

计数排序

把基排序的基拓展到极限，就是每一个数都有一个bracket，然后放进去。
开一个数列空间，大小为O(Max-Min)，然后分别计数，最后输出。
值得注意的是，这个速度真的超级快啊，尤其是数据比较密集的时候。但是大分布小数据就比较不适合，根据业务不同要区别对待。

class Solution:
    def countSort(self,arr):
        minNum=min(arr)
        maxNum=max(arr)
        tmp = (maxNum-minNum+1)*[0]
        for i in arr:
            tmp[i-minNum]+=1

        res = []
        for i in range(len(tmp)):
            if tmp[i]:
                res+=[i+minNum]*tmp[i]
        return res

桶排序

桶排序其实应该是介于基排序与计数排序之间的，它比较灵活，可以自由拆解组合。
计数排序是每个数给个桶，这下桶的数量会有点多，如果按照每10个数给个桶，然后桶内用插入排序，就会很快，因为桶内一直是有序的，插入排序就会很快。

class Solution:
    def bucketSort(self,arr):
        maxNum=max(arr)
        bucket = [[] for x in range(int(maxNum/10)+1)]

        for i in arr:
            n=int(i/10)
            if bucket[n]==[]:
                bucket[n].append(i)
            else:   
                m= len(bucket[n])
                for j in range(m):
                    if i<=bucket[n][j]:
                        bucket[n].insert(j,i)
                        break
                if len(bucket[n])==m:
                    bucket[n].append(i)

        res = []
        for i in bucket:
            res+=i
        return res

最重要的，是掌握归并排序和快速排序，其它的了解思想即可，当有针对性业务时，才会有比较好的效果。