算法--常见十大排序算法（python实现）

一、冒泡排序

算法思想：

第 i (i = 1，2，… ) 趟排序时从序列中前 n - i + 1 个元素的第 1 个元素开始，相邻两个元素进行比较，若前者大于后者，两者交换位置，否则不交换。

冒泡排序法是通过相邻元素之间的比较与交换，使值较小的元素逐步从后面移到前面，值较大的元素从前面移到后面，就像水底的气泡一样向上冒，故称这种排序方法为冒泡排序法。

算法步骤：

• 先将序列中第 1 个元素与第 2 个元素进行比较，若前者大于后者，则两者交换位置，否则不交换；
• 然后将第 2 个元素与第 3 个元素比较，若前者大于后者，则两者交换位置，否则不交换；
• 依次类推，直到第 n - 1 个元素与第 n 个元素比较（或交换）为止。经过如此一趟排序，使得 n 个元素中值最大元素被安置在序列的第 n 个位置上。
• 此后，再对前 n - 1 个元素进行同样过程，使得该 n - 1 个元素中值最大元素被安置在第 n - 1 个位置上。
• 然后再对前 n - 2 个元素重复上述过程，直到某一趟排序过程中不出现元素交换位置的动作，排序结束。

算法分析：

• 最好的情况下，初始时序列已经是从小到大有序（升序），则只需经过一趟 n - 1 次元素之间的比较，并且不移动元素，算法就可结束排序。此时，算法的时间复杂度为 O(n)。
• 最差的情况是当参加排序的初始序列为逆序，或者最小值元素处在序列的最后时，则需要进行 n - 1 趟排序，总共进行 ∑i=2n(i−1)=n(n−1)/2 次元素之间的比较，因此，冒泡排序算法的平均时间复杂度为 O(n**2)。
• 冒泡排序方法在排序过程中需要移动较多次数的元素。因此，冒泡排序方法比较适合于参加排序序列的数据量较小的情况，尤其是当序列的初始状态为基本有序的情况；而对于一般情况，这种方法是排序时间效率最低的一种方法。
• 由于元素交换是在相邻元素之间进行的，不会改变值相同元素的相对位置，因此，冒泡排序法是一种 稳定排序法。

代码实现：

class Solution:
  def bubbleSort(self,arr):
    for i in range(len(arr)):
      for j in range(len(arr)-i-1):
        if arr[j] > arr[j+1]:
          arr[j],arr[j+1] = arr[j+1],arr[j]
          
    return arr
  
  def sortArray(self,nums:List[int]) --> List[int]:
    return self.bubbleSort(nums)

案例实现：

【LeetCode】283.移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例：

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

使用冒泡排序解题：

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
      	for i in range(len(nums)):
            for j in range(len(nums)-i-1):
                if nums[j] < nums[j+1]:
                    nums[j],nums[j+1] = 								nums[j+1],nums[j]
      	return nums

结果是错误的：

输入：

[0,1,0,3,12]

输出：

[12,3,1,0,0]

预期结果：

[1,3,12,0,0]

​ 原来我们题目要求是要保证原数字相对位置不改变，但是我们冒泡算法的书写是没问题的，不过并不常用。

二、选择排序

算法思想：

第 i 趟排序从序列的后 n − i + 1 (i = 1, 2, …, n − 1) 个元素中选择一个值最小的元素与该 n - i + 1 个元素的最前面那个元素交换位置，即与整个序列的第 i 个位置上的元素交换位置。如此下去，直到 i == n − 1，排序结束。

可以简述为：每一趟排序中，从剩余未排序元素中选择一个最小的元素，与未排好序的元素最前面的那个元素交换位置。

算法步骤：

• 在算法中设置整型变量 i，既可以作为排序趟数的计算，同时也作为执行第 i 趟排序时，参加排序的后 n − i + 1 个元素的第 1 个元素的位置。
• 整型变量 min_i 记录这 n − i + 1 个元素中值最小元素的位置。
• 每一趟排序开始，先另 min_i = i （即暂时假设序列的第 i 个元素为值最小者，以后经过比较后视实际情况再正式确定最小值元素的位置）。
• 第 i 趟排序比较结束时，这 n − i + 1 个元素中真正的值最小元素为下标 min_i 对应的元素。此时，若有 min_i == i，说明值最小元素就是这 n − i + 1 个元素的第 1 个元素，意味着此趟排序不必进行元素交换。

算法分析：

对于具有 n 个元素的序列采用选择排序方法要经过 n - 1 趟排序。

