排序

排序简介

排序：就是将一组无序的记录序列按照某种逻辑顺序重新排序，调整为有序的记录序列的过程。

简单的说，对于一组记录序列而言，就是根据记录的关键字递增顺序或者递减关系，将记录的次序进行重新排列，使得原来一组次序任意的记录序列转变为按其值有序排列的一组记录序列。

排序算法分类

由于待排序的记录数量不同，使得排序过程中涉及的存储器不同，可将排序算法分为两大类：

  • 内部排序算法：当参加排序的数据量不大时，在排序过程中将全部记录存放在内存中处理，这种算法称为内部排序算法。
  • 外部排序算法：当参加排序的数据量较大时，以致于内存不足以一次存放全部记录，在排序过程中需要通过内存与外存之间的数据交换来达到排序目的，这种排序算法称为外部排序算法。

对于具有多个相同值的记录序列来说，如果采用的排序算法使得排序前后拥有相同值记录的相对位置保持不变，则称此排序为稳定的，否侧就是不稳定的。相应的排序算法可以分为以下两大类：

  • 稳定性排序算法：对于值相同的两个元素，排序前后的先后次序不变，这种方法称为稳定性排序方法。
  • 非稳定性排序算法：对于值相同的两个元素，排序前后的先后次序改变，这种方法称为非稳定性排序方法。

根据记录在存储介质上的组织方式划分排序算法的种类，可以分为以下两大类：

  • 顺序存储结构排序算法（数组排序）：记录之间的逻辑顺序是通过其物理地址的先后来映射，在排序过程中需要移动记录的位置。
  • 链式存储结构排序算法（链表排序）：文件中的一个记录对应着链表中的一个链结点，记录之间的逻辑顺序是通过指针来反应，因而排序过程中不必移动记录，只需修改相应指针的指向。

常见的排序算法

常见的排序算法主要有十种：冒泡排序算法、选择排序算法、插入排序算法、希尔排序算法、归并排序算法、快速排序算法、堆排序算法、计数排序算法、桶排序算法、基数排序算法。
按照算法时间复杂度来划分：

  • O(n^2):冒泡排序算法、选择排序算法、插入排序算法
  • O(n*log_{2}n)：希尔排序算法、归并排序算法、快速排序算法、堆排序算法。
  • O(n):计数排序算法、桶排序算法、基数排序算法

数组相关的排序算法

冒泡排序算法

冒泡排序基本思想

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

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

冒泡排序算法步骤

1.先将序列中第1个元素与第2个元素进行比较，若前者大于后者，则两者交换位置，否则不交换；

2.然后将第2个元素与第3个元素比较，若前者大于后者，则两者交换位置，否则不交换；

3.依次类推，直到第n-1个元素与第n个元素比较（或交换）为止。经过如此一趟排序，使得n个元素中值最大元素被安置在序列的第n个位置上。

4.此后，再对前n-1个元素进行同样过程，使得该n-1个元素中值最大元素被安置在第n-1个位置上。

5.然后再对前n-2个元素重复上述过程，直到某一趟排序过程中不出现元素交换位置的动作，排序结束。

冒泡排序代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def bubbleSort(self, arr):
        isSorted = True
        
        for i in range(len(arr)):
            for j in range(len(arr) - i - 1):
                if arr[i] > arr[j + 1]:
                    arr[i], arr[j+1] = arr[j+1], arr[i]
                    isSorted = False
            if isSorted:
                return arr
        return arr
    def sortArray(self, nums):
        return self.bubbleSort(nums)

冒泡排序算法分析

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

选择排序算法

选择排序基本思想

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

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

选择排序算法步骤

1.在算法中设置整型变量i，既可以作为排序趟数的计算，同时也作为执行第i趟排序时，参加排序的后n-i+1个元素的第1个元素的位置。

2.整型变量min_i记录这n-i+1个元素中值最小元素的位置。

3.每一趟排序开始，先令min_i=i（即暂时假设序列的第i个元素为值最小者，以后经过比较后视实际情况再正式确定最小值元素的位置）。

4.然后在n-i+1个元素中选择一个值最小的元素，并保存下标位置到min_i中。

5.第i趟排序t比较结束时，如果有若有min_i！=i，则交换两个位置上的元素。如果有min_i==i，则不需要交换两个位置上的元素。

