本文相关图片以及部分内容引自：

• 十大经典排序算法。
• 菜鸟教程

引言

• 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
• 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

算法稳定性：单次比较后，两个值相等的邻近元素的位置在排序后，相对位置没有改变。以[a,b c,d]举例说明如下：(b=c)
(1) 稳定： b在c之前，并且b=c，排序之后b的位置还是在c的前面。[a, b, c, d]
(2) 不稳定：b在c之前，并且b=c，排序之后b的位置在c的后面。[a, c, b, d]
算法复杂度:

1. 冒泡排序

冒泡排序 (Bubble Sort)：是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。
特点：
a. 重复遍历待排序的列表。
b. 比较相邻元素并交换它们，直到整个列表有序。
c. 每次遍历都会将最大的元素“冒泡”到列表的末尾。

代码实现：

#include <iostream>
using namespace std;

// 优化版
void bubbleSort(vector<int>& arr){
	int len = arr.size();
	for(int i=0; i<len; ++i){
		bool flag = false;
		for(int j =0;j<len-i-1;++j){
			if(arr[j]>arr[j+1]){
				std::swap(arr[j], arr[j+1]);
				flag= true;
			}
		}
		if(!flag) break;
	}
}

2. 快速排序

快速排序(quickSort)：是由东尼·霍尔所发展的一种排序算法。快速排序的最坏运行情况是 O(n²)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。
特点：
a. 从数列中挑出一个元素，称为 “基准”（pivot）。
b. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
c. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

代码实现：

#include <iostream>
using namespace std;

int partition(vector<int>& arr, int left, int right)
{
	int pivot = arr[left];
	int pLeft = left + 1;
	int pRight = right;
	while (pLeft <= pRight)
	{
		while (pLeft <= pRight && arr[pLeft] <= pivot) pLeft++;
		while (pLeft <= pRight && arr[pRight] >= pivot) pRight--;
		if (pLeft < pRight) {
			std::swap(arr[pLeft], arr[pRight]);
		}
	}

	std::swap(arr[left], arr[pRight]);
	return pRight;
}
void quicksort(vector<int>& arr, int left, int right)
{
	if (left >= right) return;
	int pivot = partition(arr, left, right);
	quicksort(arr, left, pivot - 1);
	quicksort(arr, pivot + 1, right);
}

3. 直接插入排序

插入排序 (Insertion Sort)：一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。类似于扑克牌整理。
特点：将待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。(如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。)

代码实现：

#include <iostream>
using namespace std;

//插入排序
void Insertsort(vector<int>& arr)
{
	for (int i = 1; i < arr.size(); ++i)
	{
		int mark = i;
		for (int j = i - 1; j >= 0; --j)
		{
			if (arr[mark] < arr[j])
			{
				std::swap(arr[mark--], arr[j]);
			}
		}
	}
}

4. 希尔排序

希尔排序 (Shell Sort)：基于插入排序，但通过在多个阶段对元素进行排序，使用逐渐缩小的增量进行多次插入排序。
给出一个示例分析希尔排序过程。

• 开始为乱序数组[8，6，1，7，3，5，4，2]。
  
• 初始增量gap = len/2 = 4，意味着数据被分为四组[8，3]，[6，5]，[1，4]，[7，2]。各组分别插入排序，小在前，大在后。
  
• 缩小增量gap = 4/2 =2，数据被分为两组[3，1，8，4]，[5，2，6，7]。同理再次排序。
  
• 缩小增量gap = 2/2 =1，数据排序后得到[1，2，3，5，4，6，8，7]。
  
• 通过局部调整，最终得到有序数组[1，2，3，4，5，6，7，8]。
  

代码实现：

#include <iostream>
using namespace std;

//希尔排序
void shellsort(vector<int>& arr)
{
	for (int grp = arr.size() / 2; grp >= 1; grp /= 2)
	{
		for (int i = grp; i < arr.size(); ++i)
		{
			int compval = arr[i];
			int j = i - grp;
			while (j >= 0 && arr[j] >= compval)
			{
				arr[j + grp] = arr[j];
				j -= grp;
			}
			arr[j + grp] = compval;
		}
	}
}

5. 选择排序

选择排序 (Selection Sort)：每次都在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

代码实现：

#include <iostream>
using namespace std;

void selectsort(vector<int>& arr)
{
	int minidx = 0;
	for (int i = 0; i < arr.size(); ++i)
	{
		minidx = i;
		for (int j = i + 1; j < arr.size(); ++j)
		{
			if (arr[j] < arr[minidx])
			{
				minidx = j;
			}
		}
		std::swap(arr[i], arr[minidx]);
	}
}

6. 堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列。
小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列。

上图转自一组动画彻底了解堆排序。

代码实现：

#include <iostream>
using namespace std;