• 当原始序列是一个按值递增序列（升序）时，元素的移动次数最少，为 0 次。当序列初始时是一个按值递减序列（逆序）时，元素的移动次数最多，为 3(n−1) 次（3 是交换 arr[i] 与 arr[min_i] 的执行次数）。
• 但是，无论序列中元素的初始排列状态如何，第 i 趟排序要找出值最小元素都需要进行 n − i 次元素之间的比较。因此，整个排序过程需要进行的元素之间的比较次数都相同，为 ∑i=2n(i−1)=n(n−1)/2 次。
• 这说明选择排序法所进行的元素之间的比较次数与序列的原始状态无关，同时可以确定算法的时间复杂度为 O(n**2)。
• 由于值最小元素与未排好序的元素中第 1 个元素的交换动作是在不相邻的元素之间进行的，因此很有可能会改变值相同元素的前后位置，因此，选择排序法是一种不稳定的排序方法。

代码实现：

class Solution:
  def selectionSort(self,arr):
    for i in range(len(arr)-1):
      min_i = i
      for j in range(i+1,len(arr)):
        if arr[j] < arr[min_i]:
          min_i = j
      if i != min_i:
        arr[i],arr[min_i] = arr[min_i],arr[i]
   	return arr
  
  def sortArray(self,nums:List[int])-->List[int]:
    return self.selectionSort(nums)

案例实现：

【LeetCode】215. 数组中的第K个最大元素

给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例：

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

使用选择排序解题：

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
      for i in range(len(nums)-1):
            min_i = i
            for j in range(i+1,len(nums)):
                if nums[j] < nums[min_i]:
                    min_i = j
            if i != min_i:
                nums[i],nums[min_i] = 								nums[min_i],nums[i]
      return nums[-k]

将数组排序后取第k大的元素，但是这样的结果花费的时间特别长，使用的也并不常见。

三、插入排序

算法思想：

将整个序列切分为两部分：前 i - 1 个元素是有序序列，后 n - i + 1 个元素是无序序列。每一次排序，将无序序列的首元素，在有序序列中找到相应的位置并插入。

可以简述为：每一趟排序中，将剩余无序序列的第一个元素，插入到有序序列的适当位置上。

算法步骤：

• 将第一个元素作为一个有序序列，将第 2 ~ n - 1 个元素作为无序序列。
• 从头至尾一次扫描无序序列，将扫描到的每个元素插入到有序序列的适当位置上。

算法分析：

• 对于具有 n 个元素的序列，插入排序方法一共要进行 n - 1 趟排序。
• 对于插入排序算法，整个排序过程只需要一个辅助空间 temp。
• 当原始序列是一个按值递增序列（升序）时，对应的每个 i 值只进行一次元素之间的比较，因而总的比较次数最少，为 ∑i=2n1=n−1，并不需要移动元素（记录），这是最好的情况。
• 最坏的情况是，序列初始时是一个按值递减序列（逆序），则对应的每个 i 值都要进行 i - 1 次元素之间的比较，总的元素之间的比较次数达到最大值，为 ∑i=2n(i−1)=n(n−1)/2。
• 如果序列的初始情况是随机的，即参加排序的序列中元素可能出现的各种排列的概率相同，则可取上述最小值和最大值的平均值作为插入排序时所进行的元素之间的比较次数，约为 n2/4。由此得知，插入排序算法的时间复杂度 O(n**2)。
• 插入排序方法属于稳定性排序方法。

代码实现：

class Solution:
  def insertSort(self,arr):
    for i in range(1,len(arr)):
      temp = arr[i]
      j = i
      while j > 0 and arr[j-1] > temp:
        arr[j] = arr[j-1]
        j -= 1
      arr[j] = temp
    return arr
  
  def sortArray(self,nums:List[int])-->List[int]:
    return self.insertionSort(nums)
  

案例实现：

【LeetCode】75. 颜色分类

给定一个包含红色、白色和蓝色、共 n* *个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库的sort函数的情况下解决这个问题。

示例：

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

使用插入排序解题：

class Solution:
    def sortColors(self, nums: List[int]) -> None:
      for i in range(1,len(nums)):
         temp = nums[i]
         j = i
         while j > 0 and nums[j-1] > temp:
             nums[j] = nums[j-1]
             j -= 1
         nums[j] = temp
      return nums

插入排序也是一个比较耗时的方法，一般这类题目也比较少，不是很常见。

四、希尔排序

算法思想：

