3类方法 - 实现数组排序

题目

NO. 912
给你一个整数数组 nums，请你将该数组升序排列。

示例 1：

输入：nums = [5,2,3,1]
输出：[1,2,3,5]

示例 2：

输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]

提示：

1 <= nums.length <= 50000
-50000 <= nums[i] <= 50000

常用概念

1. 大 O 复杂度：并不具体表示代码真正的复杂度，而是表示随着数据规模增长的变化趋势
2. 时间复杂度：代码执行时间或执行指令次数，通过大O复杂度表示，称为渐进时间复杂度，简称时间复杂度，一般有4种分类来表示，默认指平均：
   1. 最好情况时间复杂度：在最理想的情况下，执行这段代码的时间复杂度
   2. 最坏情况时间复杂度：在最糟糕的情况下，执行这段代码的时间复杂度
   3. 平均情况时间复杂度：对各类情况加权平均后的时间复杂度，或叫加权平均时间复杂度或者期望时间复杂度
   4. 均摊时间复杂度：一种特殊的平均时间复杂度，大意是指平摊到每种执行花费的查询时间
3. 空间复杂度：类别时间复杂度的概念，表示算法的存储空间与数据规模之间的增长关系。
4. 稳定性：对于存在相等元素的待排序元素，经过排序之后，相等元素之间原始顺序是否改变
5. 原地排序：指空间复杂度是 O(1)

解法一（冒泡[n²]类）

思路：以冒泡为代表的一类排序算法，通过两层循环进行数据对比和排序，这类排序算法的时间复杂度为O(n²)，常见的排序算法包括：冒泡排序、选择排序、插入排序，3个的核心思想近似。

1. 冒泡排序：查询就像是水里的泡泡往水面冒一样，每次对比相邻两个元素，如果不满足大小关系要求就让它俩互换位置
2. 插入排序：取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入
3. 选择排序：在未排序区间的数据中，查找最小的元素，放到已排序区间的末尾

• 时间复杂度：O(n²)
• 空间复杂度：O(1)
• 稳定性：稳定（冒泡、插入），不稳定（选择）
• 原地排序：是

解法二、三全部算法通过了全部测试用例，解法一时间复杂度过高，数据量大的时候会超时，有个超时的测试用例有5万个正负整数，具体看链接：https://www.zhenxiangsimple.com/files/tech/testCase20200331.txt

冒泡排序

# author：suoxd123@126.com
class Solution:#冒泡排序
    def sortArray(self, nums: List[int]) -> List[int]:
        numLen = len(nums)
        for i in range(0,numLen):
            flag = True  #提前退出冒泡循环的标志位
            for j in range(0,numLen-1-i):
                if nums[j] > nums[j+1]: #比较相邻元素，顺序不满足时，交换位置
                    nums[j],nums[j+1] = nums[j+1],nums[j] 
                    flag = False #存在数据交换
            if flag:
            	break
        return nums

插入排序

# author：suoxd123@126.com
class Solution:#插入排序
    def sortArray(self, nums: List[int]) -> List[int]:
        numLen = len(nums)
        for i in range(1,numLen):# 从前往后表示有序数据放前面
            j, tmpVal = i-1, nums[i]
            while j >= 0 and nums[j] > tmpVal:#查找插入位置
                nums[j+1] = nums[j] # 数据向后移动
                j -= 1
            nums[j+1] = tmpVal
        return nums

选择排序

# author：suoxd123@126.com
class Solution: #选择排序
    def sortArray(self, nums: List[int]) -> List[int]:
        numLen = len(nums)
        for i in range(0,numLen):
            minIdx, tmpVal = i, nums[i]
            for j in range(i+1, numLen): #查找最小值
                if nums[j] < tmpVal:
                    minIdx, tmpVal = j, nums[j] # 找到更小值
            if i != minIdx:  #交换最小值和无序的第一个（有序的末尾）
                nums[i], nums[minIdx] = nums[minIdx], nums[i]
        return nums

解法二（快排[nlogn]类）

思路：以快速排序为代表的一类排序算法，通过分治的思想实现排序，这类排序算法的时间复杂度为O(nlogn)，适合大规模的数据排序，比上面的那三种排序算法更常用，常见的排序算法包括：快速排序、归并排序、堆排序、希尔排序，4个的核心思想基本近似。

