排序算法：比较排序

标签：arr int 插入排序 算法 复杂度 排序 比较

算法简介：排序

排序是一个非常经典的问题，它以特定顺序（递增、非递减（递增或扁平））对数组（或列表）的项目（可以比较，例如整数、浮点数、字符串等）进行重新排序)、递减、非递增（递减或平坦）、字典式等）。

有许多不同的排序算法，每一种都有自己的优点和局限性。

排序通常用作各种计算机科学课程中的介绍性问题，以展示一系列算法思想。

以下所以排序都以升序为例.

冒泡排序

冒泡排序（英语：Bubble Sort）又称为泡式排序，是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

算法：

冒泡排序算法的运作如下：

1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

助记码

参考：冒泡排序 - 维基百科，自由的百科全书

 i∈[0,N-1)               //循环N-1遍
   j∈[0,N-1-i)           //每遍循环要处理的无序部分
     swap(j,j+1)          //两两排序（升序/降序）

由于它的简洁，冒泡排序通常被用来对于程序设计入门的学生介绍算法的概念。

冒泡排序图示：

每一轮冒泡，会将无序序列中最大的数"浮"到无序序列的最后一个位置，此位置成为"有序"，并且为有序序列中的最小值，有序序列的个数增加1，无序序列的个数减1，当只有一个位置是无序时，整个数组有序。

代码实现：

void swap(int* s1, int* s2)
{
	int tmp = *s1;
	*s1 = *s2;
	*s2 = tmp;
}

void BubbleSort(int* arr, int sz)
{
	int i = 0;
	for (i = 0; i < sz - 1; i++)
	{
		int flag = 0;//flag来标记是否还需要继续排序
		int j = 0;
		for (j = 0; j < sz - 1 - i; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				flag = 1;//标记仍需排序
				swap(arr + j + 1, arr + j);
			}		
		}
		if (flag == 0)//如果if一次都没进去，说明数组已经有序，直接退出
			break;
	}
}

算法分析：

• 最坏时间复杂度

​ 最坏时间复杂度是序列为降序，设无序序列有 x 个，则每轮冒泡都需要交换 x - 1次，结果即为等差数列求和

​ $\sum\limits_{x=1}^{n - 1}$x = n(n - 1) / 2，即O(n2)

• 最优时间复杂度

​ 序列本就为有序序列，遍历一次即跳出，即O(n)

• 平均时间复杂度

​ O(n2)

• 空间复杂度

​ O(1)

总结：

冒泡排序对n个项目需要O(n2)的比较次数，且可以原地排序。尽管这个算法是最简单了解和实现的排序算法之一，但它对于包含大量的元素的数列排序是很没有效率的。

插入排序

插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序)，因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

Insertion Sort 和打扑克牌时非常相似，从牌桌上逐一拿起扑克牌，在手上排序的过程相同。

举例：

摸牌顺序: {5 2 4 6 1 3}。

首先拿起第一张牌, 手上有 {5}。

拿起第二张牌 2, 把 2 insert 到手上的牌 {5}, 得到 {2 5}。

拿起第三张牌 4, 把 4 insert 到手上的牌 {2 5}, 得到 {2 4 5}。

以此类推。

算法：

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置后
6. 重复步骤2~5

插入排序图示：

代码实现：

void InsertSort(int* arr, int sz)
{
	int i = 0;
	for (i = 1; i < sz; i++)
	{
		int j = 0;
		int tmp = arr[i];
		for (j = i - 1; j >= 0; j--)
		{
			if (arr[j] < tmp)//遇到了比目标小的数，不在向前遍历，break
				break;
			arr[j + 1] = arr[j];
		}
		arr[j + 1] = tmp;//插入到最后一个比较数据的后面
	}
}

算法分析：

• 最坏时间复杂度

​ 序列为降序时，每插入下标为 i 的值，需要移动i - 1个数据，因此也是等差数列求和，即O(n2)

• 最优时间复杂度

​ 序列为升序时，每次插入都不需要移动元素，即O(n)

• 平均时间复杂度

​ O(n2)

• 空间复杂度

​ O(1)

直接插入排序的特性总结：

1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定

插入排序对几乎有序的序列排序的效率很高，接近于O(n).

插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千；或者若已知输入元素大致上按照顺序排列，那么插入排序还是一个不错的选择。 插入排序在工业级库中也有着广泛的应用，在STL的sort算法和stdlib的qsort算法中，都将插入排序作为快速排序的补充，用于少量元素的排序（通常为8个或以下）。

Shell排序

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

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

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

如图几乎有序序列有着先行排序的效率

因此我们可以先对要排序的数组进行预排序，让他变成几乎有序的状态。

以升序为例，我们的目的是：

• 让大的数更快的到后面
• 让小的数更快的到前面

普通的插入排序是从前到后依次插入，跨度为1，那么为了更快我们可以增加跨度。（跨度越大意味着每次插入数据只需要移动较少的次数，便可以大致到它排序后的位置）

希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。

