基于C++实现的各种内部排序算法汇总

概述

本攻略汇总了常见的基于C++实现的内部排序算法，包括选择排序、冒泡排序、插入排序、希尔排序、归并排序、快速排序、堆排序。以下是算法的具体实现过程。

选择排序

选择排序的核心思想是每次找到未排序序列中的最小值，然后放到已排序序列的末尾。具体实现过程如下：

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

示例：

vector<int> nums = {3, 2, 1, 5, 4};
selection_sort(nums);
// nums: {1, 2, 3, 4, 5}

冒泡排序

冒泡排序的核心思想是从未排序序列中不断交换相邻元素，直到将最大元素放到已排序序列的末尾。具体实现过程如下：

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

示例：

vector<int> nums = {3, 2, 1, 5, 4};
bubble_sort(nums);
// nums: {1, 2, 3, 4, 5}

插入排序

插入排序的核心思想是将未排序序列中的元素依次插入到已排序序列中的合适位置。具体实现过程如下：

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

示例：

vector<int> nums = {3, 2, 1, 5, 4};
insertion_sort(nums);
// nums: {1, 2, 3, 4, 5}

希尔排序

希尔排序是插入排序的改进版。它将序列按照一定间隔分组，对每组进行插入排序，然后逐步缩小间隔直到为1，最后再进行一次插入排序。具体实现过程如下：

void shell_sort(vector<int>& nums) {
    int n = nums.size();
    int gap = n / 2;
    while (gap > 0) {
        for (int i = gap; i < n; i++) {
            int j = i - gap;
            int temp = nums[i];
            while (j >= 0 && nums[j] > temp) {
                nums[j + gap] = nums[j];
                j -= gap;
            }
            nums[j + gap] = temp;
        }
        gap /= 2;
    }
}

示例：

vector<int> nums = {3, 2, 1, 5, 4};
shell_sort(nums);
// nums: {1, 2, 3, 4, 5}

归并排序

归并排序的核心思想是将序列分成两部分，对每部分分别进行排序，然后再将两部分合并。具体实现过程如下：

void merge(vector<int>& nums, int l, int m, int r) {
    vector<int> sorted(r - l + 1);
    int i = l, j = m + 1, k = 0;
    while (i <= m && j <= r) {
        if (nums[i] < nums[j]) {
            sorted[k++] = nums[i++];
        } else {
            sorted[k++] = nums[j++];
        }
    }
    while (i <= m) {
        sorted[k++] = nums[i++];
    }
    while (j <= r) {
        sorted[k++] = nums[j++];
    }
    for (int i = l, k = 0; i <= r; i++, k++) {
        nums[i] = sorted[k];
    }
}

void merge_sort(vector<int>& nums, int l, int r) {
    if (l < r) {
        int m = (l + r) / 2;
        merge_sort(nums, l, m);
        merge_sort(nums, m + 1, r);
        merge(nums, l, m, r);
    }
}

示例：

vector<int> nums = {3, 2, 1, 5, 4};
merge_sort(nums, 0, nums.size() - 1);
// nums: {1, 2, 3, 4, 5}

快速排序

快速排序的核心思想是选择一个基准元素，将比它小的元素放在左边，比它大的元素放在右边，然后再分别对左右部分进行排序。具体实现过程如下：

int partition(vector<int>& nums, int l, int r) {
    int pivot = nums[r];
    int i = l;
    for (int j = l; j < r; j++) {
        if (nums[j] < pivot) {
            swap(nums[i], nums[j]);
            i++;
        }
    }
    swap(nums[i], nums[r]);
    return i;
}

void quick_sort(vector<int>& nums, int l, int r) {
    if (l < r) {
        int p = partition(nums, l, r);
        quick_sort(nums, l, p - 1);
        quick_sort(nums, p + 1, r);
    }
}

示例：

vector<int> nums = {3, 2, 1, 5, 4};
quick_sort(nums, 0, nums.size() - 1);
// nums: {1, 2, 3, 4, 5}

堆排序

堆排序的核心思想是将序列看成一颗完全二叉树，每个节点的值不大于它的子节点的值，将其称为小根堆。堆排序的过程就是不断将堆顶元素与最后一个元素交换，然后将剩下的序列重新构建成小根堆。具体实现过程如下：

void heapify(vector<int>& nums, int n, int i) {
    int largest = i;
    int l = 2 * i + 1, r = 2 * i + 2;
    if (l < n && nums[l] > nums[largest]) {
        largest = l;
    }
    if (r < n && nums[r] > nums[largest]) {
        largest = r;
    }
    if (largest != i) {
        swap(nums[i], nums[largest]);
        heapify(nums, n, largest);
    }
}

void heap_sort(vector<int>& nums) {
    int n = nums.size();
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(nums, n, i);
    }
    for (int i = n - 1; i >= 0; i--) {
        swap(nums[0], nums[i]);
        heapify(nums, i, 0);
    }
}

示例：

vector<int> nums = {3, 2, 1, 5, 4};
heap_sort(nums);
// nums: {1, 2, 3, 4, 5}

结语

以上便是常见的基于C++实现的内部排序算法。这些算法在不同的场景下有着不同的适用性，需要根据具体情况选择合适的算法。