1. 快速排序：随机选择一个数A，将小于A的放左边，大于A的数放右边，然后分别对左右两边进行排序
2. 归并排序：将待排序元素按下标分为两部分，分别对两边排序后，再合并为一个整体
3. 堆排序：将待排序元素构建为堆结构（大顶堆），并取堆顶元素放到有序区域（最前面），重复前面步骤，直到待排序区域只剩一个元素，也可以选择小顶堆。
4. 希尔排序：首先对待排序元素分别按照一个间隔进行分组，然后对组内元素进行插入排序，重复前面步骤，直到间隔值到1后排序的结果即为有序集合，间隔一般选：n/2, n/4, 8/n，…，1

• 时间复杂度：O(nlogn)
• 空间复杂度：归并O(n)，其它O(1)
• 稳定性：归并稳定，（快排、堆、希尔）不稳定
• 原地：归并不是，（快排、堆、希尔）是

快速排序

# author：suoxd123@126.com
class Solution:#快速排序
    # 将数组按分为大小两部分，并递归进行快排
    def splitArray(self, nums, start, end):
        if start >= end: #起止中间没有数据
            return        
        splitIdx = self.getQuickIdx(nums,start, end)
        self.splitArray(nums, start, splitIdx-1) # 左边
        self.splitArray(nums, splitIdx+1, end) # 右边
    # 获取分割数值对应的索引
    def getQuickIdx(self, nums, start, end):
        tmpVal = nums[end] #以最后一个作为分割数（也可以选第一个或其它）        
        i = start # i 标记分割数要插入的位置（即i始终指向比tmpVal大的第一个数）
        #也可以从左到右找大值，从右到左找小值，然后交换
        for j in range(start,end+1):        
            if nums[j] < tmpVal:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1
        nums[i], nums[end] = nums[end], nums[i]
        return i

    def sortArray(self, nums: List[int]) -> List[int]:
        numLen = len(nums)
        self.splitArray(nums,0,numLen-1)
        return nums

归并排序

# author：suoxd123@126.com
class Solution:#归并排序
    # 将数组按下标递归分开为两部分
    def splitArray(self, nums, start, end):
        if start >= end: #起止中间没有数据
            return        
        mid = int((start + end) / 2)
        self.splitArray(nums, start, mid) # 左边
        self.splitArray(nums, mid+1, end) # 右边
        self.joinArray(nums, start, mid, mid+1, end)
    # 将两个有序数组，合并为一个有序数组
    def joinArray(self, nums, leftStart, leftEnd, rightStart, rightEnd):
        leftIdx, rightIdx , idx, cnt= leftStart, rightStart, 0, rightEnd - leftStart + 1
        tmpArray = [0] * cnt
        # 使用两个指针分别指向两部分的最小值
        while leftIdx <= leftEnd and rightIdx <= rightEnd: 
            if nums[leftIdx] < nums[rightIdx]:
                tmpArray[idx] = nums[leftIdx]
                leftIdx += 1
            else:
                tmpArray[idx] = nums[rightIdx]
                rightIdx += 1
            idx += 1
        #判断哪部分仍有剩余数组
        tmpStart, tmpEnd = leftIdx, leftEnd
        if rightIdx <= rightEnd:
            tmpStart, tmpEnd = rightIdx, rightEnd
        while tmpStart <= tmpEnd:
            tmpArray[idx] = nums[tmpStart]
            idx , tmpStart = idx+1, tmpStart+1
        # 将临时有序数据 放回原始数组
        for i in range(0,cnt):
            nums[leftStart+i] = tmpArray[i]        

    def sortArray(self, nums: List[int]) -> List[int]:
        numLen = len(nums)
        self.splitArray(nums,0,numLen-1)
        return nums

堆排序

# author：suoxd123@126.com
class Solution:#堆排序
    #将原始数组 调整为堆结构
    def initalHeap(self, nums,cnt):
        mid = int(cnt/2)  # n/2以上的都在叶子节点，不需要调整
        for i in range(mid,-1,-1):   #从下往上建堆
            self.buildHeap(nums,cnt, i)
    # 设置索引idx的堆值（最大/小值）
    def buildHeap(self,nums, cnt, idx): #构建大顶堆
        maxIdx = idx
        if idx * 2 < cnt and nums[idx] < nums[idx * 2]:#左子树
            maxIdx = idx * 2
        if idx*2 + 1<cnt and nums[maxIdx] < nums[idx*2 + 1]:#右子树
            maxIdx = idx*2 + 1
        if maxIdx != idx: #递归 保证子树原来的堆结构
            nums[maxIdx], nums[idx] = nums[idx], nums[maxIdx]
            self.buildHeap(nums, cnt, maxIdx)

    def sortArray(self, nums: List[int]) -> List[int]:
        numLen = len(nums)
        self.initalHeap(nums,numLen)
        for i in range(numLen-1,0,-1): #直到剩下一个元素
            #大顶堆的堆顶是最大值，放在数组末尾
            nums[0], nums[i] = nums[i], nums[0]
            self.buildHeap(nums,i, 0)
        return nums

