【数据结构】经典排序法-Toy模板网

这篇具有很好参考价值的文章主要介绍了【数据结构】经典排序法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

【数据结构】经典排序法

欢迎来到Cefler的博客😁
🕌博客主页：那个传说中的man的主页
🏠个人专栏：题目解析
🌎推荐文章：题目大解析2

【数据结构】经典排序法

👉🏻 直接插入排序

插入排序是一种简单但有效的排序算法，它的基本思想是将一个元素插入到已排序的序列中，从而得到一个新的有序序列。
就像我们打扑克一样，一张一张的模，每摸新的一张放入已经排序好的牌中，在通过简单的对比，放入正确的位置，就能得到新的有序序列。
【数据结构】经典排序法

代码实现如下：👇🏻

int main()
{
	int arr[] = { 12,34,52,2,4,41,24,6,7,24,15 };
	int sz = sizeof(arr) / sizeof(arr[0]);

	for (size_t i = 1; i < sz; i++)
	{
		int end = i - 1;
		int tmp = arr[i];
		while (end >= 0)
		{
			if (arr[end] > tmp) 
			{
				arr[end + 1] = arr[end];
				end--;
			}
			else
				break;
			
		}
		arr[end + 1] = tmp;
	}
	for (size_t i = 0; i <sz; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

👉🏻 选择排序

这里我们以升序为终点出发思想：
选择排序的基本思想是每次从未排序的序列中选择最小的元素，然后将其放到已排序的序列的末尾。
选择排序的思想其实和直接插入排序很相似，但是我们仔细对比一下，会发现略有不同，直接插入排序中，我们插入一个元素到一个已经排好序的序列当中，此时这个元素是不定的，它比较随机，我们还要将其跟已经排好序的序列进行对比放到适合的位置。
而选择排序不同的是，它插入的这个元素，是经过选择过后的，选择排序从未排序的序列中挑选最小的插入已经排好序的末尾，此时这个最小的元素是已经排好序的序列中最大的了，所以此时无需再去跟已经排好序的序列对比，就省了些功夫。
具体代码实现如下：👇🏻

void Swap(int* x1, int* x2)
{
	int tmp = *x1;
	*x1 = *x2;
	*x2 = tmp;
}
void SelectSort(int arr[], int n)
{
	int i, j;
	for (i = 0; i < n; i++)
	{
		int min = i;
		for (j = i + 1; j < n; j++)
		{
			if (arr[j] < arr[min])
				min = j;
		}
		Swap(&arr[i], &arr[min]);
	}
}
int main()
{
	int arr[] = { 12,34,52,2,4,41,24,6,7,24,15 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	SelectSort(arr, sz);
	for (size_t i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}

	return 0;
}

最小和最大一起插入排序
既然如此，我们还可以顺着这个思想，分别从未排序的序列中寻找最小和最大的值，最小的值插入左侧已经排好序的序列的末尾，最大值插入右侧已经排好序的序列的头部。
具体代码实现如下：👇🏻

void Swap(int* x1, int* x2)
{
	int tmp = *x1;
	*x1 = *x2;
	*x2 = tmp;
}
void SelectSort(int arr[], int n)
{
	int left = 0,right = n-1;
	for (; left < right;)
	{
		int min = left,max = right;
		for (int j = left + 1; j < right; j++)
		{
			if (arr[j] < arr[min])
				min = j;
			if (arr[j] > arr[max])
				max = j;
		}
		Swap(&arr[min], &arr[left]);
		
		Swap(&arr[max], &arr[right]);
		left++;
		right--;
	 }
	
	
}
int main()
{
	int arr[] = { 12,34,52,2,4,41,24,6,7,24,15 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	SelectSort(arr, sz);
	for (size_t i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}

	return 0;
}

👉🏻 希尔排序

希尔排序是一种基于插入排序的排序算法，它的基本思想是将一个大的序列分成若干个子序列，对每个子序列进行插入排序，然后逐步缩小子序列的长度，最终将整个序列排序。希尔排序可以在一定程度上提高插入排序的效率，因为它可以将较小的元素快速移动到正确的位置，从而减少了插入排序中的比较和交换次数。
另外，希尔排序的实现也比较简单，只需要对插入排序进行一些简单的修改即可。
【数据结构】经典排序法
对于gap的初始值和变化如何定义？ 🤔
我们知道，gap最后的值一定得是1，因为前面分成多个子序列只是为了方便我们快速将序列进行有序化（为了后期统一插入排序减少不必要的比较），但是我们最后要对整个序列还是要再进行插入排序的（即gap ==1）

但是，gap的初始化应该是多少呢？每次gap应该减少多少呢？
首先，我们先了解gap的大小对整个排序的影响:

gap大：有利于大的数据快速排到后面，有利于小的数据快速排到前面
gap小：有利于整体的有序性提升

所以，对于gap的如何初始化，每次减少多少其实并没有明确的规定，各有利弊，这个取决于你。
不过常见的有：
先将gap初始化为n(n为序列的长度)
而后每次gap每次变化：

gap = gap/3+1;加1是为了确保gap最后的值一定是为1
gap = gap/2;

好了，说了这么多，看具体的代码实现👇🏻

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

		}
	}
	
}

👉🏻 快速排序

霍尔部分排序

思想：
任意从需排列的数据中取一个值，而后将剩余数据中，小于该值的数据居于左侧，大于该值的数据居于右侧，
而后分别再从左右区间再重复该过程，直到区间中的数据数为1或区间不存在时，停止。
代码实现如下：

void Swap(int* x1, int* x2)
{
	int tmp = *x1;
	*x1 = *x2;
	*x2 = tmp;
}
int PartSort(int* a,int left, int right)
{
	int key = left;
	while (left < right)
	{
		//右边找小
		while (left < right && a[right] >= a[key])
		{
			right--;
		}
		//左边找大
		while (left < right && a[left] <= a[key])
		{
			left++;
		}
		
		//开始交换
		Swap(&a[left], &a[right]);
	}
	Swap(&a[left], &a[key]);
	return left;
}
void QuickSort(int* a, int left, int end)
{
	if (left >= end)
		return;
	int key = PartSort(a, left, end);
	QuickSort(a, left, key-1);
	QuickSort(a, key+1, end);
}

霍尔部分区间排序中，主要是选取首端/末端的数据为key值，而后从首末两端分别出发，左边找大于key的值，右边找小于key的值，找到后将二者进行交换，使得小的到了左边，大的到了右边，这边的停止判断条件就是left和right相遇时。
📢这里还有需要注意的有：
一定要先右端先找，这样右端始终会快左端一步，快的一端先到达相遇点，而这里我们进行的是升序排序，假设是左端先找，左端找到的肯定是大于key的值，于是相遇点的值就是大于key的值，而后相遇点的值再与key值交换，此时key值左端存在了一个大于key的值，不符合我们的左小右大。

挖坑法

思想：
先将首端数据为key值，并将其取出设为坑，而后从右开始找小，找到后与坑中值进行交换，而后该位置形成新坑，然后再从左开始找大，重复上述动作

int PartSort2(int* a, int left, int right)
{
	int hole = left;
	int key = a[left];
	while (left < right)
	{
		//右边找小
		while (left < right && a[right] >= key)
		{
			right--;
		}
		Swap(&a[right], &a[hole]);
		hole = right;
		//左边找大
		while (left < right && a[left] <= key)
		{
			left++;
		}
		Swap(&a[left], &a[hole]);
		hole = left;
	}
	return hole;
}

前后指针法

步骤：
选取两个指针prev和cur,cur先走，找小于key的值，找到后，先prev++，然后prev处与cur处进行交换，cur再++，直到cur越界后停止，然后将key值与prev处值进行交换。
思想：
其思想就是找比key小的值，然后全部放在左边，prev每次++,是因为prev左边的值都是符合小于key的值，所以无需再判断。

int PartSort3(int* a, int left, int right)
{
	int cur = left + 1;
	int prev = left;
	int key = left;
	while (cur <= right)
	{
		if (a[cur] <= a[key])
		Swap(&a[++prev], &a[cur]);
		cur++;
	}
	Swap(&a[key], &a[prev]);
	return prev;
}

三路划分法

void QuickSort3R(int* a, int begin, int end)
{
	if (begin >= end)
		return;

	int mid = GetMidKey(a, begin, end);
	Swap(&a[begin], &a[mid]);
	int key = a[begin];
	int left = begin;
	int cur = begin + 1;
	int right = end;
	while (cur <= right)
	{
		if (a[cur] < key)
		{
			Swap(&a[++left], &a[cur++]);
		}
		else if (a[cur] > key)
		{
			Swap(&a[right--], &a[cur]);

		}
		else
		{
			cur++;
		}
	}
	QuickSort3R(a, begin, left);
	QuickSort3R(a, cur, end);

}

非递归排序（栈思想）

void PartSortNonR(int* a, int begin, int end)
{
	ST st;
	InitST(&st);
	PushST(&st, end);
	PushST(&st, begin);
	while (!STEmpty(&st))
	{
		int left = TopST(&st);
		PopST(&st);
		int right = TopST(&st);
		PopST(&st);
		int mid = PartSort3(a, left, right);
		if (mid + 1 < right)
		{
			PushST(&st, right);
			PushST(&st, mid + 1);
		}
		if (left < mid - 1)
		{
			PushST(&st, mid - 1);
			PushST(&st,left);
		}
	}
}

将若干个要处理（排序）的区间依次压入栈中，而后再出栈进行排序，虽然不是递归，但是过程和递归大体相同，都是深度优先。

归并排序

思想：
归并排序的思想其实就是运用二叉树中的后序思想，分左区间和右区间，然后先对左区间进行排序，再对右区间排序，这里我们在动态空间创建一个数组，每次排序在该数组上实现，排序结束后，将已排好序的数组粘贴回原来的数组中去，即归并回去。

void _MergeSort(int* a, int begin, int end, int* tmp)
{
	if (begin >= end)
		return;
	int mid = (begin + end) / 2;
	_MergeSort(a, begin, mid, tmp);
	_MergeSort(a, mid+1,end ,tmp);
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int i = begin;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] <= a[begin2])
		{
			tmp[i++] = a[begin1++];
		}
		else
		{
			tmp[i++] = a[begin2++];
		}
	}
	//接下来将未排完的给排完
	while (begin1 <= end1)
	{
		tmp[i++] = a[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[i++] = a[begin2++];
	}
	//全部排序完后，记得拷贝回去
	memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));

}
void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	_MergeSort(a, 0, n - 1, tmp);
	free(tmp);
}

