From: 爱编程的大丙
Author: 爱编程的大丙
原文链接：八大排序算法

一、冒泡排序

  1. 冒泡排序是稳定排序,原因是相等的值不交换，且只与相邻元素交换，不会打乱原有顺序
  2. 做法：每次都从待排序的部分挑选出一个最大值放在最后（挑选的方式是相邻元素都比较一次）
void bubble_sort(std::vector<int>& arr)
{
    int length = arr.size() - 1;
    // isSwap用于减少循环轮数，防止已经排好序后继续排序
    bool isSwap = false;
    // i 控制循环轮数
    for (int i = 0; i < length; ++i)
    {
        isSwap = false;
        // j不能从j=i+1开始，一次完整的内循环只能将最大的数字放在相对最后的位置，并没有对左边的数字进行排序
        for (int j = 0; j < length - i; ++j)
        {
            if (arr[j] > arr[j + 1])
            {
                std::swap(arr[j], arr[j + 1]);
                isSwap = true;
            }
        }
        if (!isSwap)
        {
            break;
        }
    }
}

二、选择排序

  1. 选择排序是不稳定排序 原因是会出现长距离交换，会打乱原有的顺序
  2. 做法：每次都从待排序的部分找到最大或最小值的位置然后交换放在相对最前的位置
void selected_sort(std::vector<int>& arr)
{
    int length = arr.size() - 1;
    // i 控制循环轮数
    for (int i = 0; i < length; ++i)
    {
        int minPos = i;
        // 找到最大或最小值的位置
        for (int j = i + 1; j <= length; ++j)
        {
            if (arr[minPos] > arr[j])
            {
                minPos = j;
            }
        }
        if (minPos != i)
        {
            std::swap(arr[i], arr[minPos]);
        }
    }
}

三、插入排序

  1. 插入排序是稳定排序， 原因是我们是根据待排序数组的顺序进行排序的，且与相邻元素比较，不会出现长距离交换的情况
  2. 做法：从待排序的数组中选出第一个元素A，让这个元素和已排好序的数组的最后一个进行比较B，如果A<B,则将A后移一位覆盖数据，从此往复，知道找到小于B的元素，然后将B插入到该位置
void insert_sort(std::vector<int>& arr)
{
    int length = arr.size() - 1;
    // i表示待排序的数组
    for (int i = 1; i <= length; ++i)
    {
        // 使用一个临时的变量存储待排序的第一个元素，方便后续插入数据和移动覆盖数据
        int temp = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > temp)
        {
            arr[j + 1] = arr[j];
            --j;
        }
        arr[j + 1] = temp;
    }
}

四、 希尔排序

  1. 插入排序的优化版 但并不是稳定排序 原因是：交换的元素并不是相邻的元素，存在长距离交换的情况
  2. 做法：利用插入排序趋向排好序的数组排序速度快的特点，将一个大数组分为一个个小数组对其进行插入排序，又因为每一个小数组都趋向于有序，所以排序速度很快，最后会导致整个大数组都趋向于有序，这样就能提高排序速度
void shell_sort(std::vector<int>& arr)
{
    int length = arr.size();
    for (int gap = length / 2; gap > 0; gap /= 2)
    {
        for (int i = gap; i < length; ++i)
        {
            int temp = arr[i];
            int j = i - gap;
            while (j >= 0 && arr[j] > temp)
            {
                arr[j + gap] = arr[j];
                j -= gap;
            }
            arr[j + gap] = temp;
        }
    }
}

五、快速排序

  1. 快速排序是不稳定排序，原因是因为交换的元素并不是相邻的元素，会出现长距离交换元素的情况
  2. 做法：快速排序采用分治法，通常在中间取一个基准数，然后将比基准数小的元素放在左边，比基准数大的元素放在右边，如果左边的元素比基准数大，右边的元素比基准数小，则交换这两个元素的位置，直到所有元素都排好序，即left>right停止，然后重新划分子数组，通过不断递归的方式，当所有的子数组都排好序后，整个数组也就排好序了
void quick_sort(std::vector<int>& arr)
{
    if (arr.empty())
    {
        return;
    }
    quick_sort(arr, 0, arr.size() - 1);
}
void quick_sort(std::vector<int>& arr, int left, int right)
{
    if (left >= right)
    {
        return;
    }
    // 基准数 取中间元素作为基准数,left + (right - left) / 2是为了防止left+right溢出
    int pivotValue = arr[left + (right - left) / 2];

    int begin = left - 1, end = right + 1;
    while (begin < end)
    {
        do
        {
            begin++;
        } while (arr[begin] < pivotValue);
        do
        {
            end--;
        } while (arr[end] > pivotValue);

        if (begin < end)
        {
            std::swap(arr[begin], arr[end]);
        }
    }
    quick_sort(arr, left, end);
    // 下面这个的left参数不能使用begin+1,否则会导致一个元素会排序两次
    quick_sort(arr, end + 1, right);
}

