数据结构之排序一

1.排序

一.概念及其分类

二.排序的稳定性

2.插入排序

一.基本思想

二.插入排序的实现

复杂度

稳定性的分析

3.希尔排序

一.预排序代码的实现

二.希尔排序代码实现

复杂度分析

4.clock函数

1.排序

一.概念及其分类

说到排序，我们都不陌生，一些基本的排序，比如冒泡，堆排等等

排序的概念呢则是：排序就是将一组杂乱无章的数据按照一定的规律（升序或降序）组织起来。

常见的排序算法

加入排序
a. 直接插入排序
b. 希尔排序
选择排序
a. 选择排序
b. 堆排序
交换排序
a. 冒泡排序
b. 快速排序
归并排序
a. 归并排序

二.排序的稳定性

稳定性：稳定排序算法会让原本有相等键值的纪录维持相对次序。也就是如果一个排序算法是稳定的，当有两个相等键值的纪录R和S，且在原本的列表中R出现在S之前，在排序过的列表中R也将会是在S之前。

简单来说就是，两个数字AB（A在B的前边），如果经过排序代码后，A仍就在B的前边，那么这个排序就是稳定的，反之不稳定。

2.插入排序

一.基本思想

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

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

实际中我们玩扑克牌时，就用了插入排序的思想

二.插入排序的实现

当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与 array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移

首先构造函数

void InsertSort(int *a,int n);

比方说我们现在有五个数字，现在进行一个插入排序

那么我们将end+1的数字定义为tmp

当tmp大于end时，tmp就往前到end的前面
然后end-1，再与tmp进行比较，知道tmp变成相比较之下更大的数字

这里还有另一种情况

当我们的tmp比前边的都要小时，如果不及时制止

那么就会出现越界的情况

这样我们的tmp就越界了，运行后就会崩

所以如果我们只考虑实现单趟的插入排序代码：

void InsertSort(int* a, int n)
{
	int end;
	int tmp = a[end + 1];
	while (end >= 0)
	{
		if (tmp < a[end])
		{
			a[end + 1] = a[end];
			end--;
		}
		else
		{
			break;
		}
		a[end + 1] = tmp;
	}
}

这里跳出循环有两种情况：

1.找到了所需的插入位置：当tmp大于a[end]时，这是就会跳出循环
2.tmp小于前边的所以数：当tmp在是数中最小的数字时，这是tmp就会不断地往前移动，直到成为整个序列的起始位

在这两种跳出循环的情况下，我们总是需要执行a[end+1]=tmp来将tmp元素放置到正确的位置上。因为无论是找到合适的插入点还是tmp成为新的最小元素，我们都需要将它实际插入到有序序列中，这就是为什么这行代码放在循环之外，确保跳出循环后，我们执行最终的插入动作。

接下来我们去考虑整体排序：

因为上边的代码是单趟的排序

如果想要整体排序，那么就需要进行一个循环去实现整体的排序

void InsertSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
	}
	
		a[end + 1] = tmp;
	}
}

在这里我们进行了一个for循环，并且将end赋值为i

这样就相当于从一开始的两个数进行排序，当i的值不断增大，排序也就不断进行，同时其范围也在不断进行

注意这里的i需要小于n-1，不能是n

因为当i小于n的时候，这是end也就是n，而end+1则越界了，程序会崩

需要注意范围

测试一下

这样就测试完成了

接下来看一看时间复杂度

复杂度

插入排序算法的时间复杂度取决于输入数组中元素的初始排序状态：

最坏情况：这时数组是完全逆序的，那么每次插入操作都需要将元素移到已排序部分的开头。这就意味着对于第i个元素，可能需要进行i次比较和移动。这种情况下，算法的时间复杂度是O(N2)，因为需要进行总计1 + 2 + 3 + … + (n-1)次比较，这是一个n(n-1)/2的等差数列
最好情况：这种情况发生在数组已经完全有序时。在这种情况下，每次比较后，很快就会找到插入位置（在已排序元素的末尾），不需要进行额外的移动。因此，最好情况下插入排序的时间复杂度是O(N)，因为外层循环只会遍历一次数组，内层循环不会进行任何实际的比较和移动操作。
插入排序的空间复杂度为O(1)，因为它是一个原地排序算法，不需要额外的存储空间来排序。

稳定性的分析

排序初始时，认为第一个元素自成一个已排序的序列
从第二个元素开始，取出未排序的下一个元素，在已排序的序列中从后向前扫描
如果当前扫描到的元素大于新元素（待插入），那么将扫描到的元素向后移动一个位置
重复步骤3，直到找到一个元素小于或等于新元素的位置，或者序列已经扫描完毕
将新元素插入到这个位置后面
在步骤4中，插入排序的算法逻辑保证了如果存在相等的元素，新元素（待插入）将被放置在相等元素的后面。因此，原始顺序得以保持，插入排序被认为是稳定的

3.希尔排序

希尔排序是一种基于插入排序的算法，通过引入增量的概念来改进插入排序的性能

所以希尔排序是具有一定的优势的