假设有一个很小的数据在一个已按升序排好序的数组的末端。如果用复杂度为O(n2)的排序（冒泡排序或插入排序），可能会进行n次的比较和交换才能将该数据移至正确位置。而希尔排序会用较大的步长移动数据，所以小数据只需进行常数次比较和交换即可到正确位置。

原始数组：

• 长度length = 10

• 初始步长 gap = length / 2 = 5

​ 即两个一组，被分为了五组：

​ 这和大家军训时教官让大家挨着重复报数 0 或者 1 一样，喊到1的为一组，喊到0的为一组；

​ （同一条线上的为一组）

​ 只不过这里是从0报数到4，那么报数相同的分为一组，有不同的5个数，那就是5组咯。

​ 即步长为多少，就分为多少组。

• 对上面5组数据分别进行插入排序，例如第一组【8，3】，经过插入排序就变成了【3，8】(升序)。

​ 那么每一组经过排序后就成为了有序序列。

​ 结果如下图：

​

​ 可以看到，每一组中较小的数都移动到了前半部分，而较大的数则移动到了后半部分。

• 继续缩小步长 gap = length / 2 / 2 = 2

​ 即被分为了两组，【3】【5】分别是这两组数组的头部。

​ 再对以上两组分别进行插入排序

​ 例如第一组：【3，1，0，9，7】，经过插入排序后变成【0，1，3，7，9】。

​ 两组数据分别排序后结果如图：

​

​ 此时整个数组已经近乎有序，大的数集中在数组尾部，小的数集中在数组头部。

​ 因此，就可以对整个数组进行直接插入排序即可完成升序排序。

​ 继续缩小步长，使gap = 1即可，即整个数组为一组，进行直接插入排序，因为数组已经几乎有序，只需要进行 少量调整即可完成排序。

​ 希尔排序示意图：

代码实现：

void ShellSort(int* arr, int sz)
{
	for (int gap = sz / 2; gap > 0; gap /= 2)
	{
		for (int i = gap; i < sz; i++)//每一次的预排序时间复杂度大致是O(n)
		{
			int tmp = arr[i];
			int j = 0;
			for (j = i - gap; j >= 0; j -= gap)
			{
				if (arr[j] > tmp)				
					arr[j + gap] = arr[j];				
				else
					break;
			}
			arr[j + gap] = tmp;
		}
	}
}

官方建议是步长选择gap = n / 3 + 1，这里用的n / 2。

算法分析：

• 平均时间复杂度

​ 根据步长序列的不同而不同。

• 最坏时间复杂度

​ 根据步长序列的不同而不同，已知最好的：O(n log²(n))

• 最优时间复杂度

​ O(n)

• 空间复杂度

​ O(1)

希尔排序的特性总结：

1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定：
4. 稳定性：不稳定

步长的选择是希尔排序的重要部分。只要最终步长为1任何步长序列都可以工作。算法最开始以一定的步长进行排序。然后会继续以一定步长进行排序，最终算法以步长为1进行排序。当步长为1时，算法变为普通插入排序，这就保证了数据一定会被排序。

选择排序

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多(n - 1)次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

算法实现：

void SelectionSort(int* arr, int sz)
{
	int left = 0;
	int right = sz - 1;
	while (left < right)
	{
		int minid = left;
		for (int i = left; i <= right; i++)
		{	//每次挑出最小的值的索引
			if (arr[i] < arr[minid])
				minid = i;
		}
		swap(arr + left, arr + minid);
		left++;
	}
}
//优化
void SelectionSort(int* arr, int sz)
{
	int left = 0;
	int right = sz - 1;
	while (left < right)
	{
		int i = 0;
		int minid = left;
		int maxid = left;
		for (i = left + 1; i <= right; i++)
		{	//每次挑出最小的和最大的
			if (arr[i] > arr[maxid])
				maxid = i;
			if (arr[i] < arr[minid])
				minid = i;
		}
		if (left == maxid)//如果minid和left的交换会影响maxid的下标，则需要修正maxid
			maxid = minid;
		swap(arr + minid, arr + left);
		swap(arr + maxid, arr + right);
		left++;
		right--;
	}
}

算法分析：

• 最坏时间复杂度

​ 序列为降序时，找到最小值需要无序序列的元素个数，寻找 n - 1次即可，总次数为等差数列求和，即O(n2)

• 最优时间复杂度

​ 序列为升序时，和最坏情况相同，即O(n2)，虽然如此，但没有交换操作。

• 平均时间复杂度

​ O(n2)

• 空间复杂度

​ O(1)

直接选择排序的特性总结：

1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

原地操作和少量的数据交换几乎是选择排序的唯二优点，当空间复杂度要求较高时，可以考虑选择排序；实际适用的场合非常罕见。

如果数组完全有序，冒泡内循环的交换一次都不会执行，而选择排序每次还要遍历并且和本身交换一次，此时冒泡效率高。但这种情况极少，所以丼从算法的角度看，选择优于冒泡。

总体效率体来说 ，希尔排序 > 插入排序 > 选择排序 > 冒泡排序

标签：arr,int,插入排序,算法,复杂度,排序,比较
From： https://www.cnblogs.com/ncphoton/p/16950870.html