提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  后端

当前栏目

数据结构——排序（C语言实现）

C语言排序数据结构 实现
2023-06-13 09:17:43 时间

排序

直接排序与希尔排序

直接插入排序

我们在玩扑克牌的时候，每次抓一张牌都要放在适合的位置，比如我就喜欢左边大右边小，这就算是插入排序。 例：

加入给这个数组排序，我们先将2和3比较，然后排序成有序，再让7和有序的2和3比较，以此循环。 最后5和有序的2，3，7，9比较，先和9比较大小，比9小就与9交换位置，然后5在和7比较，比7小再与7交换位置，最后和3比较位置，比3大，那么就排序好了，不需要和2比较。 代码的实现思路也很简单： 这里交换数太麻烦了，可以用一个变量储存数据5，把9和7往后移，原本的数就会被覆盖掉，然后将储存的数放在指定的位置。

void sort()
{
	int arr[] = { 2,3,7,9,5 };
	int i = 0;//控制end
	int n = sizeof(arr)/sizeof(arr[0]);
	for (i = 0; i < n - 1; i++)
	{
		int end = i;//这个是两个数比较中的第一个数
		int s = arr[end + 1];//保留的是两个数的后面一个数
		while (end >= 0)
		{
			if (arr[end] > s)//比较两个数的大小
			{
				arr[end + 1] = arr[end];//如果不是从大到小就重新排序
				end--;
			}
			else
			{
				break;
			}
		}
		arr[end + 1] = s;//如果顺序没错就将储存起来的数据放到指定位置，这么写的好处还有一个是end最坏的情况会到-1
	}
}

s>arr[end]的时候，不用让3覆盖end+1这个位置了，这里将5覆盖在了这个位置。 这个排序的效率是非常慢的。 时间复杂度：O（N2）

希尔排序

希尔排序是直接插入排序的优化： 希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。 例如我们要将这组数从小到大排序：

9 8 7 6 5 4 3 2 1 0 gap = 3

黑色，红色，紫色分别是三组： 黑色组：9先和6比较，9比6大，交换他们，然后是9和3比较，交换，9和0比较，交换。

然后再进行红色和紫色的比较与交换：

我们发现这个顺序已经接近从大到小了，最后用直接插入排序让他变成正序就可以了。 先来一组数预处理的代码实现：

void Shellsort()
{
	int arr[] = { 9,8,7,6,5,4,3,2,1,0 };
	int n = sizeof(arr) / sizeof(arr[0]);

	int gap = 3;
	for (int i = 0; i < n - gap; i+=gap)//一组的排序
	{
		int end = i;
		int sum = arr[end + gap];
		while (end >= 0)
		{
			if (arr[end] > sum)
			{
				arr[end + gap] = arr[end];
				end -= gap;
			}
			else
			{
				break;
			}
		}
		arr[end + gap] = sum;
	}
}

如果所有组都算就需要在加一层循环：