将整个序列切按照一定的间隔取值划分为若干个子序列，每个子序列分别进行插入排序。然后逐渐缩小间隔进行下一轮划分子序列和插入排序。直至最后一轮排序间隔为 1，对整个序列进行插入排序。

算法步骤：

• 首先确定一个元素间隔数 gap，然后将参加排序的序列按此间隔数从第 1 个元素开始一次分成若干个子序列，即分别将所有位置相隔为 gap 的元素视为一个子序列，在各个子序列中采用某种排序方法进行插入排序。

• 然后减少间隔数，并重新将整个序列按新的间隔数分成若干个子序列，再分别对各个子序列进行排序，如此下去，直到间隔数 gap = 1。

  ​

算法分析：

• 希尔排序方法的速度是一系列间隔数 gapi 的函数，不太容易弄清楚比较次数与 gap 之间的依赖关系，并给出完整的数学分析。

• 上面算法中，由于采用 gapi=⌊gapi−1/2⌋ 的方法缩小间隔数，对于具有 n 个元素的序列，若 gap1=⌊n/2⌋，则经过 p=⌊log2n⌋ 趟排序后就有 gapp=1，因此，希尔排序方法的排序总躺数为 ⌊log2n⌋。

• 从算法中也可以看到，最外层的 while 循环为 log2n 数量级，中间层 do-while 循环为 n 数量级。当子序列分得越多时，子序列内的元素就越少，最内层的 for 循环的次数也就越少；反之，当所分的子序列个数减少时，子序列内的元素也随之增多，但整个序列也逐步接近有序，而循环次数却不会随之增加。因此，希尔排序算法的时间复杂度在 O(nlog2n) 与 O(n2) 之间。

• 希尔排序方法是一种不稳定排序算法。

  ​

代码实现：

class Solution:
    def shellSort(self, arr):
        size = len(arr)
        gap = size // 2

        while gap > 0:
            for i in range(gap, size):
                temp = arr[i]
                j = i
                while j >= gap and arr[j - gap] > temp:
                    arr[j] = arr[j - gap]
                    j -= gap
                arr[j] = temp
            gap = gap // 2
        return arr

    def sortArray(self, nums: List[int]) -> List[int]:
        return self.shellSort(nums)

案例实现：

了解即可，时间复杂度上稍微比前面的排序方法快一些，但是也几乎不使用该排序方法。

五、归并排序

算法思想：

采用经典的分治策略，先递归地将当前序列平均分成两半，直到所有的子序列长度都为1，然后将有序序列两两合并，最终合并成一个有序序列。

算法步骤：

• 初始时，将待排序序列中的 n 个记录看成 n 个有序子序列（每个子序列总是有序的），每个子序列的长度均为 1。
• 把当前序列组中有序子序列两两归并，完成一遍之后序列组里的排序序列个数减半，每个子序列的长度加倍。
• 对长度加倍的有序子序列重复上面的操作，最终得到一个长度为 n 的有序序列。

算法分析：

• 归并排序算法的时间复杂度等于归并趟数与每一趟归并的时间复杂度成绩。子算法 merge(left_arr, right_arr): 的时间复杂度是 O(n)，因此，归并排序算法总的**时间复杂度为 O(nlog2n)**。
• 归并排序方法需要用到与参加排序的序列同样大小的辅助空间。因此算法的空间复杂度为 O(n)。
• 因为在两个有序子序列的归并过程中，如果两个有序序列中出现相同元素，merge(left_arr, right_arr): 算法能够使前一个序列中那个相同元素先被复制，从而确保这两个元素的相对次序不发生改变。所以归并排序算法是 稳定排序算法。

代码实现：

class Solution:
  #子序列排序函数
  def merge(self,left_arr,right_arr):
    arr = []
    while left_arr and right_arr:
      if left_arr[0] <= right_arr[0]:   
        arr.append(left_arr.pop(0))   #如果左边小于右边，则将小于的推入arr中，循环比较，直到此子序列全部排序完成
      else:
        arr.append(right_arr.pop(0))
    while left_arr:
      arr.append(left_arr.pop(0))
    while right_arr:
      arr.append(right_arr.pop(0))
    return arr
  
  def mergeSort(self,arr):
    size = len(arr)
    if size < 2:
      return arr
    mid = size//2
    left_arr,right_arr = arr[0:mid],arr[mid:]   #将序列分成两半
    return self.merge(self.mergeSort(left_arr),self.mergeSort(right_arr))
  
  def sortArray(self,nums:List[int])-->List[int]:
    return self.mergeSort(nums)