非递归归并

void _MergeSortNonR(int* a, int n,int* tmp)
{
	int gap = 1;
	while (gap < n)
	{
		int j = 0,i=0;
		for ( i = 0; i < n; i += gap * 2)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + gap * 2 - 1;
			//如果越界，则就不进行归并排序
			if (end1 >= n||begin2>=n)
				break;
			//如果end2大于等于n,则对其进行修正
			if (end2 >= n)
				end2 = n - 1;

			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					tmp[j++] = a[begin1++];
				}
				else
				{
					tmp[j++] = a[begin2++];
				}
			}
			//接下来将未排完的给排完
			while (begin1 <= end1)
			{
				tmp[j++] = a[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[j++] = a[begin2++];
			}
			memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));//归并一组粘贴回去一组

		}
		gap *= 2;
	}

}

计数排序

void CountSort(int* a,int n)
{
	//先找最大值和最小值，以确定待会创建的数组大小
	int i = 0;
	int min = a[0], max = a[0];
	for (i = 0; i < n; i++)
	{
		if (a[i] < min)
			min = a[i];
		if (a[i] > max)
			max = a[i];
	}
	int range = max - min + 1;
	int* countA = (int*)malloc(sizeof(int) * range);
	memset(countA, 0, sizeof(int) * range);//数组初始化为0
	//开始计数
	for (i = 0; i < n; i++)
	{
		countA[a[i] - min]++;
	}
	//开始写入数组
	int j = 0;
	for (i = 0; i < range; i++)
	{

		while (countA[i]--)
		{
			a[j++] = i + min;
		}
	}
}