void minHeap(vector<int>& arr, int n, int i) 
{
	int min = i;
	int left = 2 * i + 1;
	int right = 2 * i + 2;

	if (left < n && arr[left] < arr[min]) min = left;
	if (right < n && arr[right] < arr[min]) min = right;
	if (i != min) {
		swap(arr[i], arr[min]);
		minHeap(arr, n, min);
	}
}

void maxHeap(vector<int>& arr, int n, int i) 
{
	int max = i;
	int left = 2 * i + 1;
	int right = 2 * i + 2;

	if (left<n && arr[left]>arr[max]) max = left;
	if (right<n && arr[right]>arr[max]) max = right;
	if (i != max)
	{
		swap(arr[i], arr[max]);
		maxHeap(arr, n, max);
	}
}

void heapSort(vector<int>& arr)
{
	int n = arr.size();
	for (int i = n / 2 - 1; i >= 0; i--) 
	{
		maxHeap(arr, n, i);
		//minHeap(arr, n, i);
	}

	for (int i = n - 1; i >= 0; i--) {
		swap(arr[0], arr[i]);
		maxHeap(arr, i, 0);
		//minHeap(arr, i, 0);
	}
}

7. 归并排序

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
(1) 自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）。
(2) 自下而上的迭代。

代码实现：

#include <iostream>
using namespace std;

//归并排序
void merge(vector<int>& v, int left, int mid, int right)
{
	vector<int> v1(right - left + 1);
	int i = left, j = mid + 1, k = 0;
	while (i <= mid && j <= right)
	{
		v1[k++] = v[i] < v[j] ? v[i++] : v[j++];
	}
	while (i <= mid)v1[k++] = v[i++];
	while (j <= right)v1[k++] = v[j++];
	for (i = 0; i < v1.size(); ++i)
	{
		v[left + i] = v1[i];
	}
}
void mergesort(vector<int>& arr, int left, int right)
{
	if (left >= right) return;
	int mid = left + (right - left) / 2;
	mergesort(arr, left, mid);
	mergesort(arr, mid + 1, right);
	merge(arr, left, mid, right);
}

8. 计数排序

计数排序 (Counting Sort)：计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
应用场景：适用于范围已知且相对较小的整数排序。通过统计每个元素出现的次数来确定元素位置。

代码实现：

#include <iostream>
#include <vector>
using namespace std;

void countingSort(int arr[], int n) {
    int maxVal = *max_element(arr, arr + n);
    vector<int> count(maxVal + 1, 0);
    for (int i = 0; i < n; i++) {
        count[arr[i]]++;
    }
    int index = 0;
    for (int i = 0; i <= maxVal; i++) {
        while (count[i] > 0) {
            arr[index++] = i;
            count[i]--;
        }
    }
}

9. 基数排序

基数排序 (Radix Sort)是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

代码实现：

#include <iostream>
using namespace std;

int getMax(int arr[], int n) {
    int maxVal = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > maxVal) maxVal = arr[i];
    }
    return maxVal;
}

void countingSortForRadix(int arr[], int n, int exp) {
    int output[n];
    int count[10] = {0};
    for (int i = 0; i < n; i++) count[(arr[i] / exp) % 10]++;
    for (int i = 1; i < 10; i++) count[i] += count[i - 1];
    for (int i = n - 1; i >= 0; i--) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }
    for (int i = 0; i < n; i++) arr[i] = output[i];
}

void radixSort(int arr[], int n) {
    int maxVal = getMax(arr, n);
    for (int exp = 1; maxVal / exp > 0; exp *= 10) {
        countingSortForRadix(arr, n, exp);
    }
}

10. 桶排序

桶排序 (Bucket Sort)将元素分配到若干个桶中，每个桶内进行排序，最后将所有桶中的元素合并。
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：
(1) 在额外空间充足的情况下，尽量增大桶的数量。
(2) 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中。

1. 什么时候最快 ?
   当输入的数据可以均匀的分配到每一个桶中。
2. 什么时候最慢 ?
   当输入的数据被分配到了同一个桶中。

代码实现：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void bucketSort(float arr[], int n) {
    if (n <= 0) return;
    vector<float> buckets[n];
    for (int i = 0; i < n; i++) {
        int index = n * arr[i];
        buckets[index].push_back(arr[i]);
    }
    for (int i = 0; i < n; i++) {
        sort(buckets[i].begin(), buckets[i].end());
    }
    int index = 0;
    for (int i = 0; i < n; i++) {
        for (float val : buckets[i]) {
            arr[index++] = val;
        }
    }
}

基数排序：根据键值的每位数字来分配桶。
计数排序：每个桶只存储单一键值。
桶排序：每个桶存储一定范围的数值。

欢迎大家评论，点赞和关注，一起进步，加油！