案例实现：

做了力扣上的一道叫合并排序的数组，两个数组合并后排序，但是用归并没做出来，不是因为两个数组的问题，而是因为归并数组算法思想是分而治之，递归思想，在两个数组下，没有搞明白如何去递归，导致最后没能写出来。

六、快速排序

算法思想：

快速排序，又称划分交换排序，从无序队列中挑取一个元素，把无序队列分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

算法步骤：

• 从数组中随机找到一个基准数。
• 然后将数组中比基准数大的元素移动到基准数右侧，比他小的元素移动到基准数左侧，从而把数组拆分为左右两个部分。
• 再对左右两个部分分别重复第二步，直到各个部分只有一个数，则排序结束。

算法分析：

• 在参加排序的元素初始时已经有序的情况下，快速排序方法花费的时间最长。此时，第 1 趟排序经过 n - 1 次比较以后，将第 1 个元素仍然确定在原来的位置上，并得到 1 个长度为 n - 1 的子序列；第 2 趟排序进过 n - 2 次比较以后，将第 2 个元素确定在它原来的位置上，又得到 1 个长度为 n - 2 的子序列；依次类推，最终总的比较次数为 (n−1)+(n−2)+…+1=n(n−1)/2。因此时间复杂度为 O(n2)。

• 还有一种情况，若每趟排序后，分界元素正好定位在序列的中间，从而把当前参加排序的序列分成大小相等的前后两个子序列，则对长度为 n 的序列进行快速排序所需要的时间为：

  T(n)≤ n+2T(n/2) ≤ 2n+4T(n/2) ≤ 3n+8T(n/8) …… ≤ (log2n)n+nT(1)=O(nlog2n)

  因此，快速排序方法的时间复杂度为 O(nlog2n)，时间性能显然优于前面讨论的几种排序算法。

• 无论快速排序算法递归与否，排序过程中都需要用到堆栈或其他结构的辅助空间来存放当前待排序序列的首、尾位置。最坏的情况下，空间复杂度为 O(n)。

• 若对算法进行一些改写，在一趟排序之后比较被划分所得到的两个子序列的长度，并且首先对长度较短的子序列进行快速排序，这时候需要的空间复杂度可以达到 O(log2n)。

• 快速排序时一种 不稳定排序算法，也是一种不适合在链表结构上实现的排序算法。

代码实现：

class Solution:
  def sortArray(self,nums:List[int])-->List[int]:
    return self.quick_sort(nums,0,len(nums)-1)
  
  def quick_sort(self,arr,low,high):
    # 分治 一分为二
    # start=end ,证明要处理的数据只有一个
    # start>end ,证明右边没有数据
    if low >= high:
        return
    # 定义两个游标，分别指向0和末尾位置
    left = low
    right = high
    # 把0位置的数据，认为是中间值
    mid = arr[left]
    while left < right:
        # 让右边游标往左移动，目的是找到小于mid的值，放到left游标位置
        while left < right and arr[right] >= mid:
            right -= 1
        arr[left] = arr[right]
        # 让左边游标往右移动，目的是找到大于mid的值，放到right游标位置
        while left < right and arr[left] < mid:
            left += 1
        arr[right] = arr[left]
    # while结束后，把mid放到中间位置，left=right
    arr[left] = mid
    # 递归处理左边的数据
    quick_sort(arr, low, left-1)
    # 递归处理右边的数据
    quick_sort(li, left+1, high)

案例实现：

【LeetCode】912.排序数组

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

示例：

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