选择排序代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def selectSort(self, arr):
        for i in range(len(arr) - 1):
            # 记录序列最小数索引
            min_i = i
            for j in range(1, len(arr)):
                if arr[j] < arr[min_i]:
                    min_i = j
            # 如果找到最小数，则替换i位置上元素和最小数位置上元素
            if i != min_j:
                arr[i], arr[min_i] = arr[min_i], arr[i]
        return arr
    
    def sortArray(self, nums):
        return self.bubbleSort(nums)

选择排序算法分析

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

  • 无论序列中初始排列状态如何，第i趟排序要找出值最小元素都需要进行n-i次元素之间的比较。因此，整个排序过程需要进行的元素之间的比较次数都相同，为\sum_{i=2}^{n}(i - 1)=\frac{n(n-1)}{2}次。
  • 这说明选择排序法所进行的元素之间的比较次数与序列的原始状态无关，同时可以确定算法的时间复杂度为O(n^2)。
  • 由于我们进行交换元素时是在不相邻的元素之间进行的，因此很有可能会改变值相同元素的前后位置，因此，选择排序法是一种非稳定性排序算法。

插入排序

插入排序算法思想

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

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

插入排序算法步骤

1.将第一个元素作为一个有序序列，将第2~n-1个元素作为无序序列。

2.从无序序列中挑出第一个元素，在有序序列中找到对应位置。

3.将该元素插入到有序序列的对应位置上（可能需要移动元素再插入）。

4.继续2~3步，直到每个元素都插入到有序序列的适当位置上。

插入排序算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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):
        return self.insertSort(nums)f

插入排序算法分析

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

希尔排序

希尔排序其实是插入排序的一个优化。前面我们知道，插入排序的时间复杂度为O(n^2)，主要取决于数组的有序程度和数组元素个数，数组有程度高且数组元素个数较少则插入排序工作量就相对小了，不需要过多的比较和交换。而希尔排序就是为插入排序预先创造了这两个条件。

希尔排序算法思想

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

希尔排序算法步骤

  • 首先确定一个元素间隔数gap，然后将参加排序的序列按此间隔数从第1个元素开始一次分成若干个子序列，即分别将所有位置相隔为gap的元素视为一个子序列，在各个子序列中采用某种排序方法进行排序。
  • 然后减少间隔数，并重新将整个序列按新的间隔数分成若干个子序列，再分别对各个子序列进行排序，如此下去，直到间隔数gap=1。

希尔排序图解

希尔排序代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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 //= 2
        return arr
    
    def sortArray(self, nums):
        return self.shellSort(nums)