希尔排序的基本思想是将原始列表分成多个子列表，先对每个子列表进行插入排序，然后逐渐减少子列表的数量，使整个列表趋向于部分有序，**最后当整个列表作为一个子列表进行插入排序时，由于已经部分有序，所以排序效率高。**这个过程中，每次排序的子列表是通过选择不同的“增量”来确定的。

实现思路：

预排序
整体直接插入排序

预排序：
根据当前增量，数组被分为若干子序列，这些子序列的元素在原数组中间隔着固定的增量。对每个子序列应用插入排序。

我们假设现在的增量是三

这样的话就会形成三组

9 6 3 0
8 5 2
7 4 1

然后我们对着三组数据进行有序排序就会形成

0 3 6 9
2 5 8
1 4 7

然后我们将排列完的数据放回到原来的数组中就变成了

此时我们完成了第一轮的希尔排序

但现在的数据仍旧是乱的，但是相较于之前，已经变得有序了许多，然后减小增量，通常是将原来的增量除以2（如果增量序列选择为原始的版本）

但由于3无法整除2，所以我们这里直接取一进行排序

最后就会变成0 1 2 3 4 5 6 7 8 9 这样的序列

一.预排序代码的实现

首先我们先进行单趟的控制

void ShellSort(int* a, int n)
{
	int gap = 3;
	int end;
	int tmp = a[end + gap];
	while (end >= 0)
	{
		if (tmp < a[end])
		{
			a[end + gap] = a[end];
			end -= gap;
		}
		else
			break;
	}
	a[end + gap] = tmp;
}

这样我们就完成了单趟的排序

与上边插入排序不同的是我们这里均加减的是gap，也就是间隔增量数

这样单插完后

以gap = 3为例，我们在进行控制这一组的子序列的整个过程

//希尔排序
void ShellSort(int* a, int n)
{
	int gap = 3;
	for (int i = 0; i < n - gap; i += gap)
	{
		int end = i;
		int tmp = a[end + gap];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + gap] = a[end];
				end -= gap;
			}
			else
				break;
		}
		a[end + gap] = tmp;
	}
}

这里我们将定义的gap放到循环外

定义一个for循环，然后这里的i也是小于n-gap，防止越界，同时i也是+=gap，使得一个组的进行排序

在里面，我们定义end为i，这样也就和上边的代码一样了，只是加了一个for循环

然后再对整个序列进行排序

void ShellSort(int* a, int n)
{
	int gap = 3;

	for (int i = 0; i < n - gap; i++)
	{
		int end = i;
		int tmp = a[end + gap];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + gap] = a[end];
				end -= gap;
			}
			else
				break;
		}
		a[end + gap] = tmp;
	}
}

这里，我们还是定义的gap为三，然后套用for循环，但这里的i增加是不断地加一而不是加gap

意味着将这所有的数分组后，进行一次排序完每个组的第二个元素，再进行下一个元素的排序

这里测试一下

说明我们的代码是成功的

二.希尔排序代码实现

我们对预排序的增量进行分析一下：

我们将会发现一个规律

gap越大，大的值更快调到后面，小的值更快调到前面，越不接近有序
gap越小，大的值更慢调到后面，小的值更慢调到前面，越接近有序

所以，如果当我们的gap等于一时，我们的排序将会百分百的成为有序

所以，这里我们gap不可以是固定值，变成灵活变化的值将会更适合希尔排序

因此，在希尔排序的时候，我们将gap设置成随n变化而改变的值，从而实现多次排序

void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 2;
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
					break;
			}
			a[end + gap] = tmp;
		}
	}
}

这里我们将gap设置为n，然后建立一个while循环，当gap>1时就可以进入循环进行分组排序，完成一次就将gap/2，然后不断重复，直到gap变成1，此时也会跳出循环。

这样就可以实现希尔排序

测试一下就是这样的

但这里有人提出了将gap/3会更好

因为在这里如果除2的话，预排序会很多，但很多时候经过预排序后已经很接近有序了

所以我们将2改为3

为了让最后的结果为1，我们也进行一些处理

void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
					break;
			}
			a[end + gap] = tmp;
		}
	}

测试一下

这样也是ok的

复杂度分析

希尔排序的时间复杂度并不固定，它依赖于所选择的间隔序列（增量序列）。直到今天，已经有多种不同的间隔序列被提出来，每种都有自己的性能特点

所以很多不同的教科书给出了不同的定义

其稳定性则是不稳定

4.clock函数

这个函数是<time.h>头文件中的一个函数，用来返回程序启动到函数调用时之间的CPU时钟周期数。这个值通常用来帮助衡量程序或程序的某个部分的性能

我们可以用这个函数进一步对比两种排序占用的CPU时间

void TestOP()
{
	    srand(time(0));
		const int N = 100000;
		int* a1 = (int*)malloc(sizeof(int) * N);
		int* a2 = (int*)malloc(sizeof(int) * N);
	for (int i = 0; i < N; ++i)
	{
		a1[i] = rand();
		a2[i] = a1[i];
	}
	int begin1 = clock();
	InsertSort(a1, N);
	int end1 = clock();
	int begin2 = clock();
	ShellSort(a2, N);
	int end2 = clock();
	printf("InsertSort:%d\n", end1 - begin1);
	printf("ShellSort:%d\n", end2 - begin2);
	free(a1);
	free(a2);
}