快速排序方法解题：

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def quicksort(nums,left,right):
            flag=nums[(left+right)//2]              #每次从中间初始化哨兵位置
            i,j=left,right                          #设定从左到右的指针i，从右到左的指针j
            while i<=j:
                while nums[i]<flag: i+=1            #i从左往右扫，找到大于等于flag的数。
                while nums[j]>flag: j-=1            #j从右往左扫，找到小于等于flag的数。
                if i<=j:
                    nums[i],nums[j]=nums[j],nums[i] #交换左右指针下标对应的数值
                    i+=1                            #左指针继续往右走
                    j-=1                            #右指针继续往左走
            if i<right: quicksort(nums,i,right)     #递归解决flag左边的低位数组的排序
            if j>left:  quicksort(nums,left,j)      #递归解决flag右边的低位数组的排序
        quicksort(nums,0,len(nums)-1)               #函数入口，将整个数组的信息传入
        return nums                                 #返回修改后的nums

快排主要搞定对范围判定及递归过程的理解

七、堆排序

算法思想：

堆顶（小顶堆）的元素是整个堆中最小的元素，将堆顶元素与最后一个元素交换，然后用一次‘向下筛选’将新的堆顶元素移动到堆中正确的位置：即比较堆顶元素与其两个左右子结点的大小，如果堆顶元素最小，则将其保留在堆顶位置，停止；如果左子结点或右子结点最小，则交换堆顶元素与左子结点或右子结点的值，然后再沿着当前路径不断地比较下去，直至最初的堆顶元素在某一次比较中是最小值或者到达叶结点位置。

此外，如果是小顶堆，得到的是降序序列；如果是大顶堆，得到的是升序序列。

堆可以看作一棵完全二叉树，这棵二叉树满足，任何一个非叶节点的值都不大于（或不小于）其左右孩子节点的值

算法步骤：

堆排序需要解决两个问题：

• 如何由一个无序序列建成一个堆
• 如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？

针对第二个问题：一般在输出堆顶元素之后，视为将这个元素排除，然后用表中最后一个元素填补它的位置，自上向下进行调整：首先将堆顶元素和它的左右子树的根结点进行比较，把最小的元素交换到堆顶；然后顺着被破坏的路径一路调整下去，直至叶子结点，就得到新的堆。

Step 1： 构造初始堆

初始化堆时是对所有的非叶子结点进行筛选
最后一个非终端元素的下标是[n/2]向下取整，所以筛选只需要从第[n/2]向下取整个元素开始，从后往前进行调整。

Step 2：进行堆排序

堆排序是一种选择排序。建立的初始堆为初始的无序区。

排序开始，首先输出堆顶元素（因为它是最值），将堆顶元素和最后一个元素交换，这样，第n个位置（即最后一个位置）作为有序区，前n-1个位置仍是无序区，对无序区进行调整，得到堆之后，再交换堆顶和最后一个元素，这样有序区长度变为2。。。

不断进行此操作，将剩下的元素重新调整为堆，然后输出堆顶元素到有序区。每次交换都导致无序区-1，有序区+1。不断重复此过程直到有序区长度增长为n-1，排序完成。

算法分析：

• 因为建堆的时间复杂度是 O ( n ) O(n)O(n) ，调整堆的时间复杂度是 O ( l o g n ) O(logn)O(logn) ，所以堆排序的时间复杂度是 O ( n l o g n ) O(nlogn)O(nlogn)
• 由于在堆积排序中只需要一个记录大小的辅助空间，因此，堆积排序的空间复杂度为：O(1)。
• 堆排序属于 不稳定排序算法。堆排序也是一种不适合在链表上实现的排序。
• 堆排序方法对记录数较少的文件并不值得提倡，但对n较大的文件还是很有效的。因为其运行时间主要耗费在建初始堆和调整建新堆时进行的反复“筛选”上。

代码实现：

案例实现：

八、计数排序

算法思想：

使用一个额外的数组 counts，其中第 i 个元素 counts[i] 是待排序数组 arr 中值等于 i 的元素个数。然后根据数组 counts 来将 arr 中的元素排到正确的位置。

计数排序(Counting Sort)是一种不比较数据大小的排序算法，是一种牺牲空间换取时间的排序算法。

计数排序适合数据量大且数据范围小的数据排序，如对人的年龄进行排序，对考试成绩进行排序等。

算法步骤：

• 找到待排序列表中的最大值 k，开辟一个长度为 k+1 的计数列表，计数列表中的值都为 0。
• 走访待排序列表，如果走访到的元素值为 i，则计数列表中索引 i 的值加1。
• 走访完整个待排序列表，计数列表中索引 i 的值 j 表示 i 的个数为 j，统计出待排序列表中每个值的数量。
• 创建一个新列表，遍历计数列表，依次在新列表中添加 j 个 i，新列表就是排好序后的列表，整个过程没有比较待排序列表中的数据大小。

算法分析：

• 当输入元素是 n 个 0 ~ k 之间的整数时，计数排序的时间复杂度为 O(n+k)。
• 由于用于计数的数组 counts 的长度取决于待排序数组中数据的范围（等于待排序数组最大值减去最小值再加 1）。所以计数排序对于数据范围很大的数组，需要大量的时间和内存。
• 计数排序一般用于排序整数，不适用于按字母顺序排序人名。
• 计数排序是 稳定排序算法。

代码实现：

class Solution:
    def countingSort(self, arr):
        arr_min, arr_max = min(arr), max(arr)
        size = arr_max - arr_min + 1
        counts = [0 for _ in range(size)]   #生成一个全是0的列表，用于计数

        for num in arr:
            counts[num - arr_min] += 1
        for j in range(1, size):
            counts[j] += counts[j - 1]

        res = [0 for _ in range(len(arr))]   #新建一个列表用于存放新排序后的元素
        for i in range(len(arr) - 1, -1, -1):
            res[counts[arr[i] - arr_min] - 1] = arr[i]
            counts[arr[i] - arr_min] -= 1
        return res

    def sortArray(self, nums: List[int]) -> List[int]:
        return self.countingSort(nums)

案例实现：

【LeetCode】1122. 数组的相对排序

给你两个数组，arr1 和 arr2，arr2 中的元素各不相同，arr2 中的每个元素都出现在 arr1 中。

对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。

示例：

输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
输出：[2,2,2,1,4,3,3,9,6,7,19]

九、桶排序

算法思想：

将未排序的数组分到若干个「桶」中，每个桶的元素再进行单独排序。

算法步骤：

• 将区间划分为 n 个相同大小的子区间，每个区间称为一个桶。
• 遍历数组，将每个元素装入对应的桶中。
• 对每个桶内的元素单独排序（使用插入、归并、快排等算法）。
• 最后按照顺序将桶内的元素合并起来。

算法分析：

• 桶排序可以在线性时间内完成排序，当输入元素个数为 n，桶的个数是 m 时，每个桶里的数据就是 k = n / m 个。每个桶内排序的时间复杂度为 O(k∗log2k)。m 个桶就是 $m * O(k * log_2k) = m * O((n/m)log_2(n/m)) = O(nlog_2(n/m))$。当桶的个数 m 接近于数据个数 n 时，log2(n/m) 就是一个较小的常数，所以排序桶排序时间复杂度接近于 O(n)。
• 由于桶排序使用了辅助空间，所以桶排序的空间复杂度是 o(n+m)。
• 如果桶内使用插入排序算法等稳定排序算法，则桶排序也是 稳定排序算法。

代码实现：

class Solution:
    def insertionSort(self, arr):
        for i in range(1, len(arr)):
            temp = arr[i]
            j = i
            while j > 0 and arr[j - 1] > temp:
                arr[j] = arr[j - 1]
                j -= 1
            arr[j] = temp

        return arr

    def bucketSort(self, arr, bucket_size=5):
        arr_min, arr_max = min(arr), max(arr)    #找到最大最小的数
        bucket_count = (arr_max - arr_min) // bucket_size + 1  #划分子区间
        buckets = [[] for _ in range(bucket_count)]  #创建桶

        for num in arr:
            buckets[(num - arr_min) // bucket_size].append(num)   #将元素放置相对应的桶中

        res = []   
        for bucket in buckets: 
            self.insertionSort(bucket)  #使用选择排序对桶中元素进行排序
            res.extend(bucket)

        return res

    def sortArray(self, nums: List[int]) -> List[int]:
        return self.bucketSort(nums)

案例实现：

十、基数排序

算法思想：

将整数按位数切割成不同的数字，然后按每个位数分别比较进行排序。

算法步骤：

基数排序算法可以采用「最低位优先法（Least Significant Digit First）」或者「最高位优先法（Most Significant Digit first）」。最常用的是「最低位优先法」。

下面我们以最低位优先法为例，讲解一下算法步骤。

• 遍历数组元素，获取数组最大值元素，并取得位数。
• 以个位元素为索引，对数组元素排序。
• 合并数组。
• 之后依次以十位，百位，…，直到最大值元素的最高位处值为索引，进行排序，并合并数组，最终完成排序。

算法分析：

• 基数排序的时间复杂度是 O(k∗n)。其中 n 是待排序元素的个数，k 是数字位数。k 的大小取决于数字位的选择（十进制位、二进制位）和待排序元素所属数据类型全集的大小。
• 基数排序的空间复杂度是 O(n+k)。
• 基数排序是 稳定排序算法。

代码实现：

class Solution:
    def radixSort(self, arr):
        size = len(str(max(arr)))    #获取最大元素的位数

        for i in range(size):
            buckets = [[] for _ in range(10)]
            for num in arr:
                buckets[num // (10 ** i) % 10].append(num)  #从个位开始进行排序
            arr.clear()
            for bucket in buckets:
                for num in bucket:
                    arr.append(num)

        return arr

    def sortArray(self, nums: List[int]) -> List[int]:
        return self.radixSort(nums)

案例实现：