希尔排序算法分析

  • 希尔排序方法的速度是一系列间隔数 gap_i 的函数，不太容易弄清楚比较次数与gap之间的依赖关系，并给出完整的数学分析。
  • 由于采用的方法缩小间隔数，对于具有n个元素的序列，若gap_i = n/2,则经过p = log_{2}n趟排序后就有 gap=1,因此，希尔排序方法的排序总趟数为log_{2}n。
  • 从算法中也可以看到，最外层的while循环为log_{2}n数量级，中间层 do-while 循环为n数量级。当子序列分得越多时，子序列内的元素就越少，最内层的for循环的次数也就越少；反之，当所分的子序列个数减少时，子序列内的元素也随之增多，但整个序列也逐步接近有序，而循环次数却不会随之增加。因此，希尔排序算法的时间复杂度在O(log_{2}n）与0(n^2)之间。
  • 希尔排序方法是一种非稳定性排序算法。

希尔排序最坏情况O(n^2):

数组: 2 1 5 3 7 6 9 8

对于上述数组进行排序，只要我们的增量gap是偶数，则每组元素都不会发生交换，一直到我们把增量gap缩减为1，数组才会按照直接插入排序的方式进行调整。

对此，就需要我们对希尔排序选择更有效的增量，保证分组粗调没有盲区，则每轮增量需要彼此互质，即除了1之外没有其他公约数。对此，人们提出了Hibbard增量和Sedgewick增量。

Hibbard增量序列：

1， 3， 5， 7， 15， …

通项公式：2^{k-1}

Sedgewick增量序列：

1， 5， 19， 41， 109, …

通项公式：9*4^{k} - 9*2^{k} + 1 或 4 - 3*2^{k} + 1

利用此增量方式的希尔排序最坏时间复杂度是O(n^{3/4})

归并排序算法

归并排序算法思想

  • 采用经典的分治策略，先递归地将当前序列平均分成两半。
  • 然后将有序序列两两合并，最终合并成一个有序序列。

归并排序算法步骤

1.初始时，将待排序序列中的n个记录看成n个有序子序列（每个子序列总是有序的），每个子序列的长度均为1。

2.把当前序列组中有序子序列两两归并，完成一遍之后序列组里的排序序列个数减半，每个子序列的长度加倍。

3.对长度加倍的有序子序列重复上面的操作，最终得到一个长度为的有序序列。

归并排序算法代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution:
    def merge(self, l_arr, r_arr):
        arr = []
        while l_arr and r_arr:
            if l_arr[0] <= r_arr[0]:
                arr.append(l_arr.pop(0))
            else:
                arr.append(r_arr.pop(0))
        while l_arr:
            arr.append(l_arr.pop(0))
        while r_arr:
            arr.append(r_arr.pop(0))
        return arr
    
    def mergeSort(self, arr):
        size = len(arr)
        if size < 2:
            return arr
        mid = len(arr) // 2
        l_arr, r_arr = arr[0:mid], arr[mid:]
        return self.merge(self.mergeSort(l_arr), self.mergeSort(r_arr))
    
    def sortArray(self, nums):
        return self.mergeSort(nums)
# 通用写法2
class Solution:
    def mergeSort(self, arr, start, end):
        if start < end:
            mid = start + (end - start) // 2
            self.mergeSort(arr, start, mid)
            self.mergeSort(arr, mid + 1, end)
            
            self.merge(arr, start, mid, end)
    
    def merge(self, arr, start, mid, end):
        temp_arr = [0 for i in range(end - start + 1)]
        p1 = start
        p2 = mid + 1
        p = 0
        
        while p1 <= mid and p2 <= end:
            if arr[p1] < arr[p2]:
                temp_arr[p] = arr[p1]
                p1 += 1
            else:
                temp_arr[p] = arr[p2]
                p2 += 1
            p += 1
            
        while p1 <= mid:
            temp_arr[p] = arr[p1]
            p1, p = p1 + 1, p + 1
        while p2 <= end:
            temp_arr[p] = arr[p2]
            p2, p = p2 + 1, p + 1
        
        for i in range(len(temp_arr)):
            arr[i + start] = temp_arr[i]

归并排序算法分析

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

快速排序算法

快速排序算法思想

通过一趟排序将无序序列分为独立的两个序列，第一个序列的值均比第二个序列的值小。然后递归地排列两个子序列，以达到整个序列有序。

快速排序算法步骤

1.从数组中找到一个基准数。

2.然后将数组中比基准数大的元素移动到基准数右侧，比他小的元素移动到基准数左侧，从而把数组拆分为左右两个部分。

3.再对左右两个部分分别重复第二步，直到各个部分只有一个数，则排序结束。

快速排序代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import random

class Solution:
    def randomPartition(self, arr, low, high):
        # 随机生成一个pivot下标
        i = random.randint(low, high)
        # 将pivot数值与数组末尾的数值交换位置
        arr[i], arr[high] = arr[high], arr[i]
        # 调用partition函数进行排序
        return self.partition(arr, low, high)
        
    def partition(self, arr, low, high):
        # 设置i为比pivot值(high下标对应得值)小的值与大的值的分界线，初始化下标设置在数组最左边外
        i = low - 1
        # 获取pivot值
        pivot = arr[high]
        # 开始比较
        for j in range(low, high):
            # 如果j小于pivot值
            if arr[j] <= pivot:
                # 将比pivot大的值arr[i]与比pivot小的值arr[j]交换位置
                i += 1
                # 此时i指向比pivot小的值的下标
                arr[i], arr[j] = arr[j], arr[i]
        # i值比pivot小，将pivot值与i+1下标指向的值交换，此时i+1位置为pivot值，前i+1为有序，i+1~n不一定有序,但一定都大于pivot值，这样就确定了一个元素的位置，以此类推
        arr[i + 1], arr[high] = arr[high], arr[i + 1]
        return i + 1
        
    def quickSort(self, arr, low, high):
        if low < high:
            pi = self.randomPartition(arr, low, high)
            self.quickSort(arr, low, pi - 1)
            self.quickSort(arr, pi + 1, high)
        return arr
    
    def sortArray(self, arr):
        return self.quickSort(arr, 0, len(arr) - 1)

3.6.5快速排序算法分析

  • 在参加排序的元素初始时已经有序的情况下，快速排序方法花费的时间最长。此时，第1趟排序经过n - 1次比较以后，将第1个元素仍然确定在原来的位置上，并得到1个长度为n - 1的子序列；第2趟排序经过n - 2次比较以后，将第2个元素确定在它原来的位置上，又得到1个长度为n - 2的子序列；依次类推，最终总的比较次数为。因此时间复杂度为0(n^2)。
  • 还有一种情况，若每趟排序后，分界元素正好定位在序列的中间，从而把当前参加排序的序列分成大小相等的前后两个子序列，则对长度为n的序列进行快速排序所需要的时间为O(n*log_{2}n)。
  • 快速排序是一种非稳定性排序算法。

堆排序算法

堆排序算法思想

借用「堆结构」所设计的排序算法。将数组转化为大顶堆，重复从大顶堆中取出数值最大的节点，并让剩余的堆维持大顶堆性质。

堆排序算法步骤

1.首先将无序序列构造成第1个大顶堆（初始堆），使得n个元素的最大值处于序列的第1个位置。

2.然后交换序列的第1个元素（最大值元素）与最后一个元素的位置。

3.此后，再把序列的前n - 1个元素组成的子序列调整成一个新的大顶堆，这样又得到第2个最大值元素，把子序列的第1个元素（最大值元素）与第n-1个元素交换位置。

4.此后再把序列的前n - 2个元素调整成一个新的大顶堆，…，如此下去，直到整个序列变换成一个有序序列。

堆调整方法

把移走了最大值元素以后的剩余元素组成的序列再构造为一个新的堆积。具体步骤如下：

  • 从根节点开始，自上而下地调整节点的位置，使其成为堆积。即把序号为i的节点与其左子树节点（序号为2*i)、右子树节点（序号为2*ⅰ+1)中值最大的节点交换位置。(注意：序号和节点下标是两个概念)
  • 因为交换了位置，使得当前节点的左右子树原有的堆积特性被破坏。于是，从当前节点的左右子树节点开始，自上而下继续进行类似的调整。
  • 如此下去直到整棵完全二叉树成为一个大顶堆。

