本期是C++基础语法分享的第十五节，今天给大家来梳理一下十大排序算法前五个！

冒泡排序

冒泡排序思路：

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。

2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

3. 针对所有的元素重复以上的步骤，除了最后一个。

4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

示例：

// 冒泡排序void BubbleSort(vector<int>& v) {	int len = v.size();	for (int i = 0; i < len - 1; ++i)		for (int j = 0; j < len - 1 - i; ++j)			if (v[j] > v[j + 1]) 				swap(v[j], v[j + 1]);}// 模板实现冒泡排序template<typename T> //整數或浮點數皆可使用,若要使用物件(class)時必須設定大於(>)的運算子功能void bubble_sort(T arr[], int len) {	for (int i = 0; i < len - 1; i++)		for (int j = 0; j < len - 1 - i; j++)			if (arr[j] > arr[j + 1])				swap(arr[j], arr[j + 1]);}// 冒泡排序（改进版）void BubbleSort_orderly(vector<int>& v) {	int len = v.size();	bool orderly = false;	for (int i = 0; i < len - 1 && !orderly; ++i) {		orderly = true;		for (int j = 0; j < len - 1 - i; ++j) {			if (v[j] > v[j + 1]) {  // 从小到大				orderly = false;	// 发生交换则仍非有序				swap(v[j], v[j + 1]);			}		}	}}

选择排序思路：

1. 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置

2. 从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾

3. 以此类推，直到所有元素均排序完毕

示例：

