0912. 排序数组

0912. 排序数组 #

  • 标签:数组、分治、桶排序、计数排序、基数排序、排序、堆(优先队列)
  • 难度:中等

题目大意 #

给你一个整数数组 nums

要求:将该数组升序排列。

解题思路 #

这道题是一道用来复习排序算法,测试算法时间复杂度的好题。我试过了十种排序算法。得到了如下结论:

  • 超时算法(时间复杂度为 $O(n^2)$):冒泡排序、选择排序、插入排序。没毛病,这些都是时间复杂度 $O(n^2)$ 的排序算法。
  • 通过算法(时间复杂度为 $O(nlog_2n)$):希尔排序、归并排序、快速排序、堆排序
  • 通过算法(时间复杂度为 $O(n)$):计数排序、桶排序
  • 解答错误算法(普通基数排序只适合非负数):基数排序

下面给出这十种排序算法相关的代码。

代码 #

1. 冒泡排序 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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)

2. 选择排序 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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
            # 如果找到最小数,将 i 位置上元素与最小数位置上元素进行交换
            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)

3. 插入排序 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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 sortArray(self, nums: List[int]) -> List[int]:
        return self.insertionSort(nums)

4. 希尔排序 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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)

5. 归并排序 #

 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 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))
            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 = len(arr) // 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)

6. 快速排序 #

 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
import random
    
class Solution:
    def randomPartition(self, arr, low, high):
        i = random.randint(low, high)
        arr[i], arr[high] = arr[high], arr[i]
        return self.partition(arr, low, high)

    def partition(self, arr, low, high):
        x = arr[high]
        i = low - 1
        for j in range(low, high):
            if arr[j] <= arr[high]:
                i += 1
                arr[i], arr[j] = arr[j], arr[i]
        arr[i + 1], arr[high] = arr[high], arr[i + 1]
        return i + 1

    def quickDivideSort(self, arr, low, high):
        n = len(arr)
        if low < high:
            pi = self.randomPartition(arr, low, high)
            self.quickDivideSort(arr, low, pi - 1)
            self.quickDivideSort(arr, pi + 1, high)

        return arr

    def quickSort(self, arr):
        low, high = 0, len(arr) - 1
        return self.quickDivideSort(arr, low, high)

7. 堆排序 #

 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
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 = index * 2 + 1
            right = left + 1

    # 初始化大顶堆
    def buildMaxHeap(self, arr):
        size = len(arr)
        # (size-2) // 2 是最后一个非叶节点,叶节点不用调整
        for i in range((size - 2) // 2, -1, -1):
            self.heapify(arr, i, size - 1)
        return arr

    # 升序堆排序,思路如下:
    # 1. 先建立大顶堆
    # 2. 让堆顶最大元素与最后一个交换,然后调整第一个元素到倒数第二个元素,这一步获取最大值
    # 3. 再交换堆顶元素与倒数第二个元素,然后调整第一个元素到倒数第三个元素,这一步获取第二大值
    # 4. 以此类推,直到最后一个元素交换之后完毕。
    def maxHeapSort(self, arr):
        self.buildMaxHeap(arr)
        size = len(arr)
        for i in range(size):
            arr[0], arr[size-i-1] = arr[size-i-1], arr[0]
            self.heapify(arr, 0, size-i-2)
        return arr

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

8. 计数排序 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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))]
        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)

9. 桶排序 #

 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
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)

10. 基数排序 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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)
本站总访问量  次  |  您是本站第  位访问者