6 种排序算法动画与实现

1. 冒泡排序#

$O(n^2)$ ，稳定

每一轮比较前后两个相邻元素，如果前面比后面的大，则交换位置。

从后往前依次变得有序。

直到某次遍历发现不需要任何交换，此时序列有序。

INTERACTIVE

Bubble Sort

Loading demo…

C++14 linesExpandCollapse

void bubbleSort(vector<int>& nums) {
    int n = nums.size();
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;
        
        for (int j = 0; j < n - i - 1; j++) {
            if (nums[j] > nums[j + 1]) {
                swap(nums[j], nums[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

2. 选择排序#

$O(n^2)$ ，不稳定

每一轮从未排序区间中找到最小值，放到未排序区间的开头。

INTERACTIVE

Selection Sort

Loading demo…

C++15 linesExpandCollapse

void selectionSort(vector<int>& nums) {
    int n = nums.size();
    
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        
        for (int j = i + 1; j < n; j++) {
            if (nums[j] < nums[minIndex]) {
                minIndex = j;
                break;
            }
        }
        swap(nums[minIndex], nums[i]);
    }
}

3. 插入排序#

$O(n^2)$ ，稳定

每次从未排序序列中取第一个数，从右往左看有序序列，比它大的都往右移动一格，直到合适的位置放置该数。从前往后变得有序。

INTERACTIVE

Insertion Sort

Loading demo…

C++14 linesExpandCollapse

void insertionSort(vector<int>& nums) {
    int n = nums.size();
    
    for (int i = 1; i < n; i++) {
        int key = nums[i];
        int j = i - 1;
        
        while (j >= 0 && nums[j] > key) {
            nums[j + 1] = nums[j];
            j--;
        }
        nums[j + 1] = key;
    }
}

4. 快速排序#

$O(n\log n)$ ，不稳定

需要传三个参数：数组、左端点索引、右端点索引。

构建两个指针 i, j，初始时分别指向 left， right。

先选定一个 pivot。pivot 可以是左起点，可以是右起点，也可以是中点。

每一轮循环，从左向右找第一个大于 pivot 的元素，从右向左找第一个小于 pivot 的元素。这两个元素找到之后，如果他们的顺序是反的，则交换。

当左右指针相遇时，索引 i 的左边都小于等于 pivot，索引 i 的右边都大于等于 pivot。这个时候把 pivot 和索引 i 对应的元素交换，pivot 将会成为左右分界。

然后以索引 i 为界，递归进行左边和右边。

INTERACTIVE

Quick Sort

Loading demo…

C++24 linesExpandCollapse

void quickSort(vector<int>& nums, int left, int right) {
    if (left >= right) return;
    
    int i = left, j = right;
    int pivot = nums[left];
    while (i < j) {
        // 从右向左找第一个小于 pivot 的元素
        while (i < j && nums[j] >= pivot) {
            j--;
        }
        nums[i] = nums[j];
        // 从左向右找第一个大于 pivot 的元素
        while (i < j && nums[i] <= pivot) {
            i++;
        }
        nums[j] = nums[i];
    }
    
    // 此时 i == j，是 pivot 实际应该在的位置
    nums[i] = pivot;
    
    quickSort(nums, left, i - 1);
    quickSort(nums, i + 1, right);
}

5. 归并排序#

$O(n\log n)$ ，稳定

归并排序的关键在于合并有序数组。先递归排序左半数组和右半数组，然后将左右两个有序数组进行合并。

左右两个有序数组的合并：创建一个临时数组 temp，再创建两个指针，分别从 left 和 mid + 1 出发，两边较小的数可以添加到 temp 中，对应指针右移一位。最终剩余的未添加元素添加到 temp 数组末尾即可。最后再把temp的值复制到 nums 即可。

INTERACTIVE

Merge Sort

Loading demo…

C++27 linesExpandCollapse

void mergeSort(vector<int>& nums, int left, int right) {
    if (left >= right) return;

    int mid = left + (right - left) / 2;

    mergeSort(nums, left, mid);
    mergeSort(nums, mid + 1, right);

    vector<int> temp;
    int i = left, j = mid + 1;

    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j])
            temp.push_back(nums[i++]);
        else
            temp.push_back(nums[j++]);
    }

    while (i <= mid)
        temp.push_back(nums[i++]);

    while (j <= right)
        temp.push_back(nums[j++]);

    for (int k = 0; k < temp.size(); k++)
        nums[left + k] = temp[k];
}

6. 堆排序#

$O(n\log n)$ ，不稳定

堆排序利用大根堆进行排序。大根堆是满足父节点 >= 子节点的完全二叉树。

（完全二叉树：除了最后一层其他层都必须填满，且最后一层从左向右填不能有空缺）

步骤：

1.由数组建立大根堆
2.交换堆顶和末尾，把堆顶拿掉
3.调整堆重新变成大根堆
4.重复上述步骤

INTERACTIVE

Heap Sort

Loading demo…

C++46 linesExpandCollapse

void heapSort(vector<int>& nums) {
    int n = nums.size();

    // 建立大根堆
    for (int i = n / 2 - 1; i >= 0; i--) {
        int p = i;

        while (2 * p + 1 < n) {
            int child = 2 * p + 1; // 左孩子

            // 找左右孩子中较大的
            if (child + 1 < n && nums[child + 1] > nums[child]) {
                child++;
            }

            // 如果父节点已经大于孩子，结束
            if (nums[p] >= nums[child]) {
                break;
            }

            swap(nums[p], nums[child]);
            p = child;
        }
    }

    // 依次取出堆顶元素
    for (int i = n - 1; i > 0; i--) {
        swap(nums[0], nums[i]); // 最大值放到末尾

        int p = 0;
        while (2 * p + 1 < i) { // 重新调整堆
            int child = 2 * p + 1;

            if (child + 1 < i && nums[child + 1] > nums[child]) {
                child++;
            }

            if (nums[p] >= nums[child]) {
                break;
            }

            swap(nums[p], nums[child]);
            p = child;
        }
    }
}