【C++】基础排序源码分享

• 六个基础排序

插入，希尔；
选择，堆；
冒泡，快速。
查看更多

#include 

using namespace std;

/// 

/// 插入排序
/// 
/// 
void insertion_sort(vector& arr) {

    // 从第二个元素向后遍历
    for (int i = 1; i < arr.size(); i++)
    {
        // 从当前元素向前遍历且前一个更大
        for (int j = i; j - 1 >= 0 && arr[j - 1] > arr[j]; j--)
        {
            // 交换二者
            swap(arr[j], arr[j - 1]);
        }
    }
}

/// 

/// 希尔排序
/// 
/// 
void shell_sort(vector& arr) {

    // 分组步长h的二分循环
    for (int h = arr.size() / 2; h >= 1; h /= 2)
    {
        // 第二个元素向后遍历
        for (int i = h; i < arr.size(); i++)
        {
            // 从当前元素向前遍历且前一个更大
            for (int j = i; j - h >= 0 && arr[j - h] > arr[j]; j -= h)
            {
                // 交换二者
                swap(arr[j - h], arr[j]);
            }
        }
    }
}

/// 

/// 选择排序
/// 
/// 
void selection_sort(vector& arr) {
    // 从第一个元素向后遍历
    for (int i = 0; i < arr.size() - 1; i++)
    {
        // 记录最小值索引
        int min = i;
        //从后一个元素向后遍历
        for (int j = i + 1; j < arr.size(); j++)
        {
            // 更新最小值索引
            if (arr[j] < arr[min])
                min = j;
        }
        // 交换二者
        std::swap(arr[i], arr[min]);
    }
}

// 堆排序：调整大顶堆
void adjust_heap(vector& nums, int right, int idx) {

    // 越界返回
    if (idx > right) return;

    // 找idx的最大子节点
    int l = idx * 2 + 1,
        r = idx * 2 + 2,
        max_child = idx;
    max_child = (l <= right && nums[max_child] < nums[l]) ? l : max_child;
    max_child = (r <= right && nums[max_child] < nums[r]) ? r : max_child;

    // 交换父子节点并置idx为最大子节点
    if (nums[idx] < nums[max_child])
    {
        swap(nums[idx], nums[max_child]);
        adjust_heap(nums, right, max_child);
    }

}

/// 

/// 堆排序
/// 
/// 
void heap_sort(vector& arr) {

    // 如果数组元素小于等于1返回
    if (arr.size() <= 1) return;

    // 从最后一个非叶子结点开始建立大根堆
    for (int i = arr.size() / 2; i >= 0; --i)
        adjust_heap(arr, arr.size() - 1, i);

    // 从最后一个节点开始交换堆顶元素并调整大根堆
    for (int i = arr.size() - 1; i >= 1; --i)
    {
        swap(arr[0], arr[i]);
        adjust_heap(arr, i - 1, 0);
    }
}

/// 

/// 冒泡排序
/// 
/// 
void bubble_sort(vector& arr) {
    // 从第一个元素向后遍历
    for (int i = 0; i < arr.size() - 1; i++)
    {
        // 从第一个元素向后遍历
        for (int j = 0; j < arr.size() - 1 - i; j++)
        {
            // 比后一个大则冒泡交换
            if (arr[j] > arr[j + 1])
                swap(arr[j], arr[j + 1]);
        }
    }
}

/// 

/// 快速排序
/// 
/// arr
/// 左边界
/// 右边界
void quick_sort(vector& arr, int l, int r) {
    // 左右边界存在
    if (l < r)
    {
        // 左右两个标兵
        int i = l, j = r;
        // 左右标兵存在
        while (i < j)
        {
            // 左右标兵存在且右标兵大于最左
            while (i < j && arr[j] >= arr[l]) --j;
            // 左右标兵存在且左标兵小于最左
            while (i < j && arr[i] <= arr[l]) ++i;
            // 交换左右标兵
            swap(arr[i], arr[j]);
        }

        // 交换标兵最左
        swap(arr[l], arr[i]);
        // 左右分别递归
        quick_sort(arr, l, i - 1);
        quick_sort(arr, i + 1, r);
    }
}