希尔排序

# author：suoxd123@126.com
class Solution:#希尔排序
    def sortArray(self, nums: List[int]) -> List[int]:
        numLen, gapLen = len(nums), int(len(nums)/2)
        while gapLen >= 1:
            for i in range(0,gapLen): #共gapLen个分组
                for k in range(i,numLen,gapLen):#组内插入排序
                    j, tmpVal = k - gapLen, nums[k]
                    while j >= 0 and nums[j] > tmpVal:#插入排序：寻找插入点
                        nums[j+gapLen] = nums[j]
                        j -= gapLen
                    nums[j + gapLen] = tmpVal
            gapLen = int(gapLen/2) #间隔减半
        return nums

解法三（桶[n]类）

思路：前面两类排序算法都是基于比较实现排序，当前以桶排序为代表的一类排序算法，都不涉及元素之间的比较，这类排序算法的时间复杂度为O(n)，适合用在有特殊属性的数据的排序，常见的排序算法包括：桶排序、计数排序、基数排序，3个的核心思想近似。

1. 桶排序：将要排序的数据分到几个有序的桶里，对每个桶里的数据进行单独排序，桶内排序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。
2. 计数排序：当要排序的 n 个数据，所处的范围并不大的时候，比如最大值是 k，就可以把数据划分成 k 个桶，每个桶内的数据值都是相同的，省掉了桶内排序的时间。
3. 基数排序：将待排序元素按位数切割成不同的数字，然后按每个位数分别比较进行排序，要求比较的排序使用稳定的排序算法。

• 时间复杂度：（桶、计数）O(n+k)，基数O(nk)，k是桶个数
• 空间复杂度：（桶、基数）O(n)，计数O(n+k)
• 稳定性：稳定
• 原地：不是

桶排序

计数排序可以当作桶排序的一种特例，对桶内的数据进行排序即为桶排序，桶内数据的排序可以使用快排或归并排序，甚至可以继续使用桶排序进行递归，本算法使用了python内置的排序。
当前桶数量选择了可以覆盖所有数值的数量，也可以选择其它数量，只要能够将数据按顺序映射到各个桶内即可。

# author：suoxd123@126.com
class Solution:#桶排序
    def sortArray(self, nums: List[int]) -> List[int]:
        numLen, numMin, numMax = len(nums), min(nums), max(nums)
        bucketCnt = numMax - numMin +1  #桶的数量可以覆盖所有数值
        buckets = [[] for _ in range(0, bucketCnt)] #构建桶
        for num in nums:
            buckets[num - numMin].append(num)
        for i in range(0, bucketCnt):# 桶内排序
            buckets[i].sort()
        return [valArray[i] for valArray in buckets for i in range(0,len(valArray))]

计数排序

# author：suoxd123@126.com
class Solution:#计数排序
    def sortArray(self, nums: List[int]) -> List[int]:
        numLen, numMin, numMax = len(nums), min(nums), max(nums)
        tmpBucket = [0] * (numMax-numMin + 1) # 申请k个桶
        # 对元素进行计数（放入桶中）
        for num in nums:
            tmpBucket[num-numMin] += 1
        for i in range(1,numMax-numMin + 1):#把计数进行累加
            tmpBucket[i] += tmpBucket[i-1]
        tmpArray = [0] * numLen
        for i in range(0,numLen):#直接将数据放入累计数量对应的索引
            tmpArray[tmpBucket[nums[i]-numMin] - 1] = nums[i]
            tmpBucket[nums[i]-numMin] -= 1
        nums = tmpArray
        return nums

基数排序

# author：suoxd123@126.com
class Solution:#基数排序
    def sortArray(self, nums: List[int]) -> List[int]:
        numLen, numMin = len(nums), min(nums)
        nums = [num - numMin for num in nums] #兼容负值
        numMax = max(nums)
        i, j = 0, len(str(numMax)) #记录最高位数
        while i < j: #从低到高，对所有位数进行排序
            tmpBitArray = [[] for _ in range(10)]
            for num in nums:
                tmpBitArray[int(num / (10**i)) % 10].append(num)
            nums.clear()# 清除原数组
            for bitArray in tmpBitArray:
                for val in bitArray:
                    nums.append(val)#使用有序子序列恢复原数据
            i += 1        
        return [num + numMin for num in nums]