• 十种经典排序算法总结

    一、冒泡排序（Bubble Sort）

    为位置找元素的过程，遍历所有的数据，每次对相邻元素进行两两比较（稳定排序的基础），如果顺序和预先规定的顺序不一致，则进行位置交换；这样一次遍历会将最大的沉到底部或最小的数据上浮到顶端，一轮之后为序列的底部或顶端位置找到元素，之后再重复同样的操作，直到所有的数据有序。数据是反序时，耗费时间最长O(n²)；数据是正序时，耗费时间最短O(n)。

    平均时间复杂度为O(n²)，空间复杂度为O(1)，是一种稳定的排序算法。

    • 把最大的沉下去
    vector<int> BubbleSort(vector<int>& array) {
	if (0 == array.size() || 1 == array.size()){
		return array;
	}

	for (size_t i = array.size() - 1; i > 0; i--) //为每一轮的底部找元素
	{
		for (size_t j = 0; j < i; j++) 
		{
			if (array[j] > array[j + 1])		  //两两比较，若逆序,则交换
			{
				swap(array[j], array[j + 1]);
			}
		}
	}

	return array;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 把最小的冒上来
    vector<int> BubbleSort2(vector<int>& array) {
	if (0 == array.size() || 1 == array.size()) {
		return array;
	}

	for (size_t i = 0; i < array.size(); i++)	  //为每一轮的顶端找元素
	{
		for (size_t j = array.size() - 1; j > i; j--)
		{
			if (array[j] < array[j - 1])		  //两两比较，若逆序,则交换
			{
				swap(array[j], array[j - 1]);
			}
		}
	}

	return array;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    二、选择排序（Selection Sort）

    为位置找元素的过程，每一趟在n-i+1（i=1，2，…,n-1）个记录中选取关键字最小的记录作为有序序列中的第i个记录。遍历所有数据，先在数据中找出最大或最小的元素，放到序列的起始（不是相邻两个两两比较，不是稳定排序）；然后再从余下的数据中继续寻找最大或最小的元素，依次放到序列中直到所有数据有序。原始数据的排列顺序不会影响程序耗费时间O(n²)，相对费时，不适合大量数据排序。

    平均时间复杂度为O(n²)，空间复杂度为O(1)，是一种不稳定的排序算法。

    vector<int> SelectionSort(vector<int>& array) {
	if (0 == array.size() || 1 == array.size()) {
		return array;
	}

	for (size_t i = 0; i < array.size(); i++)	  //为每一轮的顶端找元素
	{
		int minindex = i;
		for (size_t j = i + 1; j < array.size(); j++)
		{
			if (array[minindex] > array[j])
			{
				minindex = j;					//找到该轮次最小值下标
			}
		}
		swap(array[i], array[minindex]);		//为第i个位置选择该轮次最小元素
	}
	return array;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    三、快速排序（Quick Sort）

    为元素找位置的过程，快速排序采用分治法。首先从数列中挑出一个元素作为中间值（所以第一个元素对算法的效率有直接影响），依次遍历数据，所有比中间值小的元素放在左边，所有比中间值大的元素放在右边（不是稳定排序）。然后按此方法对左右两个子序列分别进行递归操作，直到所有数据有序。最理想的情况是，每次划分所选择的中间数恰好将当前序列几乎等分（均匀排布），整个算法的时间复杂度为O(n logn)。 最坏的情况是，每次所选的中间数是当前序列中的最大或最小元素（正序和逆序都是最坏），整个排序算法的时间复杂度为O(n²)。

    平均时间复杂度为O(n logn)，空间复杂度为O(logn)，是一种不稳定的排序算法。

    void QuickSort(vector<int>& array, size_t ileft, size_t iright) {
	if (0 == array.size() || 1 == array.size()) {
		return;
	}
	size_t i = ileft, j = iright, temp = array[iright];	//temp中存的就是基准数(轴) 
	if (ileft >= iright) {
		return;
	}

	while (i != j) {
		while (array[i] <= temp && i < j) {
			i++;
		}

		while (array[j] >= temp && i < j) {
			j--;
		}

		if (i < j) {
			swap(array[i], array[j]);
		}
	}

	//为基准数array[iright]找到位置，且左边的都不大于它，右边的都不小于它
	swap(array[i], array[iright]);

	QuickSort(array, ileft, i -1);
	QuickSort(array, i+1, iright);
	
	return;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31

    四、插入排序（Insertion Sort）

    将前i个（初始为1）数据假定为有序序列，依次遍历数据，将当前数据插入到前述有序序列的适当位置，形成前i+1个有序序列，依次遍历完所有数据，直至序列中所有数据有序。从而实现从局部有序到整体有序。数据是反序时，耗费时间最长O(n²)；数据是正序时，耗费时间最短O(n)。适用于部分数据已经排好的少量数据排序。

    平均时间复杂度为O(n²)，空间复杂度为O(1)，是一种稳定的排序算法。

    void InsertionSort(vector<int>& array)
{
	if (0 == array.size() || 1 == array.size()) {
		return;
	}

	for (size_t i = 0; i < array.size() - 1; i++) //array[i]为已排好序的最后一个元素
	{
		int icurrent = array[i + 1];
		int preindex = i;
		while (preindex >= 0 && icurrent < array[preindex]) {
			array[preindex + 1] = array[preindex]; //元素依次后移，为当前待插入元素腾位置
			preindex--;
		}
		array[preindex+1] = icurrent;		//找到当前元素的位置，此时array[i+1]为已排好序的最后一个元素
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    五、希尔排序（Shell Sort）

    希尔排序也称递减增量排序，是对插入排序的改进，以牺牲稳定性的方法提高效率。基本思路是先将整个数据序列分割成若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时，再对全部数据进行依次直接插入排序，直至所有数据有序。希尔排序算法的性能与所选取的分组长度序列有很大关系，复杂度下界为O(n log²n)，在中等规模的数据中表现良好。我们选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2…1}，称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。

    平均时间复杂度为O(n^3/2)，空间复杂度为O(1)，是一种不稳定的排序算法。

    void ShellSort(vector<int>& array)
{
	if (0 == array.size() || 1 == array.size()) {
		return;
	}

	int gap = array.size() / 2;
	while (gap) {
		for (size_t i = gap; i < array.size(); i++) 
		{
			int icurrent = array[i];
			int preindex = i - gap;
			while (preindex >= 0 && icurrent < array[preindex]) {
				array[preindex + gap] = array[preindex]; //元素依次后移，为当前待插入元素腾位置
				preindex -= gap;
			}
			array[preindex + gap] = icurrent;		
		}
		gap /= 2;
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    六、堆排序（Heap Sort）

    堆排序利用堆这种近似完全二叉树的数据结构进行排序。是对简单选择排序的优化。堆的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。以大根堆为例，堆中的最大值总是位于根节点。首先将待排序的n个数据构造为大根堆，将顶端数据与末尾数据进行交换并将堆的尺寸减一，然后剩余n-1个数据再次构造为大根堆，再次交换，再次缩减，直至所有数据有序。建堆复杂度为O(n)，调整堆复杂度为O(n logn)。最优的情况为所有叶节点铺满最底层，最差情况所有叶节点都没铺满，对复杂度的影响在常数级别，时间复杂度均为O(n logn)。

    还有一个基本概念：查找数组中某个数的父结点和左右孩子结点，比如已知索引为i的数，那么
    1. 父结点索引：(i-1)/2（这里计算机中的除以2，省略掉小数）
    2. 左孩子索引：2i+1
    3. 右孩子索引：2i+2

    所以上面两个数组可以脑补成堆结构，因为他们满足堆的定义性质：
    大根堆：arr(i)>arr(2i+1) && arr(i)>arr(2i+2)
    小根堆：arr(i)

    平均时间复杂度为O(n logn)，空间复杂度为O(1)，是一种不稳定的排序算法。

    //构造大根堆（通过新插入的数上升）
static void heapInsert(vector<int>& arr)
{
	for (int i = 0; i < arr.size(); i++) {
		//当前插入的索引
		int currentIndex = i;
		//父结点索引
		int fatherIndex = (currentIndex - 1) / 2;
		//如果当前插入的值大于其父结点的值,则交换值，并且将索引指向父结点
		//然后继续和上面的父结点值比较，直到不大于父结点，则退出循环
		while (arr[currentIndex] > arr[fatherIndex]) {
			//交换当前结点与父结点的值
			swap(arr[currentIndex], arr[fatherIndex]);
			//将当前索引指向父索引
			currentIndex = fatherIndex;
			//重新计算当前索引的父索引
			fatherIndex = (currentIndex - 1) / 2;
		}
	}
}


//将剩余的数构造成大根堆（通过顶端的数下降）
static void heapify(vector<int>& arr, int index, int isize) {
	int ileft = 2 * index + 1;
	int iright = 2 * index + 2;

	while (ileft < isize) {
		int largestIndex;
		//判断孩子中较大的值的索引（要确保右孩子在size范围之内）
		if (arr[ileft] < arr[iright] && iright < isize) {
			largestIndex = iright;
		}
		else {
			largestIndex = ileft;
		}
		//比较父结点的值与孩子中较大的值，并确定最大值的索引
		if (arr[index] > arr[largestIndex]) {
			largestIndex = index;
		}
		//如果父结点索引是最大值的索引，那已经是大根堆了，则退出循环
		if (index == largestIndex) {
			break;
		}
		//父结点不是最大值，与孩子中较大的值交换
		swap(arr[largestIndex], arr[index]);
		//将索引指向孩子中较大的值的索引
		index = largestIndex;
		//重新计算交换之后的孩子的索引
		ileft = 2 * index + 1;
		iright = 2 * index + 2;
	}
}


void HeapSort(vector<int>& array)
{
	if (0 == array.size() || 1 == array.size()) {
		return;
	}

	//构造大根堆
	heapInsert(array);
	int isize = array.size();
	while (isize > 1) {
		//固定最大值
		swap(array[0], array[isize - 1]);
		isize--;
		//将剩余的数构造成大根堆
		heapify(array, 0, isize);
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72

    另一种写法：

    /// 大顶堆调整方法
void HeapAdjust(vector<int>& array, size_t istart, size_t iend)
{
	//istart代表需要调整的节点
	//iend表示当前大顶堆的最后一个节点的下标位置
	size_t ifatherindex = istart;
	size_t isonindex = ifatherindex * 2 + 1;//这里isonindex是初始节点的左孩子

	while (isonindex <= iend)
	{
		//如果右孩子的值比左孩子大，那么son=右孩子，因为要找到子节点中最大的那个和父节点交换
		if (isonindex + 1 <= iend && array[isonindex] < array[isonindex + 1]) {
			isonindex++;
		}
			
		if (array[ifatherindex] > array[isonindex])//如果父节点大于两孩子中最大的那个，那就没什么事了，返回
		{
			break;
		}
		else
		{
			//否则交换这父子两个节点的值
			swap(array[ifatherindex], array[isonindex]);
			//继续往下遍历，因为父节点现在在子节点上，其值可能会比子节点的子节点（孙子节点）小，需要继续往下检查，直到end结束
			ifatherindex = isonindex;
			isonindex = ifatherindex * 2 + 1;
		}
	}
}

void HeapSort1(vector<int>& array)
{
	//初始化二叉树，从第一个非叶子节点开始调整整个树
	int ulen = array.size();
	for (int i = (ulen - 1 - 1) / 2; i >= 0; i--) {
		HeapAdjust(array, i, ulen - 1);
	}

	//初始化结束后，就可以将堆顶的元素与最后一个节点交换，交换后最后一个节点就被排除在二叉堆外了
	for (int i = ulen - 1; i > 0; i--){
		swap(array[0], array[i]);
		//然后由于堆顶元素变化了，那么我们就需要继续调整，直到结束
		HeapAdjust(array, 0, i - 1);
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45

    七、归并排序（Merge Sort）

    该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是稳定排序。
    归并操作的基本步骤如下：
    1.申请两个与已经排序序列相同大小的空间，并将两个序列拷贝其中；
    2.设定最初位置分别为两个已经拷贝排序序列的起始位置，比较两个序列元素的大小，依次选择相对小的元素放到原始序列；
    3.重复2直到某一拷贝序列全部放入原始序列，将另一个序列剩下的所有元素直接复制到原始序列尾。

    设归并排序的当前区间是R[low…high]，分治法的三个步骤是：

    1. 分解：将当前区间一分为二，即求分裂点
    2. 求解：递归地对两个子区间R[low…mid]和R[mid+1…high]进行归并排序；
    3. 组合：将已排序的两个子区间R[low…mid]和R[mid+1…high]归并为一个有序的区间R[low…high]。
      递归的终结条件：子区间长度为1（一个记录自然有序）。
      算法示意图：
      在这里插入图片描述
    vector<int> MergeArr(vector<int> leftarr, vector<int>  rightarr) 
{
	vector<int> resultarr(leftarr.size() + rightarr.size());
	for (size_t index = 0, i = 0, j = 0; index < resultarr.size(); index++)
	{
		if (i >= leftarr.size()) 
		{
			resultarr[index] = rightarr[j++];
		}
		else if (j >= rightarr.size()) 
		{
			resultarr[index] = leftarr[i++];
		}
		else if (leftarr[i] > rightarr[j])
		{
			resultarr[index] = rightarr[j++];
		}
		else 
		{
			resultarr[index] = leftarr[i++];
		}
	}
	return resultarr;
}


vector<int> MergeSort(vector<int> array)
{
	if (array.size() < 2)
	{
		return array;
	}

	int mid = array.size() / 2;
	vector<int> leftarr(mid);
	size_t i = 0;
	for (; i < mid; i++) 
	{
		leftarr[i] = array[i];
	}

	vector<int> rightarr(array.size() - mid);
	for (size_t j = 0; i < array.size(); i++)
	{
		rightarr[j++] = array[i];
	}

	return MergeArr(MergeSort(leftarr), MergeSort(rightarr));
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49

    推荐一篇非常好的博客：
    https://zhanghaiyang.blog.csdn.net/article/details/100136531

  • 相关阅读:
    0.泛型基础学习
    python经典百题之用*号输出字母C的图案
    【API 管理】什么是 API 管理，为什么它很重要？
    【博士每天一篇文献-算法】Progressive Neural Networks
    【MySQL】什么是索引？如何选择索引类型？
    Nginx纯前端服务器部署
    前端该如何优雅地Mock数据
    springboot+vue 架构 （一）
    确保软件供应链安全，不容忽略的三大步骤
    8.Vue3虚拟节点的实现
  • 原文地址：https://blog.csdn.net/chanlp129/article/details/126441115