作为最简单的排序算法之一，冒泡排序给我的感觉就像 Abandon 在单词书里出现的感觉一样，每次都在第一页第一位，所以最熟悉。冒泡排序还有一种优化算法，就是立一个 flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序，就可以直接退出排序了。但这种改进对于提升性能来说并没有什么太大作用。

如果需要排倒叙，只需要更改一下比较时的大于小于号就行。

1、算法步骤

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

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

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

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

2、动图演示

3、什么时候最快最慢

最快：当输入的数据已经是正序时（都已经是正序了那我还用你冒泡排序干啥）

最慢：当输入的数据是反序时（写一个 for 循环反序输出数据不就行了，干嘛要用你冒泡排序呢，我是闲的吗）。

4、代码实现


//冒泡排序
void Swap(int& a, int& b)
{
	int c = a;
	a = b;
	b = c;
}
 
 
void Bubble_sort(int* arr, int len)
{
	int i, j;
	for ( i = 0; i < len; i++)
	{
		for (j = 0; j < len - i - 1; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				Swap(arr[j], arr[j + 1]);
			}
		}
	}
}

二、选择排序

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度，是一种不稳定的排序。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

1、算法步骤

选择排序的基本思想是每一次从待排序的数据元素在选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部排序的数据元素排完。

2、动图演示

3、代码实现


void Swap(int& a, int& b)
{
	int c = a;
	a = b;
	b = c;
}
 
//选择排序
void Selection_sort(int* arr, int len)
{
	for (int i = 0; i < len; i++)
	{
		int min = i;
		for (int j = i + 1; j < len; j++)
		{
			if (arr[min] > arr[j])
			{
				min = j;
			}
		}
		Swap(arr[min], arr[i]);
	}
}

当然，这里也有一个优化方式，就是同时找最大最小，同时调换到最后面与最前面。


void Selection_sort(int* arr, int len)
{
	int begin = 0, end = len - 1;
	while (begin < end)
	{
		int max = begin, min = begin;
		for (int i = begin + 1; i <= end; i++)
		{
			if (arr[min] > arr[i])
			{
				min = i;
			}
			if (arr[max] < arr[i])
			{
				max = i;
			}
		}
		Swap(arr[max], arr[end]);//如果end与min重合了，或者max与begin重合了，就会出现一个位置多次被交换数值，导致数值对不上顺序的情况
		//由于max与end交换在前，倘若min与end重合，第一次就相当于max与min交换了一次，原本的min指向了最大值，但后面的交换min所指的最大值会被交换到begin的位置上，使顺序出错
		if (min == end)
		{
			min = max;//纠正，把min所指向的位置移到了最小值所在地
		}
 
		Swap(arr[min], arr[begin]);
		//倘若min与begin交换在前，就是讨论max是否与begin重合，然后修改max为正确的值了
		begin++;
		end--;
	}
}

但是这样写就要注意是否出现一个位置多次交换导致出错的问题了。

三、插入排序

直接插入排序是一种简单的插入排序法，其基本思想是：

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录单插入完为止，得到一个新的有序序列。

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。

1、算法步骤

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

2、动图演示

3、代码实现


//插入排序
void Swap(int& a, int& b)
{
	int c = a;
	a = b;
	b = c;
}
 
void Insert_sort(int* arr, int len)
{
	for (int end = 0; end < len - 1; end++)
	{
		int i = end + 1;
		while (i > 0 && arr[i] < arr[i - 1])
		{
			Swap(arr[i], arr[i - 1]);
			i--;
		}
	}
}

四、希尔排序

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

1、基本思想

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。

2、希尔排序的特性总结

希尔排序是对直接插入排序的优化
当gap值>1时都是预排序，目的是为了让数组更加接近有序。当gap==1时，数组已经接近有序，这样就会很快。
希尔排序的时间复杂度不好计算，并不固定。

3、算法步骤

选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；

按增量序列个数 k，对序列进行 k 趟排序；（我们通常初识定义一个一个值gap，每次预排序之后对gap不断除以二，在gap==1之前使循环不断进行）

每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

4、动图演示

5、代码实现


//希尔排序
void Shell_sort(int* arr, int len)
{
	int gap = len;
	while (gap > 1)
	{
		gap /= 2;
		for (int i = 0; i < len - gap; i++)//gap相当于是当前分出来的组数，gap组，总共len个数，只需要len-gap次排序就行
		{
			int end = i;
			int tmp = arr[end + gap];//tmp的值固定为了arr[end+gap]，当end值变的时候，tmp也会跟着改变
			while (end >= 0)
			{
				if (arr[end] > tmp)
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = tmp;//if出循环的话，end最后减了gap，现在加上gap相当于是让arr[end]等于tmp，交换了值。break出循环，两值本来就相等
		}
	}
}

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/weixin_40725706/article/detail/415579