希尔排序和选择排序及计数排序的简单介绍

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数gap，把待排序文件中所有数据分成几个组，所有距离为gap的数据分在同一组内，并对每一组内的数据进行排序。然后gap减减，重复上述分组和排序的工作。当到达gap=1时，所有数据在同一组内排好序（gap==1时就是上次讲的插入排序）。

希尔排序举例：

#include <stdio.h>
// 打印
void Printarry(int* arr, int n)
{
	assert(arr);
	for (int i = 0;i < n;i++)
	{
		printf("%d ", arr[i]);

	}
	printf("\n");
}
// 希尔排序
// 时间复杂度 O（N^1.3-N^2)
// gap越大，前面大的数据可以越快排到后面，后面小的数可以越快拍到前面，gap越大，越不接近有序
// gap越小越接近有序，如果gap==1其实就是直接插入排序，就有序了
void ShellSort(int* arr, int n)
{
	assert(arr);
	int gap = n;

	// gap>1相当于预排序，让数组接近有序
	// gap==1就相当于直接插入排序，保证有序
	while (gap > 1)
	{
		gap = gap / 3 + 1; // +1是保证了最后一次gap一定是1

		// 注意结束条件，防止造成越界访问（画图）
		for (int i = 0;i < n - gap;i++)  // 多趟并排
		{
            // 单趟排序
			int end = i;               // 当end==0时就是单趟排序，排间距为gap的那一趟
			int temp = arr[end + gap];  // 将新的排序数值存起来，方便每次比较大小
			while (end >= 0)   
			{
				if (temp < arr[end])
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = temp;  // 跳出循环后temp放到end+gap位置
		}

		// 打印每一个gap时的排序状态
		Printarry(arr, n);
	}
	
}

void TestShellSort() 
{
	int arr[] = { 3,1,4,2,8,4,9,6,0,7 };
	Printarry(arr, sizeof(arr) / sizeof(arr[0]));
 
	ShellSort(arr, sizeof(arr) / sizeof(arr[0]));
	Printarry(arr, sizeof(arr) / sizeof(arr[0]));
}
 
int main()
{
	TestShellSort();
 
	return 0;
}

选择排序

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

直接选择排序:

在元素集合arr[i]--arr[n-1]中选择最大(小)的数据 若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换 在剩余的array[i]--array[n-2]（array[i+1]--array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素。

举例：利用双指方法，begin指向首元素，end指向末尾元素，找到最大值时maxi和end位置数据互换，最小值mini位置和begin位置数据互换。

当begin和maxi重叠时，mini位置的数据和begin位置的数据互换后要将mini的值给到maxi，在将maxi位置的数据和end位置的数据互换。

#include <stdio.h>
// 打印
void Printarry(int* arr, int n)
{
	assert(arr);
	for (int i = 0;i < n;i++)
	{
		printf("%d ", arr[i]);

	}
	printf("\n");
}
// 选择排序
// 空间复杂度为O（1）
// 时间复杂度为 O（N^2）,最好的情况是接近有序比较n次即可，最坏的是不完全有序接近无顺序
void SelectSort(int* arr, int n)
{
	assert(arr);
	int begin = 0;
	int end = n - 1;
	//int mini = 0;
	//int maxi = 0;

	while (begin < end)
	{
		int mini = 0;
		int maxi = 0;
		maxi = mini = begin;
		// 在[begin，end]之间选出最大值和最小值
		for (int i = begin + 1;i <= end;++i)
		{
			if (arr[i] > arr[maxi])
			{
				maxi = i;
			}

			if (arr[i] < arr[mini])
			{
				mini = i;
			}
		}
		Swap(&arr[begin], &arr[mini]);

		// 如果maxi与begin位置重叠的话要修正maxi的位置
		if (begin == maxi)
			maxi = mini;
		Swap(&arr[end], &arr[maxi]);
		--end;
		++begin;
	}
}

void TestSelectSort()
{
	int arr[] = { 15,18,23,3,1,14,2,8,4,9,6,0,7 };
	SelectSort(arr, sizeof(arr) / sizeof(arr[0]));
	Printarry(arr, sizeof(arr) / sizeof(arr[0]));
}
int main()
{
	TestShellSort();
 
	return 0;
}

计数排序

首先找到待排序数组的最大值和最小值，然后开辟一个空间temp数组，大小为最大值减去最小值加1；然后遍历数组，将数据出现的次数放到temp数组相对位置中；然后再遍历temp数组取出对应数据出现的次数，将该数据依次覆盖回原数组中。

注意：这个排序缺点就是浪费空间比如，待排序数组最小值为100，最大值为1000；那么要开辟0-1000个空间的数组，才能存放比如100出现10次，那么temp数组中下标100位置就存放10，这样就很浪费空间。我们在这里开辟900个空间的数组，将100出现的次数放到相对位置中，相对位置为：100-min。覆盖回原数组的时候再加上min即可。相对减少空间浪费。

举例子：

#include <stdio.h>
// 打印
void Printarry(int* arr, int n)
{
	assert(arr);
	for (int i = 0;i < n;i++)
	{
		printf("%d ", arr[i]);

	}
	printf("\n");
}
// 计数排序
// 时间复杂度O(N+range)
// 空间复杂度O(range)
void CountSort(int* arr, int n)
{
	// 找出最大最小值
	int min = arr[0];
	int max = arr[0];
	for (int i = 1;i < n;i++)
	{
		if (arr[i] > max)
			max = arr[i];
		if (arr[i] < min)
			min = arr[i];
	}
	// 创建计数的空间
	int range = max - min + 1;
	int* countArr = (int*)malloc(sizeof(int) * range);

	memset(countArr, 0, sizeof(int) * range); // 将数组元素置为0

	// 遍历数组将相同的数值出现的次数放到相对位置处：arr[i] - min
	for (int i = 0;i < n;i++)
	{
		countArr[arr[i] - min]++;
	}
	// 遍历countArr数组将某个数出现的次数，依次将这个数放回到原数组
	int index = 0;
	for (int i = 0;i < range;i++)
	{
		while (countArr[i]--)  // 控制数据出现的次数
		{
			arr[index++] = i + min;
		}
	}
}

void TestCountSort()
{
	int arr[] = { 15,18,23,3,1,14,2,8,4,9,6,0,7 };
	CountSort(arr, sizeof(arr) / sizeof(arr[0]));
	Printarry(arr, sizeof(arr) / sizeof(arr[0]));
}
int main()
{
	TestCountSort();
 
	return 0;
}