初始堆建立方法

具体步骤如下：

  • 如果原始序列对应的完全二叉树（不一定是堆）的深度为d，则从d - 1层最右侧分支节点（序号为|n/2|）开始，初始时令i=|n/2|，调用堆调整算法。
  • 每调用一次堆调整算法，执行一次i=i - 1,直到i==1时，再调用一次，就把原始序列调整为了一个初始堆。

堆排序算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import random

class Solution:
    # 调整为大顶堆
    def heapify(self, arr, index, end):
        left = index * 2 + 1
        right = left + 1
        while left <= end:
            # 当前节点为非叶子节点
            max_index = index
            if arr[left] > arr[max_index]:
                max_index = left
            if right <= end and arr[right] > arr[max_index]:
                max_index = right
            if index == max_index:
                # 如果不用交换说明当前父节点要大于左右子节点,结束此循环
                break
            # 说明父节点要小于子节点，同时父子节点交换后还要对变动的子节点的树进行调整
            arr[index], arr[max_index] = arr[max_index], arr[index]
            index = max_index
            left = 2 * index + 1
            right = left + 1
    
    # 初始化大顶堆
    def buildMaxHeap(self, arr):
        size = len(arr)
        # (size - 2) // 2是最后一个非叶子节点，叶节点不用调整(2i + 1 = 左子节点)
        for i in range((size - 2)//2, -1, -1):
            self.heapify(arr, i, size - 1)
        
        return arr
    
    def maxHeapSort(self, arr):
        # 构建大顶堆
        self.buildMaxHeap(arr)
        size = len(arr)
        for i in range(size):
            # 交换第一个最大元素到数组最末尾，并将数组长度-1
            arr[0], arr[size - i - 1] = arr[size - i - 1], arr[0]
            self.heapify(arr, 0, size - i - 2)
        
    def sortArray(self, arr):
        return self.maxHeapSort(arr)

堆排序算法分析

  • 堆积排序的时间主要花费在两个方面：

    • 构造初始堆积方法。
    • 排序过程中的，调整大顶堆方法。

  • n个元素构成的序列所对应的完全二叉树深度为d=log_{2}n+1,算法由两个部分组成：

    • 第一个部分：构造初始堆积时，从i=d-1层开始，到i=1层为止，对每个分支节点都要调用一次adjust算法，每一次adjust算法，对于第i层一个节点到第d层上建立的子堆积，所有节点可能移动的最大距离为该子堆积根节点移动到最后一层（第d层）的距离即d - i.
    • 而第i层上节点最多有2^{i-1}个，所以每一次adjust算法最大移动距离为2^{i-1}*(d-i)。因此堆积排序算法的第1个循环所需时间应该是各层上的节点数与该层上节点可移动的最大距离之积的总和，即：式子2。这部分时间花费为O(n)。

  • 在算法的第二个部分中，每次调用adjust算法一次，节点移动的最大距离为这颗完全二叉树深度d=[log_{2}n]+1，一共调用了n-1次adjust算法，所以第二个循环花费的时间为(n-1)*([log_{2}n+1=O(n*log_{2}n)])。

  • 因此，堆积排序的时间复杂度为O(n*log_{2}n)])。

  • 堆排序属于非稳定性排序算法，同时也不适合在链表上实现。

