本文共 3134 字，大约阅读时间需要 10 分钟。

1.插入排序

1.1实现

将数组在逻辑上看做有序序列和无序序列两个部分，每次从无序序列中挑选出来一个元素在有序序列中插入进去；

下面都将以升序为例

实现代码：

void InsertSort(int *arr, int size)//插入排序{   	for (int i = 0; i < size - 1; i++)//升序	{   		int end = i;//有序数组的最后一个元素下标		int key = arr[end + 1];//无序数组的第一个元素		while (end >= 0 && arr[end]>key)		{   			arr[end + 1] = arr[end];//往后挪动一个位置			end--;		}		arr[end + 1] = key;	}	//for (int i = 0; i < size - 1; i++)//降序	//{   	//	int end = i;	//	int key = arr[end + 1];	//	while (end >= 0&&arr[end] < key)	//	{   	//		arr[end + 1] = arr[end];	//		end--;	//	}	//	arr[end + 1] = key;	//}}

1.2特性

1.元素集合越接近有序，直接插入排序算法的时间效率越高；

2.适用于小规模数据或者基本有序时十分高效；

2.时间复杂度：最好为已经是有序序列，时间复杂度为O(N)。最差为逆序，时间复杂度为O(N^2);

3.空间复杂度：常数个空间，O(1);

4.稳定性：不改变相对位置，具有稳定性；

5.数据敏感度:原先数组的有效程度对排序时间复杂度的影响非常大，因此数据敏感度为敏感；

2.希尔排序

2.1实现

希尔排序是插入排序的优化版本，由上述插入排序我们知道，数组中元素的有序程度越高，时间效率就越高。

因此我们需要想办法提高数组的有序程度，于是乎就有了希尔排序法，起始希尔排序法的本质也是插入排序法，只不过将插入排序的间隔改变了；

希尔排序法是先将数组进行分组(逻辑上)排序，这样在整体上就提高了数组的有序程度。数组的有序程度提高了，插入排序的时间效率也就提高了；

gap越大，前面的数据可以越快到后面，后面小的数可以越快到前面。gap越大，越不接近有序，gap越小越接近有序。如果gap=1其实就相当于直接插入排序，就有序了；

下面我用图形来解释一下这个过程

void ShellSort(int *arr, int size){   	int gap = size;	while (gap > 1)	{   		gap = gap / 2;//每次的步距为gap		for (int i = 0; i < size - gap; i++)		{   			int end = i;//有序的最后一个元素的下标			int key = arr[end + gap];			while (end >= 0 && arr[end]>key)			{   				arr[end + gap] = arr[end];//往后挪动一个位置				end -= gap;			}			arr[end + gap] = key;		}	}}

2.2特性

1.希尔排序法是对直接插入排序的优化；

2.gap>1时都是进行预排序，即为了提高数组的有序程度；

3.时间复杂度：时间复杂度需要进行推导，这里直接给出结论，平均时间复杂度为O(N^1.3- N^2)；

4.空间复杂度：O(1)；

5.稳定性：不具有稳定性，相同的元素在分组时可能会被岔开，然后改变相对位置；

6.数据敏感度：敏感，因为本质也是插入排序；

7.当数组有序时，性能比插入排序的效率会低一点，但是总体性能要比插入排序高出很多；

3.选择排序

3.1实现

通过遍历数组，每次选取其中的最大值和最小值放在数组头和尾；

void Swap(int *arr, int sub1, int sub2){   	int temp = arr[sub1];	arr[sub1] = arr[sub2];	arr[sub2] = temp;}void SelectSort(int *arr, int size){   	int begin = 0;	int end = size - 1;		while (begin < end)	{   		int min = begin;//较小值坐标		int max = end;//较大值坐标		for (int i = begin; i <= end; i++)		{   			if (arr[i] < arr[min])//取得新的较小值坐标				min = i;			if (arr[i] > arr[max])//取得新的较大值坐标				max = i;		}		Swap(arr, begin, min);//较小值放入有序部分				if (max == begin)//有可能begin对应的值已经和min对应的值发生了交换			max = min;		Swap(arr, end, max);//较大值放入有序部分		begin++;		end--;	}}

3.2特性

1.时间复杂度：O(N^2)；

2.空间复杂度：O(1);

3.数据稳定性：不稳定，从前往后遍历，如果是遇到了最大值，那么相对顺序就会改变

4.数据敏感度：不敏感，无论数组是否有序都需要进行循环；

4.计数排序

4.1实现

void CountSort(int *arr, int size)//计数排序{   	assert(arr);	int max = arr[0];	int min = arr[0];	for (int i = 0; i < size; i++)//寻找最大最小值	{   		if (arr[i]>max)			max = arr[i];		if (arr[i] < min)			min = arr[i];	}	int *temp = (int *)malloc(sizeof(int)*(max - min + 1));//开辟统计数组空间	memset(temp, 0, sizeof(int)*(max - min + 1));	for (int i = 0; i < size; i++)//进行统计	{   		temp[arr[i]-min]++;	}	int sub = 0;	for (int i = 0; i < max - min + 1; i++)//数组回填	{   		while(temp[i])		{   			arr[sub++] = i + min;			temp[i]--;		}	}	free(temp);}

3.2特性

1.由实现思想可知，这种排序有几个缺陷只适用于整形，并且当数组元素个数少，范围特别大的时候，会造成空间的浪费；

2.时间复杂度分析：需要遍历三遍数组，分别是寻找最大最小值，时间复杂度为O(N),进行统计时间复杂度为O(N)，数据回填时间复杂度为O(范围)，因此计数统计的时间复杂度为O(max(N,范围))；

3.空间复杂度分析：需要开辟额外的空间，开辟空间的数量为待排序数组的范围，即空间复杂度为O(范围)；

4.数据敏感度：不敏感，数据有序或者无序都要进行遍历

5.数据稳定性：不稳定，由于是统计元素出现的个数，不能确定元素的先后

转载地址：http://vmse.baihongyu.com/