【C++】十大排序算法之归并排序快速排序

本次介绍内容参考自：十大经典算法>排序算法（C++实现） - fengMisaka - 博客园 (cnblogs.com)

算法>排序算法是《数据结构与算法》中最基本的算法之一。

十种常见算法>排序算法可以分为两大类：

比较类排序：通过比较来决定元素间的相对次序，时间复杂度为 O(nlogn)～O(n²)。
非比较类排序：不通过比较来决定元素间的相对次序，其时间复杂度可以突破 O(nlogn)，以线性时间运行。

【十大经典算法>排序算法分类】

【十大经典算法>排序算法的复杂度分析】

名词解释：

时间/空间复杂度：描述一个算法执行时间/占用空间与数据规模的增长关系。
n：待排序列的个数。
k：“桶”的个数（上面的三种非比较类排序都是基于“桶”的思想实现的）。
In-place：原地算法，指的是占用常量内存，不占用额外内存。即空间复杂度为 O(1) 。
Out-place：非原地算法，占用额外内存。
稳定性：假设待排序列中两元素相等，排序前后这两个相等元素的相对位置不变，则认为是稳定的。

一、归并排序（Merge-Sort）

归并排序是建立在归并操作上的一种有效的算法>排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为 2- 路归并。

1.1、算法描述

把长度为 n 的输入序列分成两个长度为 n/2 的子序列；
对这两个子序列分别采用归并排序；
将两个排序好的子序列合并成一个最终的排序序列。

1.2、动图演示

归并排序动图演示

1.3、C++编码

/**
* @version Copyright (c) 2024 NCDC, Servo。 Unpublished - All rights reserved
* @file MergeSort.hpp
* @brief 归并排序
* @autor 写代码的小恐龙er
* @date 2024/03/05
*/

// 【分治法】 & 【递归法】
// 时间复杂度O(n * log n)
// 空间复杂度O(n)

/* 将 arr[l..m] 和 arr[m+1..r] 归并 */
void Merge(int arr[], int l, int m, int r) {
    // 将arr数组分成左右两个 有序序列 再合并在一起
    int size = r - l + 1;
    vector<int> newArr(size, 0);

    // k代表新数组的下标
    int i = 0, j = m + 1, k = 0;
    
    // 将分组后的两边按照递增顺序排列
    while(i <= m; && j <= r) newArr[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
    while(i <= m) newArr[k++] = arr[i++];
    while(j <= r) newArr[k++] = arr[j++];

    // 重新赋值
    k =0;
    for(i = l; i <= r; i++){
        arr[i] = newArr[k++];
    }
}

void MergeSort(int arr[], int l, int r) {
    // 终止条件
    if (l >= r) return;
    // 将 arr[l..r] 平分为 arr[l..m] 和 arr[m+1..r]
    int m = (l + r) / 2;
    // 分别递归地将子序列排序为有序数列
    MergeSort(arr, l, m);
    MergeSort(arr, m + 1, r);
    // 将两个排序后的子序列再归并到 arr
    Merge(arr, l, m, r);
}

1.4 、算法分析

归并排序在实现上，通常采用 Out-place 排序（即需用到 O(n) 的额外空间的排序），在排序过程中属于稳定的算法>排序算法，其时间复杂度均为O(n * log n)。在算法实现上采用了分治法与递归思想。

二、快速排序（Quick Sort）

快速排序（Quick Sort），是冒泡排序的改进版，之所以“快速”，是因为使用了分治法。它也属于交换排序，通过元素之间的位置交换来达到排序的目的。

基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

2.1 、算法描述

从数列中挑出一个元素，称为 “基准”（pivot）；
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

2.2 、动图演示

快速排序动图演示

2.3、C++编码

/**
* @version Copyright (c) 2024 NCDC, Servo。 Unpublished - All rights reserved
* @file QuickSort.hpp
* @brief 快速排序
* @autor 写代码的小恐龙er
* @date 2024/03/05
*/

// 【分治法】 & 【递归法】
// 时间复杂度O(n * log n)
// 空间复杂度O(log n)

void QuickSort(int *arr[], int begin, int end)  
{  
    // 终止条件
	if (begin > end) // 递归，直到start = end为止
		return;

    // 基准数
	int pivot = arr[begin]; 
	int i = begin;
	int j = end;

	while (i != j)
	{
		// 从右向左找比基准数小的数 （要先从右边开始找）
		while (arr[j] >= pivot && i < j) j--;
		// 从左向右找比基准数大的数
		while (arr[i] <= pivot && i < j) i++;
		if (i < j)
		{
			// 交换两个数在数组中的位置
			int temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
		}
	}

	// 最终将基准数归位
	arr[begin] = arr[i];
	arr[i] = pivot;
    
    // 递归处理
	QuickSort(arr, begin, i - 1); // 继续处理左边的，这里是一个递归的过程
	QuickSort(arr, i + 1, end); // 继续处理右边的 ，这里是一个递归的过程
}

2.4 、算法分析

快速排序是不稳定排序，之所比较快，是因为相比冒泡排序，每次交换是跳跃式的。每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换，交换的距离就大的多了。因此总的比较和交换次数就少了，速度自然就提高了。当然在最坏的情况下，仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是 O(n²)，它的平均时间复杂度为 O(n * log n)。和归并排序一样，其在算法实现上采用了分治法与递归思想。