void Shellsort()
{
	int arr[] = { 9,8,7,6,5,4,3,2,1,0 };
	int n = sizeof(arr) / sizeof(arr[0]);
	int gap = 3;
	for (int j = 0;j < gap;j++)
	{
		for (int i = j; i < n - gap; i += gap)//一组的排序
		{
			int end = i;
			int sum = arr[end + gap];
			while (end >= 0)
			{
				if (arr[end] > sum)
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = sum;
		}
	}
}

但是这样不好，三层循环很麻烦，那么我们再进行优化一下：

void Shellsort()
{
	int arr[] = { 9,8,7,6,5,4,3,2,1,0 };
	int n = sizeof(arr) / sizeof(arr[0]);
	int gap = 3;
	for (int i = 0; i < n - gap; i++)
	{ 
		int end = i;
		int sum = arr[end + gap];
		while (end >= 0)
		{
			if (arr[end] > sum)
			{
				arr[end + gap] = arr[end];
				end -= gap;
			}
			else
			{
				break;				
			}
		}
		arr[end + gap] = sum;
	}
}

改成这个样子就省了一层的循环，先交换第一组的9和6.然后end+1，就到了第二组交换第二组的8和5，以此类推，最后交换的是，3和0。 这是多组并排的方式，并且gap不知道应该定义多大，gap多大也间接影响到最后一次直接插入排序的效率，所以需要再次改进： 那么gap等于多少是最好的呢？ gap越大，虽然大的数据和小的数据排序越快，但是顺序越乱，gap越小则相反。 那么让最初的gap等于数组长度，每次除以3，进行越来越细致的预处理。

void Shellsort()
{
	int arr[] = { 9,8,7,6,5,4,3,2,1,0 };
	int n = sizeof(arr) / sizeof(arr[0]);
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;//+1是为了最后能等于1，也可以是gap=gap/2，这两种写法效率最高
		for (int i = 0; i < n - gap; i++)//这里就是以gap为一组的进行预处理排序
		{
			int end = i;
			int sum = arr[end + gap];
			while (end >= 0)
			{
				if (arr[end] > sum)
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = sum;
		}
	}
}

当gap等于1的时候就等于插入排序了。

希尔排序的时间复杂度目前算的大约是O(N1.3)。 具体的时间复杂度是多少并没有推理过程。

选择排序

选择排序

选择排序是从左向右或者是从右向左开始选择一个最小的数然放在左边或者是右边，然后再选剩下的数中最小的数放在左边或者是右边：

这里我们选择对这个数组进行升序，第一次在整个数组里面找最小的，选择的是1，放在最左边，然后第二次在5 6 8 4中找最小的，选择4，然后饭挂在5的前面，5 6 8往后移。 以此类推，直到走到尽头为止。 代码实现：

void Swap(int* a,int* b)
{
	int c = *a;
	*a = *b;
	*b = c;
}
void selection_sort()
{
	int arr[] = { 1,5,7,9,8,3,4,2,6,0 };
	int n = sizeof(arr) / sizeof(arr[0]);
	int start = 0;//开头的下标
	int end = n - 1;//结束的下标
	while (start < end)
	{
		int min = start;
		int max = start;
		for (int i = start + 1; i <= end; ++i)//i=start + 1是因为第一个位置已经给min和max了
		{
			if (arr[i] < arr[min])
			{
				min = i;//找到最小的数下标就传给min
			}
			if (arr[i] > arr[max])
			{
				max = i;//找到最大的数的下标
			}
		}
		Swap(&arr[start], &arr[min]);//将最小的值放在前面
		if (max == start)//对于max还是等于start的情况下进行修正，因为上面已经将min位置的和start位置的进行了交换
		{
			max = min;
		}
		Swap(&arr[end], &arr[max]);//将最大的值放在后面
		start++;
		end--;
	}
}

这段代码是小的放前面，大的放后面，从两头开始找，直到找完整个数组为止。 时间复杂度为O(N2)

堆排序

二叉树——堆 堆排序

交换排序

基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排 序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

冒泡排序

void Swap(int* a, int* b)
{
	int c = *a;
	*a = *b;
	*b = c;
}
void bubbling()
{
	int arr[] = { 9,8,7,6,5,4,3,2,1,0 };
	int n = sizeof(arr) / sizeof(arr[0]);
	int x = 1;
	for (int j = 0; j < n; j++)
	{
		for (int i = 0; i < n - 1 - j; i++)
		{
			if (arr[i] > arr[i + 1])
			{
				Swap(&arr[i], &arr[i + 1]);
				x = 0;
			}
		}
		if (x == 1)//如果x没有被置为0就说明没有可以交换的数据了
		{
			break;
		}
	}
}

这个排序是我最早接触的排序。 时间复杂度为：O(N2) 虽然很慢，但是很容易理解。

快速排序

基本思想：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。 快排有三种方法。（原理都是类似的）

hoare法

这个版本的方法是先选择一个key值，一般是在第一个或者是最后一个位置，然后两个变量从头和尾向中间走，相遇就会停下。 例：

这里key我选的是数组中第一个值，R找比key小的，L找比key大的，如果R找到的值比key找到的小就与L位置进行交换（但是key值只在R与L相遇才会换位置），就像这样，假如R先走，就先和key比较：

这里R走了两步，因为8比6大，10比6大，现在R的位置是4，比6小，停下，这里不进行交换，然后L走，L到7的位置停下，因为7比6大，然后R和L的位置进行交换。

然后R走一步到3的位置停下，L走一步，发现没有比key大，再走一步与R相遇，这时将R与L相遇的位置与key值的位置进行交换。

那么怎么保证L与R相遇的位置的值一定小于key呢？答案是R先走。

R停下，说明撞到了L，L虽然是找比key大的，但是在R走之前L与R位置的值一定互换了，就算L一直没动，就说明所有的值都比key大。 L停下，撞到了R，R是找小，撞到R，R的位置一定是小于key的数，如果R没动，说明所有数都比key小。 同理，如果key在右边第一个值，L先走。

排序完成之后我们发现6的前面和后面正好分成了两个区间，6的位置也是不用在进行移动的，这就是但趟排序，然后再用将这组数的前后区间进行相同方法的排序就可以了，直到剩下最后一个数为止。

以此类推，其实就是一个递归二叉树的原理。

代码实现：

#include <stdio.h>
void Swap(int* a,int* b)
{
	int c = *a;
	*a = *b;
	*b = c;
}
int single_row(int* a, int start, int end)//单趟排序
{

	int key = start;//让key变成头部位置
	while (start < end)
	{
		while (a[end] >= a[key] && end > start)//如果这里不是>=key可能会会产生死循环
		{
			end--;
		}
		while (a[start] <= a[key] && end > start)
		{
			start++;
		}
		if (start < end)//没有相遇就交换
		{
			Swap(&a[start], &a[end]);
		}
	}
	Swap(&a[key], &a[end]);//当R与L相遇交换key和相遇位置的数据
	return end;//返回相遇的位置
}

void Quicksort(int* a, int start, int end)//调用一次这个函数就等于使用一次单排的逻辑
{
	if (start >= end)//如果剩余一个数或者是没有数据就不用排序了
	{
		return;
	}
	int key = single_row(a, start, end);//单排，返回值是已经排序好的数值的位置
	Quicksort(a, start, key - 1);//左区间
	Quicksort(a, key + 1, end);//右区间
}

int main()
{
	int arr[] = { 6,2,7,1,3,4,10,8 };
	int n = sizeof(arr) / sizeof(arr[0]);
	Quicksort(arr, 0, n - 1);
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

这棵二叉树的深度是logN，每层单排的时间复杂度是O(N). 总体时间复杂度是O(N*logN), 但是这种情况只发生在相遇的地方是在数组中间左右位置的地方。 那么如果每次相遇的地方总是在头或者是尾会怎么样呢？

红色是key的位置，左边树一直都是空的，也就是说这棵树的深度是N,时间复杂度就是O(N2),这样还能能被称为快排吗？不仅仅如此，还会造成栈溢出的情况。 所以我们要优化一下。

快排的优化

有两个优化的地方：

1.key值的调整 2.避免给二叉树的后三层排序

key值的调整取中间数明显是最好的，不过数组中想取中间数很困难，不能让key每次都取数组中间的数，因为key随意位移单排的整体代码都会被更改，如果想让key的数更换直接让中间的数与开头的数交换就可以了，但是如果换过来的数正好是最小或者是最大的数呢？那么就又会发生上面的事情，所以要三数取中法，选择开头的数和中间的数，末尾的数，然后比大小，选择中间大的数。

避免二叉树的后三层是因为最后一层的结点占了整个二叉树的50%，倒数第二层占了25%，倒数第三层占了12.5%，如果在倒数第四层的地方用直接插入排序会更好，因为每次排序都会接近更有序，所以用直接插入排序更划算。

因为单排要等最后一个数才会停止，所以可以推理出倒数第四层为8个数。 代码实现

#include <stdio.h>
void sort(int* arr, int n)
{
	int i = 0;//控制end
	for (i = 0; i < n - 1; i++)
	{
		int end = i;//这个是两个数比较中的第一个数
		int s = arr[end + 1];//保留的是两个数的后面一个数
		while (end >= 0)
		{
			if (arr[end] > s)//比较两个数的大小
			{
				arr[end + 1] = arr[end];//如果不是从大到小就重新排序
				end--;
			}
			else
			{
				break;
			}
		}
		arr[end + 1] = s;//如果顺序没错就将储存起来的数据放到指定位置，这么写的好处还有一个是end最坏的情况会到-1
	}
}
void Swap(int* a, int* b)
{
	int c = *a;
	*a = *b;
	*b = c;
}
int middle(int* a, int start, int end)//取中间数
{
	int mid = (start + end) / 2;
	if (a[start] < a[mid])
	{
		if (a[start] > a[end])//mid最大，end最小
		{
			return start;
		}
		else if (a[end] > a[mid])//end最大，start最小
		{
			return mid;
		}
		else//mid最大，start最小
		{
			return end;
		}
	}
	else//a[start] >= a[mid]
	{
		if (a[end] > a[start])//end最大，mid最小
		{
			return start;
		}
		else if(a[mid] > a[end])//start最大，end最小
		{
			return mid;
		}
		else//start最大，mid最小
		{
			return end;
		}
	}
}
int PartSort(int* a, int start, int end)//单趟排序
{
	int key = middle(a, start, end);
	Swap(&a[key], &a[start]);//交换中间数和第一个数的位置
	while (start < end)
	{
		while (a[end] >= a[key] && end > start)//如果这里不是>=key可能会会产生死循环
		{
			end--;
		}
		while (a[start] <= a[key] && end > start)
		{
			start++;
		}
		if (start < end)//没有相遇就交换
		{
			Swap(&a[start], &a[end]);
		}
	}
	Swap(&a[key], &a[end]);//当R与L相遇交换key和相遇位置的数据
	return end;//返回相遇的位置
}

void Quicksort(int* a, int start, int end)//调用一次这个函数就等于使用一次单排的逻辑
{
	if (start >= end)//如果剩余一个数或者是没有数据就不用排序了
	{
		return;
	}
	if (end - start <= 8)
	{
		sort(a + start, end - start + 1);//第一个参数因为左右区间的问题，第二个参数要加一的原因是要跳过已经排序号位置的数
	}
	else
	{
		int key = PartSort(a, start, end);//单排，返回值是已经排序好的数值的位置
		Quicksort(a, start, key - 1);//左区间
		Quicksort(a, key + 1, end);//右区间
	}
}

int main()
{
	int arr[] = { 6,2,7,1,3,4,10,8 };
	int n = sizeof(arr) / sizeof(arr[0]);
	Quicksort(arr, 0, n - 1);
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

挖坑法

这里多了一个pit变量，也是代表坑的位置，一开始key位置的就是坑，然后也和hoare法一样，R先走，遇到比key小的就停下，这里要注意，R停下之后将R位置的值放进pit位置中：

在填完坑之后坑的位置就到了R这里，然后L走，以此类推：

当L与R相遇的时候，key的值就可以填到坑的位置了。 代码实现

#include <stdio.h>
void sort(int* arr, int n)
{
	int i = 0;//控制end
	for (i = 0; i < n - 1; i++)
	{
		int end = i;//这个是两个数比较中的第一个数
		int s = arr[end + 1];//保留的是两个数的后面一个数
		while (end >= 0)
		{
			if (arr[end] > s)//比较两个数的大小
			{
				arr[end + 1] = arr[end];//如果不是从大到小就重新排序
				end--;
			}
			else
			{
				break;
			}
		}
		arr[end + 1] = s;//如果顺序没错就将储存起来的数据放到指定位置，这么写的好处还有一个是end最坏的情况会到-1
	}
}
void Swap(int* a, int* b)
{
	int c = *a;
	*a = *b;
	*b = c;
}
int middle(int* a, int start, int end)//取中间数
{
	int mid = (start + end) / 2;
	if (a[start] < a[mid])
	{
		if (a[start] > a[end])//mid最大，end最小
		{
			return start;
		}
		else if (a[end] > a[mid])//end最大，start最小
		{
			return mid;
		}
		else//mid最大，start最小
		{
			return end;
		}
	}
	else//a[start] >= a[mid]
	{
		if (a[end] > a[start])//end最大，mid最小
		{
			return start;
		}
		else if (a[mid] > a[end])//start最大，end最小
		{
			return mid;
		}
		else//start最大，mid最小
		{
			return end;
		}
	}
}
int PartSort1(int* a, int start, int end)
{
	int key = middle(a, start, end);
	Swap(&a[start], &a[key]);
	int keyi = a[start];//key位置的值
	int pit = start;//坑位
	while (start < end)
	{
		while (a[end] <= keyi && start < end)//找小填坑
		{
			end--;
		}
		a[pit] = a[end];//填坑
		pit = end;//新坑位
		while (a[start] >= keyi && start < end)//找大填坑
		{
			start++;
		}
		a[pit] = a[start];//填坑
		pit = start;//新坑位
	}
	a[end] = keyi;
	return end;
}
void Quicksort(int* a, int start, int end)
{
	if (start >= end)//如果剩余一个数或者是没有数据就不用排序了
	{
		return;
	}
	if (end - start <= 8)
	{
		sort(a + start, end - start + 1);//第一个参数因为左右区间的问题，第二个参数要加一的原因是要跳过已经排序号位置的数
	}
	else
	{
		int key = PartSort1(a, start, end);//单排，返回值是已经排序好的数值的位置
		Quicksort(a, start, key - 1);//左区间
		Quicksort(a, key + 1, end);//右区间
	}
}
int main()
{
	int arr[] = { 6,2,7,1,3,4,10,8 };
	int n = sizeof(arr) / sizeof(arr[0]);
	Quicksort(arr, 0, n - 1);
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

前后指针法

虽然是名称是双指针，但其实并不是真的用指针：

定义两个变量，cur是前指针，prve是后指针，cur在prve的前面。 prve先走，cur后走，每次都只能走一步，cur找小，prve找大。 当cur遇到比key大的数时，prve会停下，然后cur会向前走，直到遇到比key小的值为止：

这时要将cur指向的位置与prve++的位置进行交换。

交换完之后cur先走，又遇到比key位置小的值，还是进行如上的交换：

直到cur走到尽头：

这种时候就需要将key位置的值与prve位置的值进行互换了：

代码实现

#include <stdio.h>
void sort(int* arr, int n)
{
	int i = 0;//控制end
	for (i = 0; i < n - 1; i++)
	{
		int end = i;//这个是两个数比较中的第一个数
		int s = arr[end + 1];//保留的是两个数的后面一个数
		while (end >= 0)
		{
			if (arr[end] > s)//比较两个数的大小
			{
				arr[end + 1] = arr[end];//如果不是从大到小就重新排序
				end--;
			}
			else
			{
				break;
			}
		}
		arr[end + 1] = s;//如果顺序没错就将储存起来的数据放到指定位置，这么写的好处还有一个是end最坏的情况会到-1
	}
}
void Swap(int* a, int* b)
{
	int c = *a;
	*a = *b;
	*b = c;
}
int middle(int* a, int start, int end)//取中间数
{
	int mid = (start + end) / 2;
	if (a[start] < a[mid])
	{
		if (a[start] > a[end])//mid最大，end最小
		{
			return start;
		}
		else if (a[end] > a[mid])//end最大，start最小
		{
			return mid;
		}
		else//mid最大，start最小
		{
			return end;
		}
	}
	else//a[start] >= a[mid]
	{
		if (a[end] > a[start])//end最大，mid最小
		{
			return start;
		}
		else if (a[mid] > a[end])//start最大，end最小
		{
			return mid;
		}
		else//start最大，mid最小
		{
			return end;
		}
	}
}
int PartSort2(int* a, int start, int end)
{
	int mid = middle(a, start, end);
	Swap(&a[start], &a[mid]);
	int key = start;
	int cur = start + 1;//前指针
	int prve = start;//后指针
	while (cur <= end)
	{
		if (a[cur] < a[key] && ++prve != cur)//如果cur小就停下与prve交换，前提是++prve不能与cur相等，防止自己与自己交换
			Swap(&a[cur], &a[prve]);
		cur++;//如果cur大就继续向前走
	}
	Swap(&a[prve], &a[key]);//cur走出范围key与prve交换
	return prve;
}
void Quicksort(int* a, int start, int end)
{
	if (start >= end)//如果剩余一个数或者是没有数据就不用排序了
	{
		return;
	}
	if (end - start <= 8)
	{
		sort(a + start, end - start + 1);//第一个参数因为左右区间的问题，第二个参数要加一的原因是要跳过已经排序号位置的数
	}
	else
	{
		int key = PartSort2(a, start, end);//单排，返回值是已经排序好的数值的位置
		Quicksort(a, start, key - 1);//左区间
		Quicksort(a, key + 1, end);//右区间
	}
}
int main()
{
	int arr[] = { 6,2,7,1,3,4,10,8 };
	int n = sizeof(arr) / sizeof(arr[0]);
	Quicksort(arr, 0, n - 1);
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

非递归快排

我们知道递归是非常占内存的，上面的递归每次调用都是在内存中栈上创建的，栈并没有那么大，所以很容易栈溢出。

我们要借助数据结构的栈来实现非递归快排（数据结构的栈实在内存中的堆上创建的），因为递归的二叉树中，是区间控制了整个数组的排序，所以想实现非递归二叉树就要在栈里面存放区间。（要注意栈的特新：先进后出）

这是在栈内出入顺序。（只针对上面的例图）

//stack.h
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>

typedef int SD;//随时更改数据类型
typedef struct stack
{
	SD* a;//数组
	int top;//栈顶
	int capacity;//容量
}ST;

void StackInit(ST* ps);//初始化
void StackPush(ST* ps, SD x);//入栈
void StackPop(ST* ps);//出栈
SD StackTop(ST* ps);//获取栈顶元素
int StackSize(ST* ps);//获取栈中有效的元素
bool StackEmpty(ST* ps);// 检测栈是否为空
void StackDestroy(ST* ps);//销毁栈
void Quicksort(int* a, int start, int end);
//stack.c
#include "stack.h"

void StackInit(ST* ps)//初始化
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}
bool StackEmpty(ST* ps)//判断
{
	assert(ps);
	return ps->top == 0;
}
void StackPush(ST* ps, SD x)//入栈
{
	assert(ps);
	//扩容
	if (ps->capacity == ps->top)
	{
		int count = (ps->capacity == 0 ? ps->capacity = 4 : ps->capacity * 2);
		SD* y = (SD*)realloc(ps->a, count * sizeof(SD));
		 if (y == NULL)
		 {
			 perror("realloc fail");
			 exit(-1);
		 }
		 ps->a = y;
		 ps->capacity = count;
	}
	ps->a[ps->top] = x;//赋值
	ps->top++;//让栈顶往后走一步
}
void StackPop(ST* ps)//出栈
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;
}
void StackDestroy(ST* ps)//销毁栈
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}
SD StackTop(ST* ps)//获取栈顶元素
{
	assert(ps);
	return ps->a[ps->top - 1];
}
int StackSize(ST* ps)//获取栈中有效的元素
{
	assert(ps);
	return ps->top;
}
//源.c
#include "stack.h" 
void sort(int* arr, int n)
{
	int i = 0;//控制end
	for (i = 0; i < n - 1; i++)
	{
		int end = i;//这个是两个数比较中的第一个数
		int s = arr[end + 1];//保留的是两个数的后面一个数
		while (end >= 0)
		{
			if (arr[end] > s)//比较两个数的大小
			{
				arr[end + 1] = arr[end];//如果不是从大到小就重新排序
				end--;
			}
			else
			{
				break;
			}
		}
		arr[end + 1] = s;//如果顺序没错就将储存起来的数据放到指定位置，这么写的好处还有一个是end最坏的情况会到-1
	}
}
void Swap(int* a, int* b)
{
	int c = *a;
	*a = *b;
	*b = c;
}
int middle(int* a, int start, int end)//取中间数
{
	int mid = (start + end) / 2;
	if (a[start] < a[mid])
	{
		if (a[start] > a[end])//mid最大，end最小
		{
			return start;
		}
		else if (a[end] > a[mid])//end最大，start最小
		{
			return mid;
		}
		else//mid最大，start最小
		{
			return end;
		}
	}
	else//a[start] >= a[mid]
	{
		if (a[end] > a[start])//end最大，mid最小
		{
			return start;
		}
		else if (a[mid] > a[end])//start最大，end最小
		{
			return mid;
		}
		else//start最大，mid最小
		{
			return end;
		}
	}
}
int PartSort2(int* a, int start, int end)
{
	int mid = middle(a, start, end);
   	Swap(&a[start], &a[mid]);
	int key = start;
	int cur = start + 1;//前指针
	int prve = start;//后指针
	while (cur <= end)
	{
		if (a[cur] < a[key] && ++prve != cur)//如果cur小就停下与prve交换，前提是++prve不能与cur相等，防止自己与自己交换
			Swap(&a[cur], &a[prve]);
		cur++;//如果cur大就继续向前走
	}
	Swap(&a[prve], &a[key]);//cur走出范围key与prve交换
	return prve;
}
void Quicksort(int* a, int start, int end)
{
	ST s;
	StackInit(&s);//初始化栈
	StackPush(&s, start);
	StackPush(&s, end);//入栈第一个区间
	while (!StackEmpty(&s))//如果栈空就停止
	{
		int right = StackTop(&s);//获取存入元素
		StackPop(&s);//出栈，end
		int left = StackTop(&s);
		StackPop(&s);//strat
		int key = PartSort2(a, left, right);//单排
		if (key + 1 < right)//判断元素是否大于一个
		{
			StackPush(&s, key + 1);//右子树的右区间
			StackPush(&s, right);//入栈右子树的左区间
		}
		if (left < key - 1)
		{
			StackPush(&s, left);//左子树右区间
			StackPush(&s, key - 1);//左子树左区间
		}
	}
}
int main()
{
	int arr[] = { 6,2,7,1,3,4,10,8 };
	int n = sizeof(arr) / sizeof(arr[0]);
	Quicksort(arr, 0, n - 1);
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

时间复杂度为O(N*logN).

归并排序

递归

基本思想：

先拆分剩一个元素，然后将他们两个一组的进行排序，两个元素分别为不同组，进行排序合并变成了一组，如上图。 这也是二叉树的后序遍历，那么在比较两组数的时候要怎么进行重新排序呢？ 这里要创建一个数组，因为如果在原数组进行排序可能会产生原本的值被覆盖，处理起来很麻烦。 我们创建一个和原数组一样大的空间，哪里排序就放在哪个位置，并且，从小到大进行尾插：

这里还要注意，每两组排序完毕记得覆盖掉原来数组中的值。 代码实现：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void mergesort(int* a, int start, int end, int* tmp)
{
	if (start >= end)
	{
		return;//遇到一个元素就返回
	}
	int mid = (start + end) / 2;
	mergesort(a, start, mid, tmp);//左子树
	mergesort(a, mid + 1, end, tmp);//右子树
	int i = start;//新数组的下标
	int left1 = start;//第一组开始
	int right1 = mid;//第一组结束
	int left2 = mid + 1;//第二组开始
	int right2 = end;//第二组结束
	while (left1 <= right1 && left2 <= right2)//尾插进新的数组
	{
		if (a[left1] <= a[left2])
		{
			tmp[i++] = a[left1++];
		}
		else
		{
			tmp[i++] = a[left2++];
		}
	}
	while (left1 <= right1)//哪组没走完继续走
	{
		tmp[i++] = a[left1++];
	}
	while (left2 <= right2)
	{
		tmp[i++] = a[left2++];
	}
	memcpy(a + start, tmp  + start, sizeof(int) * (end - start + 1));//将新数组的内容拷贝到原数组
}
void _mergesort(int* a, int start, int end)//空数组
{
	int* tmp = (int*)malloc((end + 1) * sizeof(int));
	if (tmp == NULL)
	{
		perror("malloc error");
		exit(-1);
	}
	mergesort(a, start, end, tmp);
	free(tmp);
	tmp = NULL;
}
int main()
{
	int arr[] = { 6,2,7,1,3,4,10,8 };
	int n = sizeof(arr) / sizeof(arr[0]);
	_mergesort(arr, 0, n - 1);
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

时间复杂度O(N*logN).

非递归

大体思路是没变的，还是需要靠新的数组，不过非递归的细节会非常的复杂：

核心思路还是两两一组，只不过是从原数组中直接去找单个元素排序，然后形成新的一组，再将新的组进行排序。（其实和希尔排序有点类似，这里的gap是一组中的元素个数）。 我们先对于上面这组数进行代码实现：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void MergeSortNonR(int* a, int start, int n)//创建新数组
{
	int* tmp = (int*)malloc(sizeof(int) * (n));
	if (tmp == NULL)
	{
		perror("malloc error");
		exit(-1);
	}
	for (int gap = 1; gap < n; gap = 2 * gap)//一组多少个元素
	{
		for (int j = 0; j < n; j += 2 * gap)//j是每组的开头
		{
			int i = j;//新数组的下标
			int left1 = j;//第一组开始
			int right1 = j + gap - 1;//第一组结束
			int left2 = j + gap;//第二组开始
			int right2 = j + 2 * gap - 1;//第二组结束
			while (left1 <= right1 && left2 <= right2)//尾插进新的数组
			{
				if (a[left1] <= a[left2])
				{
					tmp[i++] = a[left1++];
				}
				else
				{
					tmp[i++] = a[left2++];
				}
			}
			while (left1 <= right1)//哪组没走完继续走
			{
				tmp[i++] = a[left1++];
			}
			while (left2 <= right2)
			{
				tmp[i++] = a[left2++];
			}
			memcpy(a + j, tmp + j, sizeof(int) * (right2 - j + 1));//将新数组的内容拷贝到原数组
		}
	}
	free(tmp);
	tmp = NULL;
}
int main()
{
	int arr[] = { 6,2,7,1,3,4,10,8 };
	int n = sizeof(arr) / sizeof(arr[0]);
	MergeSortNonR(arr, 0, n);
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

这组数非常顺利，但是我们发现，这组数是可以一直被平分成两组的，如果是奇数呢？或者是10个数呢？

这时候就会出现这种情况 ，只要不是2N就不能向上面那样解决了，肯定会有分不到的组。 那么我们可以让5和9组成的这组先等下，等前面四组排序组成新的一组时就可以变成两组排序了。

像这样就可以了，实现这个逻辑就去判断分组的时候是否下标越界。 我们也发现了一个规律，如果第一组的left1没有遇到任何数则不会有后面的数，只有left1遇到了一个数，比如这组的5（假设right1没遇到9），这才说明这组不能像之前的代码一样去解决问题，因为在第一次进行分组的时候5就不会被分配到任何一组。 分组不均匀的三种情况是：

第一组中右区间缺失 第一组无缺失，第二组全缺失 第二组右区间缺失

但是这里要注意一下，两组中只要有数据就会合成一组，并不是每组都一样的数量才会合成一组。 所以在判断第三组的右区间越界的时候不能直接跳出，需要修正区间。 代码实现：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void MergeSortNonR(int* a, int start, int n)//创建新数组
{
	int* tmp = (int*)malloc(sizeof(int) * (n));
	if (tmp == NULL)
	{
		perror("malloc error");
		exit(-1);
	}
	for (int gap = 1; gap < n; gap = 2 * gap)//一组多少个元素
	{
		for (int j = 0; j < n; j += 2 * gap)//j是每组的开头
		{
			int i = j;//新数组的下标
			int left1 = j;//第一组开始
			int right1 = j + gap - 1;//第一组结束
			int left2 = j + gap;//第二组开始
			int right2 = j + 2 * gap - 1;//第二组结束
			if (right1 >= n)//第一组右区间越界
			{
				break;//跳出去原来的组会被放在tmp数组中
			}
			if (left2 >= n)//第二组全越界
			{
				break;
			}
			if (right2 >= n)//第二组右区间越界
			{
				right2 = n - 1;//修正
			}
			while (left1 <= right1 && left2 <= right2)//尾插进新的数组
			{
				if (a[left1] <= a[left2])
				{
					tmp[i++] = a[left1++];
				}
				else
				{
					tmp[i++] = a[left2++];
				}
			}
			while (left1 <= right1)//哪组没走完继续走
			{
				tmp[i++] = a[left1++];
			}
			while (left2 <= right2)
			{
				tmp[i++] = a[left2++];
			}
			memcpy(a + j, tmp + j, sizeof(int) * (right2 - j + 1));//将新数组的内容拷贝到原数组
		}
	}
	free(tmp);
 	tmp = NULL;
}
int main()
{
	int arr[] = { 6,2,7,1,3,4,10,8,5,9 };
	int n = sizeof(arr) / sizeof(arr[0]);
	MergeSortNonR(arr, 0, n);
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

非比较排序

计数排序 基本思想： 就像哈希表一样，用一个数组来映射另一个数组。

先找原数组最小的值和最大的值，因为创建一个新数组要和原数组最小与最大的差值一样大。 创建好一个数组之后，我们将原数组映射到新数组下标对应的位置：

最小的映射在下标为0的位置，第二小的映射在减去最小值下标的位置。 最后在映射的地方进行++，映射几次就加几次：

最后我们利用新建数组进行排序，下标加上最小值，从下标为0的地方开始，没有就不放回原数组：

代码实现

#include <stdio.h>
#include <stdlib.h>
void countingsort(int* a,int n)
{
	int max = a[0];//假设最大最和小值在下标为0的位置
	int min = a[0];
	for (int i = 0; i < n; i++)//在原数组中找最大的
	{
		if (max < a[i])
		{
			max = a[i];
		}
	}
	for (int i = 0; i < n; i++)//在原数组中找最小的
	{
		if (min > a[i])
		{
			min = a[i];
		}
	}
	int sum = abs(min) + abs(max) + 1;//新数组的长度
	int* tmp = (int*)malloc(sum * sizeof(int));//开辟新数组
	if (tmp == NULL)
	{
		perror("malloc error");
		exit(-1);
	}
	for (int i = 0; i < sum; i++)
	{
		tmp[i] = 0;// 新数组的初始化
	}
	for (int i = 0; i < n; i++)//映射到新数组
	{
		if (a[i] == min)
		{
			tmp[0]++;
		}
		else if (a[i] > min)
		{
			int x = a[i] - min;
			tmp[x]++;
		}
	}
	int j = 0;//原数组下标
	for (int i = 0; i < sum; i++)
	{
		while (tmp[i]--)
		{
			a[j] = i + min;//新建数组映射到原数组
			j++;
		}
	}
	free(tmp);
	tmp == NULL;
}
int main()
{
	int arr[] = { -1,-5,3,7,7,5,-1,3 };
	int n = sizeof(arr) / sizeof(arr[0]);
	countingsort(arr, n);
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

时间复杂度：O(N+sum) 空间复杂度：O(sum) 稳定性：稳定 缺点：只能对整形排序

排序的复杂度与稳定性

什么是稳定性 上面除了计数排序，剩下的都是可以针对自定义类型进行排序的，我举个例子：

排序前红色的5在黑色的5前面，黑色的1在红色的1前面，排序后红黑颠倒了，这就是不稳定，如果是整数确实没什么，如果是自定义类型就麻烦了，红色的1中可能会有其他的成员变量，黑色的也有其他不同的成员变量。 比如高考的时候，全国有很多分数相同的同学，但是我想先看谁语文分数高，然后在进行总分的排序，如果用一个稳定的排序就不会打乱原来的排序。 直接插入排序 时间复杂度：O(N2) 空间复杂度：O(1) 稳定性：稳定 在排序的过程中遇到相同的数就会停下。 希尔排序 时间复杂度：O(N1.3) 空间复杂度：O(1) 稳定性：不稳定 分组的时候容易将相同的数据分到不同的组。 选择排序 时间复杂度：O(N2) 空间复杂度：O(1) 稳定性：不稳定

蓝色的5和黑色的5顺序没变，但是蓝色的8和黑色的8顺序变了。 堆排序 时间复杂度：O(N*logN) 空间复杂度：O(1) 稳定性：不稳定 这个太不稳定了。 冒泡排序 时间复杂度：O(N2) 空间复杂度：O(1) 稳定性：稳定 快速排序 时间复杂度：O(N*logN) 优化后的 空间复杂度：O(logN) 取决于树的深度 稳定性：不稳定 归并排序 时间复杂度：O(N*logN) 空间复杂度：O(N) 稳定性：稳定 在排序的过程中是尾插进新数组的，遇到相同的就尾插到后面，非常稳定。

相关文章