计数排序算法

计数排序算法思想

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

计数排序算法步骤

1.找出待排序数组中最大值元素和最小值元素，并设置counts数组大小为最大值-最小值+1。

2.统计数组中每个值为i的元素出现的次数，存入数组的第i项。

3.对所有的计数累加（从counts中的第一个元素开始，每一项和前一项累加）。

4.反向填充目标数组：将每个元素i放在新数组的第counts[i]项，每放一个元素就要将counts[i] -= 1

计数排序代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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)]
        # 统计次数
        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))]
        # range(0, len(arr)) 也可以
        for i in range(len(arr) - 1, -1, -1):
            # counts[arr[i] - arr_min] - 1 ： 5 对应数组的下标 4 = 5 - 1
            res[counts[arr[i] - arr_min] - 1] = arr[i]
            counts[arr[i] - arr_min] -= 1
        return res
    
    def sortArray(self, arr):
        return self.countingSort(arr)

计数排序算法分析

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

桶排序算法

桶排序算法思想

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

桶排序算法步骤

1.将区间划分为n个相同大小的子区间，每个区间称为一个桶。

2.遍历数组，将每个元素装入对应的桶中。

3.对每个桶内的元素单独排序（使用插入、归并、快排等算法）。

4.最后按照顺序将桶内的元素合并起来。

桶排序算法图解

桶排序算法代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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 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.insertSort(bucket)
            res.extend(bucket)
        return res
    
    def sortArray(self, arr):
        return self.bucketSort(arr)

桶排序算法分析

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

基数排序算法

基数排序算法思想

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

基数排序算法步骤

基数排序算法可以采用「最低位优先法」或者「最高位优先法」。最常用的是「最低位优先法」。下面我们以最低位优先法为例，讲解一下算法步骤。

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

基数排序算法代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def radixSort(self, arr):
        size = len(str(max(arr)))
        
        for i in range(size):
            # 每个位上都是0 ~ 9的值
            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, arr):
        return self.radixSort(arr)

基数排序算法分析

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

总结

排序算法名称 最好时间复杂度 最差时间复杂度 平均时间复杂度 空间复杂度 是否稳定 备注
冒泡排序 O（n）[数组已是有序] O(n^2)[数组逆序或最小元素在序列最后] O(n^2) O(1) 是 元素交换频繁
选择排序 O(n^2) O(n^2) O(n^2) O(1) 否 元素交换次数较少
插入排序 O(n-1)[数组有序] O(n(n-1)/2) O(n^2/4) O(1) 是
希尔排序 O(log_{2}n) O(n^2) O(1) 否
归并排序 O(n*log_{2}n) O(n*log_{2}n) O(n*log_{2}n) O(n) 是
快速排序 O(n*log_{2}n) O(n^2)[数组有序情况下] O(n*log_{2}n) O(1) 否
堆排序 O(n*log_{2}n)]) O(n*log_{2}n)]) O(n*log_{2}n)]) O(1) 否
计数排序 O(n+k) O(n+k) O(n+k) O(n+k) 否
桶排序 O(n*log_{2}n/m) O(n)[桶的个数m接近n时] O(n*log_{2}n/m) O(n+m) 看桶排序使用的算法是否稳定来决定
基数排序 O（k*n) O（k*n) O（k*n) O(n+k) 是