stars
0%

十大排序

发表于 更新于 分类于

1. 选择排序

开启n-1轮循环，每次从未排序的元素中选择最小（或最大）的元素，将其与未排序序列的第一个元素交换位置，从而逐步构建有序序列。

选择排序的具体流程如下：

  1. 初始状态：将整个序列视为两部分，一部分是已排序序列，另一部分是未排序序列。
  2. 选择最小元素：从未排序序列中选择最小的元素，并将其与未排序序列的第一个元素交换位置。
  3. 扩大已排序序列：将交换后的元素视为已排序序列的一部分，未排序序列减少一个元素。
  4. 重复步骤2和步骤3：直到所有元素都被选择并放置到正确的位置上。

伪代码：

1
2
3
4
5
6
7
8
选择排序(A):
    for i from 0 to length(A)-2:
        minIndex = i
        for j from i+1 to length(A)-1:
            if A[j] < A[minIndex]:
                minIndex = j
        // 将未排序序列中最小元素与第i个元素交换位置
        swap(A[i], A[minIndex])

时间复杂度为O(n^2)

2. 冒泡排序

多次遍历待排序序列，每轮连续比较相邻的元素，如果“左元素 > 右元素”则交换位置，使较大的元素逐步“冒泡”到数组的末端。

冒泡排序的具体流程如下：

  1. 比较相邻元素：从数组的第一个元素开始，比较相邻的两个元素，如果前一个元素比后一个元素大，则交换它们的位置，这样较大的元素就会向数组的末端移动。
  2. 遍历整个数组：重复步骤1，遍历整个数组，直到所有的元素都已经比较过一次。
  3. 缩小范围：每次遍历过程中，都会使得数组末端的一个元素排好序，因此在下一次遍历时，可以将待排序序列的范围缩小一个元素。

伪代码：

1
2
3
4
5
6
冒泡排序(A):
    n = length(A)
    for i from 0 to n-1:
        for j from 0 to n-1-i:
            if A[j] > A[j+1]:
                swap(A[j], A[j+1])

时间复杂度：O(n^2)

3. 插入排序

插入排序（Insertion Sort）是一种简单直观的排序算法。其基本思想是将待排序的数据序列分为已排序区间和未排序区间，通过构建有序序列，对未排序的数据逐个进行插入，从而达到排序的目的。

插入排序的具体思路如下：

  1. 初始状态：将第一个元素视为已排序序列，剩余的元素为未排序序列。
  2. 遍历未排序序列：从第二个元素开始，逐个遍历未排序序列的元素。
  3. 将当前元素插入已排序序列：对于每个未排序序列中的元素，将其与已排序序列中的元素逐个比较，找到合适的位置并插入。
  4. 移动元素：为了给当前元素腾出位置，需要将已排序序列中比当前元素大的元素依次向后移动。
  5. 重复步骤3和步骤4：直到所有元素都被插入到已排序序列中。

伪代码：

1
2
3
4
5
6
7
8
插入排序(A):
    for i from 1 to length(A)-1:
        currentElement = A[i]
        j = i - 1
        while j >= 0 and A[j] > currentElement:
            A[j+1] = A[j]
            j = j - 1
        A[j+1] = currentElement

时间复杂度：O(n^2)

4. 快速排序

快速排序（quick sort）是一种基于分治策略的排序算法。基本思想是选择一个基准元素，将序列分割成两个子序列，其中一个子序列中的所有元素小于基准元素，另一个子序列中的所有元素大于基准元素，然后对这两个子序列分别进行递归排序。

快速排序的具体步骤如下：

  1. 选择基准元素：从待排序序列中选择一个元素作为基准元素。通常选择序列的第一个元素、最后一个元素或者中间的元素作为基准元素。
  2. 分割序列：根据基准元素，将序列分割成两个子序列，其中一个子序列中的元素小于基准元素，另一个子序列中的元素大于基准元素。通常使用两个指针（左指针和右指针）来实现分割，左指针指向序列的起始位置，右指针指向序列的末尾位置，然后从左右两端向中间移动指针，交换不符合条件的元素，直到左右指针相遇。
  3. 递归排序：对两个子序列分别进行递归排序，直到子序列的长度为1或0。
  4. 合并结果：将经过排序的子序列合并成最终的有序序列。

伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
快速排序(A, low, high):
    if low < high:
        pivotIndex = partition(A, low, high)
        快速排序(A, low, pivotIndex - 1)
        快速排序(A, pivotIndex + 1, high)

partition(A, low, high):
    pivot = A[low]  // 选择第一个元素作为基准元素
    left = low + 1
    right = high
    while left <= right:
        while left <= right and A[left] <= pivot:
            left = left + 1
        while left <= right and A[right] > pivot:
            right = right - 1
        if left < right:
            swap(A[left], A[right])
    swap(A[low], A[right])
    return right

快速排序的时间复杂度为 O(n log n)，其中 n 是待排序序列的长度。在平均情况下，快速排序的性能非常好，但是在最坏情况下（例如，当选择的基准元素总是序列中的最大或最小元素时），快速排序的时间复杂度可能会退化为 O(n^2)。

空间复杂度为O(n)：在输入数组完全倒序的情况下，达到最差递归深度 n ，使用 O(n)栈帧空间。若采用尾递归优化，则复杂度为O(log n)。

尾递归优化是一种编译器优化技术，用于优化递归调用的栈空间使用。在尾递归优化中，如果函数的最后一个操作是对自身的递归调用，编译器会将这种递归调用转换为循环，从而避免在调用栈上创建新的帧，节省了栈空间的使用。

5. 归并排序

归并排序（Merge Sort）是一种基于分治思想的排序算法。其基本思路是将待排序序列分成两个子序列，分别对这两个子序列进行递归排序，然后将两个已经排好序的子序列合并成一个有序序列。

具体的算法流程：

  1. 分割序列：不断地将待排序序列划分成两个子序列，直到子序列的长度为1或0
  2. 递归排序：递归地对分割后的两个子序列进行排序。
  3. 合并序列：将两个已经排好序的子序列合并成一个有序序列。

伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
归并排序(A):
    if length(A) <= 1:
        return A
    else:
        middle = length(A) / 2
        left_half = 归并排序(A[0:middle])  // 递归排序左半部分
        right_half = 归并排序(A[middle:length(A)])  // 递归排序右半部分
        return 合并(left_half, right_half)  // 合并左右两部分并返回合并后的有序序列

合并(left_half, right_half):
    result = []
    while left_half 不为空 and right_half 不为空:
        if left_half[0] <= right_half[0]:
            result.append(left_half[0])
            left_half = left_half[1:]
        else:
            result.append(right_half[0])
            right_half = right_half[1:]
    // 将剩余的元素追加到结果中
    result += left_half
    result += right_half
    return result

归并排序的时间复杂度为 O(n log n)。虽然归并排序的时间复杂度较低，但是需要额外的空间来存储归并过程中产生的临时序列，因此其空间复杂度为 O(n)。

6. 堆排序

堆排序（Heap Sort）是一种基于堆数据结构的排序算法，其基本思想是利用堆的性质实现排序。堆是一个特殊的树形数据结构，具有以下性质：

  1. 它是一个完全二叉树，即除了最后一层，其他层都是满的。
  2. 在一个小顶堆（Min Heap）中，任意节点的值都小于或等于其子节点的值。
  3. 在一个大顶堆（Max Heap）中，任意节点的值都大于或等于其子节点的值。

将待排序的序列构建成一个大顶堆，重复从堆中取出堆顶元素，并重新构建堆，直到堆为空，最终得到即为排序好的序列。

算法的流程：

  1. 构建堆：

    ​ 首先需要将待排序的序列构建成一个堆。一种常见的方法是从最后一个非叶子节点开始，依次向前进行调整，保证每个节点都满足堆的性质。

    大顶堆的调整过程：

    • 从最后一个非叶子节点开始（即 n/2-1），向前遍历到根节点。
    • 对于每个节点，如果它的子节点中有比它大的，就将其与最大的子节点进行交换，直到它没有比它大的子节点或者到达叶子节点为止。

  2. 排序：

    ​ 构建好堆之后，需要重复从堆中取出最大（或最小）的元素，并重新调整堆，直到堆为空。具体的过程如下：

    • 将堆顶元素（最大或最小值）与堆中的最后一个元素交换位置。
    • 从堆中移除最后一个元素（即最大或最小值）。
    • 对剩余的元素重新调整堆，使其满足堆的性质。

    重复以上步骤，直到堆为空。

7. 桶排序

8. 计数排序

9. 基数排序

10. 希尔排序