void SelectionSort(vector<int>& v) {	int min, len = v.size();	for (int i = 0; i < len - 1; ++i) {		min = i;		for (int j = i + 1; j < len; ++j) {			if (v[j] < v[min]) {    // 标记最小的				min = j;			}		}		if (i != min)  // 交换到前面			swap(v[i], v[min]);	}}// 模板实现template<typename T> void Selection_Sort(std::vector<T>& arr) {	int len = arr.size();	for (int i = 0; i < len - 1; i++) {		int min = i;		for (int j = i + 1; j < len; j++)			if (arr[j] < arr[min])				min = j;		if(i != min)			std::swap(arr[i], arr[min]);	}}

插入排序思路：

1. 从第一个元素开始，该元素可以认为已经被排序

2. 取出下一个元素，在已经排序的元素序列中从后向前扫描

3. 如果该元素（已排序）大于新元素，将该元素移到下一位置

4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置

5. 将新元素插入到该位置后

6. 重复步骤2~5

示例：

// 插入排序void InsertSort(vector<int>& v){    int len = v.size();	for (int i = 1; i < len; ++i) {		int temp = v[i];        for(int j = i - 1; j >= 0; --j)        {            if(v[j] > temp)            {                v[j + 1] = v[j];                v[j] = temp;            }            else                break;        }	}}

快速排序思路：

1. 选取第一个数为基准

2. 将比基准小的数交换到前面，比基准大的数交换到后面

3. 对左右区间重复第二步，直到各区间只有一个数

// 快速排序（递归）void QuickSort(vector<int>& v, int low, int high) {	if (low >= high)		// 结束标志		return;	int first = low;		// 低位下标	int last = high;		// 高位下标	int key = v[first];		// 设第一个为基准	while (first < last)	{		// 将比第一个小的移到前面		while (first < last && v[last] >= key)			last--;		if (first < last)			v[first++] = v[last];		// 将比第一个大的移到后面		while (first < last && v[first] <= key)			first++;		if (first < last)			v[last--] = v[first];	}	// 基准置位	v[first] = key;	// 前半递归	QuickSort(v, low, first - 1);	// 后半递归	QuickSort(v, first + 1, high);}// ----------------------------------------------------// 模板实现快速排序（递归）template <typename T>void quick_sort_recursive(T arr[], int start, int end) {    if (start >= end)        return;    T mid = arr[end];    int left = start, right = end - 1;    while (left < right) {        while (arr[left] < mid && left < right)            left++;        while (arr[right] >= mid && left < right)            right--;        std::swap(arr[left], arr[right]);    }    if (arr[left] >= arr[end])        std::swap(arr[left], arr[end]);    else        left++;    quick_sort_recursive(arr, start, left - 1);    quick_sort_recursive(arr, left + 1, end);}template <typename T> //整數或浮點數皆可使用,若要使用物件(class)時必須設定"小於"(<)、"大於"(>)、"不小於"(>=)的運算子功能void quick_sort(T arr[], int len) {    quick_sort_recursive(arr, 0, len - 1);}// ----------------------------------------------------// 模板实现快速排序（迭代）struct Range {    int start, end;    Range(int s = 0, int e = 0) {        start = s, end = e;    }};template <typename T> // 整數或浮點數皆可使用,若要使用物件(class)時必須設定"小於"(<)、"大於"(>)、"不小於"(>=)的運算子功能void quick_sort(T arr[], const int len) {    if (len <= 0)        return; // 避免len等於負值時宣告堆疊陣列當機    // r[]模擬堆疊,p為數量,r[p++]為push,r[--p]為pop且取得元素    Range r[len];    int p = 0;    r[p++] = Range(0, len - 1);    while (p) {        Range range = r[--p];        if (range.start >= range.end)            continue;        T mid = arr[range.end];        int left = range.start, right = range.end - 1;        while (left < right) {            while (arr[left] < mid && left < right) left++;            while (arr[right] >= mid && left < right) right--;            std::swap(arr[left], arr[right]);        }        if (arr[left] >= arr[range.end])            std::swap(arr[left], arr[range.end]);        else            left++;        r[p++] = Range(range.start, left - 1);        r[p++] = Range(left + 1, range.end);    }}

堆排序：（最大堆，有序区）。从堆顶把根卸出来放在有序区之前，再恢复堆。

#include <iostream>#include <algorithm>using namespace std;// 堆排序：（最大堆，有序区）。从堆顶把根卸出来放在有序区之前，再恢复堆。void max_heapify(int arr[], int start, int end) {	//建立父節點指標和子節點指標	int dad = start;	int son = dad * 2 + 1;	while (son <= end) { //若子節點指標在範圍內才做比較		if (son + 1 <= end && arr[son] < arr[son + 1]) //先比較兩個子節點大小，選擇最大的			son++;		if (arr[dad] > arr[son]) //如果父節點大於子節點代表調整完畢，直接跳出函數			return;		else { //否則交換父子內容再繼續子節點和孫節點比較			swap(arr[dad], arr[son]);			dad = son;			son = dad * 2 + 1;		}	}}void heap_sort(int arr[], int len) {	//初始化，i從最後一個父節點開始調整	for (int i = len / 2 - 1; i >= 0; i--)		max_heapify(arr, i, len - 1);	//先將第一個元素和已经排好的元素前一位做交換，再從新調整(刚调整的元素之前的元素)，直到排序完畢	for (int i = len - 1; i > 0; i--) {		swap(arr[0], arr[i]);		max_heapify(arr, 0, i - 1);	}}int main() {	int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };	int len = (int) sizeof(arr) / sizeof(*arr);	heap_sort(arr, len);	for (int i = 0; i < len; i++)		cout << arr[i] << ' ';	cout << endl;	return 0;}

今天的分享就到这里了，大家要好好学C++哟~

写在最后：对于准备学习C/C++编程的小伙伴，如果你想更好的提升你的编程核心能力（内功）不妨从现在开始！

编程学习书籍分享：

编程学习视频分享：

整理分享（多年学习的源码、项目实战视频、项目笔记，基础入门教程）

欢迎转行和学习编程的伙伴，利用更多的资料学习成长比自己琢磨更快哦！

对于C/C++感兴趣可以关注小编在后台私信我：【编程交流】一起来学习哦！可以领取一些C/C++的项目学习视频资料哦！已经设置好了关键词自动回复，自动领取就好了！