六、归并排序

  1. 归并排序是稳定排序, 原因是：交换的是相邻的元素且是有序的，相等的元素不会交换位置
  2. 通过不断递归将数组分到不可再分为止，最后每一个子数组都是一个元素，然后将具有同一个分支的两个子数组进行合并，合并成一个有序数组最后，当所有的子数组都合并成一个有序数组后，整个数组也就排好序了
void merge_sort(std::vector<int>& arr)
{
    if (arr.empty())
    {
        return;
    }
    std::vector<int> temp(arr.size());
    merge_sort(arr, temp, 0, arr.size() - 1);
}
void merge_sort(std::vector<int>& arr, std::vector<int>& temp, int left, int right)
{
    if (left >= right)
    {
        return;
    }
    int mid = left + (right - left) / 2;
    // 递归分割数组
    merge_sort(arr, temp, left, mid);
    merge_sort(arr, temp, mid + 1, right);
    // 合并同一个分支上的两个有序数组(开始时每一个子数组都是1个元素)
    int i = left, j = mid + 1, index = 0;
    while (i <= mid && j <= right)
    {
        if (arr[i] < arr[j])
        {
            temp[index++] = arr[i++];
        }
        else
        {
            temp[index++] = arr[j++];
        }
    }
    // 将剩余的元素放入临时数组,只会有一个while循环执行
    while (i <= mid)
    {
        temp[index++] = arr[i++];
    }
    while (j <= right)
    {
        temp[index++] = arr[j++];
    }

    // 将临时数组中的元素放入原数组
    for (int k = 0; k < index; ++k)
    {
        arr[left + k] = temp[k];
    }
}

七、堆排序

  1. 堆排序是不稳定排序，因为顶部元素和最后一个非叶子节点交换时是长距离交换，会打乱顺序
  2. 做法：先构建大根堆，通过将第一个元素和最后一个元素交换后，最后一个元素就是最大的元素，然后将剩下的元素进行再次堆排序，直到所有的元素都排好序为止
void head_sort(std::vector<int>& arr, int length, int parent)
{
    // 不需要构建满二叉树，我们默认数组就是满二叉树
    int maxIndex = parent;
    int leftChild = 2 * parent + 1;
    int rightChild = 2 * parent + 2;
    // 找到最大值的索引
    if (leftChild < length && arr[leftChild] > arr[maxIndex])
    {
        maxIndex = leftChild;
    }
    if (rightChild < length && arr[rightChild] > arr[maxIndex])
    {
        maxIndex = rightChild;
    }
    // 如果最大值不是父节点，则交换父节点和最大值的值
    if (maxIndex != parent)
    {
        std::swap(arr[parent], arr[maxIndex]);
        // 继续递归调整交换后的子树，继续比较其与其子树的大小
        head_sort(arr, length, maxIndex);
    }
}
void head_sort(std::vector<int>& arr)
{
    if (arr.empty())
    {
        return;
    }
    // 由于大根堆的性质，父节点的值大于等于子节点的值，所以我们从最后一个非叶子节点开始调整
    // 逐个向上比较全部的非叶子节点，直到将最大的非叶子节点调整到根节点，此时根节点就是最大值
    // 然后将根节点和最后一个叶子节点交换(将最大值放在最后)，然后重新构建大根堆
    // 循环这个过程，直到所有的非叶子节点都调整完毕
    
    //arr.size()/2-1就是最后一个元素的父节点,构建大根堆
    for (int i = arr.size() / 2 - 1; i >= 0; --i)
    {
        head_sort(arr, arr.size(), i);
    }
    //开始排序操作
    for (int i = arr.size() - 1; i > 0; --i)
    {
        // 交换根节点和最后一个叶子节点,i就是最后一个叶子节点的索引
        std::swap(arr[0], arr[i]);
        // 重新构建大根堆，length是去掉最后一个叶子节点的长度，即去掉节点i后的长度
        head_sort(arr, i, 0);
    }
}

推荐链接：六大排序算法：插入排序、希尔排序、选择排序、冒泡排序、堆排序、快速排序