【数据结构初阶】八大排序算法+时空复杂度

学会控制自己是人生的必修课

一、插入排序

1.直接插入排序

1.直接插入排序思想： 假设现在已经有一个有序序列，如果有一个数字插入到这段序列的末尾，我们会选择拿这个数和它前面的每个数字都比较一遍，如果前面的数字比他大，那我们就让前面的数字赋值到这个被插入的数字位置，依次与前面的数字进行比较，最后我们把插入有序序列的数字放到他应该在的位置

void InsertSort(int* arr, int n)
{
	for (int i = 0; i < n-1; i++)
	{
		int end = i;//end是指有序序列最后一个数字的下标
		int tmp = arr[end+1];//需要暂存一下尾部位置的元素
		while (end >= 0)
		{
			if (arr[end] > tmp)
			{
				arr[end + 1] = arr[end];
				end--;
			}
			else
			{
				break;
			}
		}
		arr[end+1] = tmp;
	}
}

2.代码细节说明：
一般来说，我们还是习惯将end定义为有序序列的最后一个数字的下标，如果我们将它定义为被插入数字的下标的话，比较的时候，我们就得往前比，end-1和end比，如果你喜欢这样定义的话，那也可以，后面的希尔排序，你也这样定义，比较的时候拿end-gap和end比较，也可以，没什么问题。
但是我个人觉得还是有些别扭的，我还是推荐大家将end定义为有序序列最后一个数字的下标，这样在逻辑思考上面还是对我们很有帮助的。

2.希尔排序

1.希尔排序思想： 将一整组数据分成gap组，我们先将这gap组进行组排序，将每组排好之后，可以让较大的数据尽快到后面，较小的数尽快到前面，然后我们逐渐减小gap直到1，进行最后的一次直接插入排序，最后的这次排序进行完毕，我们就可以得到一个有序序列了。

void ShellSort(int* arr, int n)//我的希尔排序一点问题都没有
{
	int gap = n;
	while (gap > 1)//当while循环里面gap为1时，排序一次之后，循环结束，排序结束
	{
		gap = gap / 3 + 1;//保证我们的最后一次排序为直接插入排序，而不是预排序
		for (int i = 0; i < n - gap; i++)//实现gap组并排，并且最后一次排序为直接插入排序
		{
			int end = i;//end为最后一个有序数字的下标
			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;
		}
	}
}

2.代码细节说明：
a. gap其实就是间距，希尔排序其实就是直接插入排序基础上的一种升华，gap/3+1是为了保证最后一次gap为1，而不是0.
如果你对于直接插入排序理解较好的话，那其实希尔排序也是很好理解的，我们只不过将数据进行了一个分组，然后进行组排序，这样会很节省时间，遍历数据的个数也会减少下来，等到最后一次排序的时候，我们也无需遍历大量的数据了，只需遍历个别不满足升序的数据即可，我们可以看到组成希尔排序的每个部分所消耗的时间其实都是短的，这也就是希尔排序效率高的一个原因，因为它可以很快的将数据归位，并且每次归位的时间消耗相比于直接插入排序，要优化很多，这也是希尔排序效率高的原因所在。
希尔排序=预排序+直接插入排序

3.希尔排序的时间复杂度：
分成gap组，每组N/gap个数据。
每组最坏的情况下的挪动次数：1 + 2 + 3 + …… + N / gap - 1 等差数列
总次数：(1 + 2 + 3 + …… + N / gap - 1) * gap次。这个次数没算外层的while循环

最开始gap很大：(N / 3 + 1)，代入到总次数可得(1 + 2 + …… 3)* (N / 3 + 1)，很接近于O(N)

……
快结束时，gap很小，带入到总次数可得总次数接近于等差数列，应该是O(N²)，但其实并不是，因为这是最后的一次预排序，接近有序，所以我们可以近似为O(N)

我们可以将每一次的预排序的运行次数看作O(N)

N/3/3/3/3……/3/3/3=1
N/2/2/2/2……/2/2/2=1
所以预排序的次数是logN，2和3作为log的底数我们不管。所以次数就是logN
那我们其实就可以毛估出来希尔排序的时间复杂度大概是O(N*logN)这个级别的。

但希尔排序的时间复杂度并不是我们毛估出来那样的，其实它的计算难度非常大，因为随着gap的减小，总次数左右两边都是较为趋近于N的，这个时候，他的时间复杂度其实是不可以看作O(N)这类的了，我们这里给出希尔排序时间复杂度的结论，O(N^1.3)，有关的严格数学证明，大家可以自己网上搜索或查阅资料

排序这个地方的时间复杂度有两个量级：一个是O(N^2)，一个是O(N*logN)，希尔排序，堆排序，快排，归并排序，等都是重量级的排序，自然学习的难度也是较大。

二、选择排序

1.直接选择排序

1.直接选择排序思想： 我们每次将数组遍历一遍，每遍历一遍就选出最大和最小的数字将其放在序列的首尾，直到将序列遍历完毕或者遍历的只剩一个数字时，我们的序列也就变得有序了。

void SelectSort(int* arr, int n)
{
	//选出来最大和最小的数分别放在左右两端
	int begin = 0, end = n - 1;
	while (begin < end)
	{
		int mini = begin, maxi = begin;
		for (int i = begin; i <= end; i++)
		{
			
			if (arr[i] < arr[mini])
			{
				mini = i;
			}
			if (arr[i] > arr[maxi])
			{
				maxi = i;
			}
		}
		if (maxi == begin)
//我们这里需要做一下调整，因为有可能最大元素的位置在begin的位置，这样我们以交换元素之后，maxi的位置就是最小元素了。
//所以如果maxi在begin的位置上，我们就需要事先把maxi的下标改为mini的下标，这样在交换元素过后，mini正好就是最大元素了。
			maxi = mini;
		Swap(&arr[begin], &arr[mini]);
		Swap(&arr[end], &arr[maxi]);
//下面那次不用调整的原因是，上面调整过后，maxi位置肯定不存在最小元素的情况，所以不存在交换最大元素和end位置时，出现最小元素在end
//位置，因为我们是先交换begin和mini，所以下面再次交换时，肯定是不会出问题的，因为我们上面已经交换过了。

		begin++;
		end--;
	}
}

2.代码细节说明：
如果出现最大元素下标正好在left位置的时候，我们第二次交换max和right一定会出问题，所以我们需要对这样的情况做出调整，将max的下标改为min的下标。
当然也有人或许会有疑问，那最小元素如果出现在right位置时，你不需要做出调整么？答案是：不需要做出调整，只需要调整一次就够了。
因为我们交换元素的顺序是先交换小在交换大，所以只要交换小不出问题，后面的交换大肯定也不会出问题。

2.堆排序（已经建好堆的基础之上）

1.堆排序思想： 升序建大堆，降序建小堆，不断的利用向下调整算法将堆顶元素依次放到堆尾。记得父节点和子节点之间的关系：parent=(child-1)/2不要给忘了。我们每重新调整堆时，传给向下调整算法的数组个数要减1，因为我们交换一次，数组的最后一个元素已经变得有序了，不需要我们调整了。

—————————————————————————————————————

void AdjustDownTeach(HPDataType* array, int n, int parent)
{
	int child = parent * 2 + 1;//上来我们就先假设最大的孩子是左孩子

	while (child<n)//我们想的是循环结束的条件，写的是循环继续的条件
	{
		//保证有右孩子的同时，看看我们的假设是否正确，错误就调整
		if (child + 1 < n && array[child + 1] > array[child])
		//如果假设错误，我们将孩子改为右孩子，并且你也有可能没有右孩子，没有右孩子，默认左孩子就是最大的
		//这里其实不用担心没有孩子的问题，因为如果parent没有孩子，child被赋值过后肯定大于n了直接跳出循环了就。
		{
			++child;//将下标自增，左孩子就变为右孩子
		}
		if (array[parent] < array[child])//我们这里建的是大堆
		{
			Swap(&array[parent], &array[child]);
			parent = child;
			child = parent * 2 + 1;//这里再重新假设左孩子是大的，下一次循环就是先看看我们的假设是否正确，若不正确就进行调整。
		}
		else
		{
			break;
		}
	}
}
void HeapSort(int* arr, int n)
{
	for (int i = 1; i < n; i++)
	{
		Swap(&arr[0], &arr[n - i]);
		AdjustDownTeach(arr, n - i, 0);//我们传过去的数组大小是需要逐渐减小的，所以传的是n-i
	}
}

2.代码细节说明：
a. 无论是建堆还是堆排序，其核心主要还是在于向下调整算法，既能帮助我们建堆，又能帮助我们对堆进行排序。我们主要说明一下向下调整算法的代码细节。

b. 由于每次判断左孩子和右孩子哪个大很费时间，并且代码写起来不够精炼，所以这里利用了一个代码技巧，就是上来就假设左孩子是最大的，如果我们假设错误，那就重新进行调整，在调整的那部分代码，有一个很坑的地方就是，有可能父节点没有右孩子，此时在if语句的条件判断部分就出现了越界访问的问题，所以我们还要加上一个判断条件，就是保证有右孩子的同时，去看一下我们的假设是否正确。

c. 另外有关于向下调整算法什么时候向下调整结束，我们这里也要说一下，一定是child>=n时，循环就要结束了，说一下为什么child==n循环就结束就可以了，因为child>n循环肯定是要结束的，这个应该是很好理解的，我也就不多说了。

三、交换排序（Swap）

1.冒泡排序（大学牲最熟悉的排序）

1.冒泡排序思想： 每遍历一次序列就将最大的元素交换到序列的最后面，直到遍历的序列中元素仅剩1个时，冒泡排序结束。

void BubbleSort(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		int exchange = 0;
		for (int j = 0; j < n - 1 - i; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				Swap(&arr[j], &arr[j + 1]);
				exchange = 1;
			}
		}
		if (exchange == 0)
		{
			break;//数组元素已经有序，不用继续排序了，跳出循环即可。
		}
	}
}

2.代码细节说明： 就简单的做了一个优化，如果我们排序的某一趟每个元素都不用交换，则说明这一趟要排序的元素已经有序，那后面的每趟排序其实就不用进行了，我们选择直接跳出循环。

2.快速排序（The fastest sort of all sorts有点儿装B，但确实挺快）

2.1 hoare版本

1.hoare排序思想： 我们默认序列左起第一个数为key，我们定义两个下标left和right分别从序列的左边和右边去找值，left找比key大的值，right找比key小的值，找到之后，交换left和right的值，等到left和right相遇的时候，此时的值一定是比key小的值，我们再把key和这个相遇位置的值进行交换，这样key就回到它应有的正确位置上，我们再递归处理key的左边区间和右边区间，递归结束之后，快排也就结束了。

int PartSort1(int* arr, int left, int right)
{
	//1.默认左边的数为key值
	//2.先让右边的数走，找小。再让左边的数走，找大，交换两个元素
	//3.当两边相遇的时候，相遇位置一定是比key要小的值，交换key和相遇位置
	
	int key = left;
	while (left<right)
	{
		while (left < right && arr[right] >= arr[key])
		{
			right--;
		}
		while (left < right && arr[left] <= arr[key])
		{
			left++;
		}
		Swap(&arr[left], &arr[right]);
	}
	Swap(&arr[key], &arr[left]);
	key = left;
	return key;
	
void QuickSort(int* arr, int begin, int end)
{
	if (begin>=end)//递归结束条件
	{
		return;
	}
	int key = PartSort1(arr, begin, end);

	QuickSort(arr, begin, key - 1);
	QuickSort(arr, key + 1, end);
}
}

2.代码细节说明：
代码思路看起来比较简单，其实实现的时候，有很多坑人的地方。
a. 如果key后面的每个数都比key小或大的话，那left向后面找或right向前面找，就会产生越界访问的问题，为了防止这样情况的产生，我们选择在if语句的判断部分加个逻辑与&&保证left小于right，以免产生越界访问的问题。
b. 我们在if语句的判断部分，找的数一定得比key小或大，连相等都是不可以的，为什么呢？因为会产生死循环。
一旦序列中的左右出现相等的数字的时候，我们if语句如果写成＞或＜而不是>=或<=，程序就废了。

2.2 三数取中+小区间优化

三数取中就是为了让我们选取的key在序列中的位置尽量靠中间，让我们递归处理的效率更高。

int GetMidIndex(int *arr, int begin, int end)
{
	int mid = (begin + end) / 2;
	if (arr[begin] > arr[end])
	{
		if (arr[end] > arr[mid])
		{
			return end;
		}
		else if (arr[begin] < arr[mid])
		{
			return begin;
		}
		else
		{
			return mid;
		}
	}
	else// arr[begin] < arr[end]
	{
		if (arr[mid] < arr[begin])
		{
			return begin;
		}
		else if (arr[end] > arr[mid])
		{
			return mid;
		}
		else
		{
			return end;
		}
	}
}

小区间优化是为了让递归深度不要太深，因为数据量过大以后，我们递归的深度就会增加，递归建立的栈帧数量会随着递归深度的增加而增加，又因为栈空间本身就小，很容易造成栈溢出的问题，这时我们就想到了一个办法，例如当递归区间的数据量较小的时候，我们不采用递归解决他们，而是换成直接插入的方法来解决较小数据量的排序。

void QuickSort(int* arr, int begin, int end)
{
	if ((end - begin) < 1)//递归结束条件
	{
		return;
	}
	if ((end - begin + 1) < 15)
	{
		InsertSort(arr + begin, end - begin + 1);
	}
	else
	{
		int key = PartSort1(arr, begin, end);
		QuickSort(arr, begin, key - 1);
		QuickSort(arr, key + 1, end);
	}
}

2.3 挖坑法版本

1.挖坑法思想： 挖坑法的思想还是要比hoare大佬的思想更加容易理解的，整体是一个什么思想呢？
我们先在序列的最左边挖一个坑，然后这个坑位的值就是key值，然后从右往左找比key小的值填到坑位上面去，这个时候坑位就变成right位置了，我们再从左向右找比key大的值，把这个值填到坑位上面去，再将坑位更新为left，循环进行这个工作，直到left和right相遇，他们相遇的位置也就是最后一次hole的位置，我们将key填到hole的位置，这样key就回到它本身的位置了。
剩下的工作我们还是交给递归，递归处理左区间和右区间。

int PartSort2(int* arr, int left, int right)
{
	int mid = GetMidIndex(arr, left, right);
	Swap(&arr[left], &arr[mid]);
	int hole = left;
	int key = arr[left];
	while (left<right)
	{
		while (left < right && arr[right] >= key)
		{
			--right;
		}
		arr[hole] = arr[right];
		hole = right;
		while (left < right && arr[left] <= key)
		{
			++left;
		}
		arr[hole] = arr[left];
		hole = left;
	}
	arr[hole] = key;
	return hole;
}

2.代码细节说明：
填好坑位的值之后，我们要记得将坑位进行更新，最后坑位的下标其实就是key应该在的位置的索引。
实现起来还是较为简单的，有了前面hoare版本的铺垫。

2.4 前后指针版本

1.前后指针思想： 我们定义两个指针一个cur一个prev，利用cur去找比key小的值，然后交换cur和prev++的值，让cur不断的向后找比key小的值，等到cur找完整个数组之后，prev位置的值肯定是比key要小的，所以prev的位置其实就是key最终应该待在的位置，这样我们就处理好key了。
剩下的还是交给递归处理。

int PartSort3(int* arr, int left, int right)
{
	int mid = GetMidIndex(arr, left, right);
	Swap(&arr[left], &arr[mid]);
	int key = left;
	int prev = left, cur = left + 1;
	while (cur <= right)
	{
		if (arr[cur] < arr[key] && ++prev != cur)//逻辑与后面的条件就是为了防止交换同一个位置的元素，这时交换没有必要
		{
			Swap(&arr[cur], &arr[++prev]);
		}
		cur++;
	}
	Swap(&arr[key], &arr[prev]);
	return prev;
}

2.代码细节说明：
有的人可能看到++prev!=cur时，有些蒙，但其实这个就是为了避免同一位置的值交换多次所做的优化。
cur是需要一直向后走的，我们只需要判断cur的每一个位置的值和key的关系并将其处理即可。

2.5 三指针版本（快排的终极优化，可适用任何刁钻的数据分布）

1.三指针思想：
假设某个序列中几乎所有数据都是相同的，并且数据量极大的情况下，原来的快排就无法适用了，因为要建立很多栈帧，递归深度太深，运行时间过长，那些几乎所有相同的数据，我们完全可以将其集中起来，把他们放到他们应该在的位置，不对其作任何处理。
这时候就从原来的前后指针版本衍生出我们的三指针版本。

大体思路：
定义left，right，cur等三个下标，利用cur对序列的遍历，找出大于key，等于key，小于key的各个数字，将他们交换到left和right等下标位置，然后递归剩余的左右区间，完成我们的排序。

void QuickSortPlus(int* arr, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	if ((end - begin + 1) < 15)
	{
		InsertSort(arr + begin, end - begin + 1);
	}
	else
	{
		int mid = GetMidIndex(arr, begin, end);
		Swap(&arr[begin], &arr[mid]);

		int key = arr[begin];
		int left = begin, right = end, cur = begin + 1;
		while (cur <= right)
		{
			if (arr[cur] < key)
			{
				Swap(&arr[left], &arr[cur]);
				left++;
				cur++;
			}
			else if (arr[cur] > key)
			{
				Swap(&arr[cur], &arr[right]);
				right--;
			}
			else//arr[cur]==key时
			{
				cur++;
			}
		}
		QuickSortPlus(arr, begin, left - 1);
		QuickSortPlus(arr, right + 1, end);
	}

}

2.代码细节说明：
因为我们是将left位置看作key，所以只有交换比key小的元素时，cur才可以++，或者遇到和key相等的值时，cur可以++，我们必须保证left左侧都是比key小的值，left和right中间都是和key相等的值，right右侧都是比key大的值。
然后我们递归begin到left-1，right+1到end两个区间，即可完成排序。

3.快速排序（非递归）

1.快排非递归思想：
我们可以利用栈结构来存储递归区间，然后再利用快排的随便一个算法模块儿对这个区间进行排序，之后再继续入栈剩余的区间，并进行排序。

void QuickSortNonR(int* arr, int begin, int end)
{
	ST st;
	StackInit(&st);
	StackPush(&st, begin);
	StackPush(&st, end);

	while (!StackEmpty(&st))
	{
		int right = StackTop(&st);
		StackPop(&st);
		int left = StackTop(&st);
		StackPop(&st);

		int key = PartSort3(arr, left, right);

		// [begin,key-1]  [key+1,end]
	
		if (key + 1 < right)//key+1==right说明区间只剩一个值，无需入栈了，一个元素可以认为有序
		{
			StackPush(&st, key+1);
			StackPush(&st, right);
		}

		if (left < key - 1)
		{
			StackPush(&st, left);
			StackPush(&st, key-1);
		}
		
	}
	StackDestroy(&st);
}

2.代码细节说明：
只要区间长度大于等于2，我们就需要继续入栈剩余的区间，其实非递归还是延续了递归的思想，我们用入栈出栈模拟了递归的过程。

四、归并排序（尾插法的再次邂逅）

1.归并排序

1.归并排序思想：
归并都是用于两端序列的归并，我们数组如果要使用归并来进行排序的话，毫无疑问，也是需要将数组分为两段，将他们合并到一个tmp数组里面，然后将tmp数组里面的内容归到原来的数组arr里面。所以思路还是很简单的，因为我们以前链表就做过两个链表合并为一个链表这样的题，所以这里我们在理解上应该是没有什么问题的。

合并的前提是两段序列得是有序的，但没有这样的条件啊，怎么办呢？我们想到了递归，一个数当然可以认为是有序的，我们可以将两个数进行归并，我们将这两个数可以看作两段有序序列，这样便可以解决问题了。

void _MergeSort(int* arr, int begin, int end, int* tmp)
{
	if (begin >= end)
	{
		return;
	}
	int mid = (begin + end) / 2;
	_MergeSort(arr, begin, mid , tmp);
	_MergeSort(arr, mid + 1, end, tmp);
	int i = begin;
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] <= arr[begin2])//等于时我们取前一个，保证算法的稳定性
		{
			tmp[i++] = arr[begin1++];
		}
		else
		{
			tmp[i++] = arr[begin2++];
		}
	}
	while (begin1 <= end1)
	{
		tmp[i++] = arr[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[i++] = arr[begin2++];
	}
	memcpy(arr+begin, tmp+begin, sizeof(int) * (end - begin + 1));
}
void MergeSort(int* arr, int begin, int end)
{
	int* tmp = (int*)malloc(sizeof(int) * (end - begin));
	_MergeSort(arr, begin, end-1, tmp);

	free(tmp);
	tmp = NULL;
}

2.代码细节说明：

a. 因为我们递归到子区间的时候，将tmp拷贝回arr拷贝的位置并不始终都是从tmp开头的位置拷贝的，有可能我们左边区间处理完毕，开始处理右半区间的时候，尾插到tmp时也是从tmp的右半区间开始处理的，所以拷贝时拷贝的位置应该是arr+begin和tmp+begin

b. 在tmp尾插时，同样容易犯错误的一个地方就是，习惯将i定义为0，和上面相同，我们处理的区间不仅仅只有左半区间，在处理右半区间的时候，也应该从begin下标位置开始处理，因为begin代表的是区间的头位置，我们尾插时当然也要从tmp相对应arr的位置开始尾插
c. 我在写这个代码时，受前面快排的影响，在定义end1时，不小心定义成mid-1了，这样就把mid位置的元素落下了，结果代码就挂了，我们递归可不是前面key那样啊，每一个元素都不可以落下的，要真正实现归并，每一个元素都要参与尾插的过程。

2.非递归—归并排序（最大的大佬在这儿呢）

1.非递归排序思想：
如果你要用栈或队列实现非递归的话，其实是非常难搞的，因为你入栈左或右区间之后，想要继续，那肯定得pop掉原来你入进去的区间，然后重新去入新的子区间，正是由于你pop掉原来的区间，也就导致了无法进行两个大的区间合并，所以利用这两个数据结构是无法完成我们的操作的。

我们可以不借助其他数据结构，直接对序列进行归并排序。

定义一个rangeN代表需要归并的两个区间内各自的数据个数，从1开始，因为1个数据我们可以认为是有序的，然后就两个两个区间开始进行归并，每遍历完一遍数组之后，开始下一轮的归并，我们这时候增大rangeN，保证最后几轮的时候，将两个大区间直接归并成一个完整的序列，这时候我们的while循环就可以停止了，因为序列的最大两个区间已经归并成一个完整的升序序列了。

//写法一：
void MergeSortNonR(int* arr, int n)//栈和队列进行非递归都非常不好搞
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

	//rangeN代表归并的每组数据个数，从1开始，因为一个数认为是有序的，可以直接进行归并。
	int rangeN = 1;
	while (rangeN < n)
	{
		for (int i = 0; i < n; i += 2 * rangeN)
		{
			//这里面要实现两个组数据的归并
			// [begin1,end1][begin2,end2] 归并

			int begin1 = i, end1 = i + rangeN - 1;//归并区间1
			int begin2 = i + rangeN, end2 = i + 2 * rangeN - 1;//归并区间2，加上2倍的rangeN之后，就跳到下一组了，-1正好就是本组的最后一个元素
			printf("[%d,%d][%d,%d]\n", begin1, end1, begin2, end2);
			int j = i;
			//end1 begin2 end2越界
			if (end1 >= n)
			{
				//修正区间  ->拷贝数据可以整体拷贝，也可以归并每组拷贝，因为无论哪种，tmp中的数据不会存在随机值的情况
				end1 = n - 1;
				//让第一个区间修正成一个正确的区间
				//将第二个区间修正成一个不存在的区间。
				begin2 = n;
				end2 = n - 1;
			}
			else if (begin2 >= n)
			{
				//修正成不存在的区间
				begin2 = n;
				end2 = n - 1;
			}
			else if (end2 >= n)
			{
				end2 = n - 1;
			}
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (arr[begin1] <= arr[begin2])//加个等号，遇到相同数字，取前一个。
				{
					tmp[j++] = arr[begin1++];
				}
				else
				{
					tmp[j++] = arr[begin2++];
				}
			}

			while (begin1 <= end1)
			{
				tmp[j++] = arr[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[j++] = arr[begin2++];
			}
			//强烈推荐归并一点，我们就往原数组拷贝回去一点，别一次性就全都拷贝回去

			memcpy(arr + i, tmp + i, sizeof(int) * (end2 - i + 1));
			//拷贝的个数是2*rangeN是不可以的，因为数据有可能不是恰好分成整数个组，我们有时可能只拷贝一个数据。
		}

		//也可以整体归并完了，再统一将tmp数组拷贝回arr里。
		//memcpy(arr, tmp, sizeof(int) * n);//这就是整体拷贝。

		rangeN *= 2;
	}
	free(tmp);//防止内存泄露
	tmp = NULL;
}
//rangeN是归并的每组的数据个数，然后我们两两为一组，进行归并。
//然后我们每次让range扩大二倍，最后的两组进行归并，结束后，我们就可以得到一个完整的归并序列了。

//先前有问题的逻辑：
//但到了10个测试数据的时候，由于他不是2的n次方个，无法被两两分成一个归并组，出现越界访问。例如rangeN==2时，两两分为一组，肯定有两个
//数据被落下，无法和其他数据凑成一个归并组。除了这样的情况之外，还有很多其他的越界情况，我们需要一一分析


//如果你是修正了区间，以防越界访问的话，那既可以整体拷贝，也可以部分拷贝。
//如果你遇到越界访问，选择跳出归并循环的话，那就不可以整体拷贝，只能部分拷贝。

//写法二：
void MergeSortNonR(int* arr, int n)//栈和队列进行非递归都非常不好搞
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

	//rangeN代表归并的每组数据个数，从1开始，因为一个数认为是有序的，可以直接进行归并。
	int rangeN = 1;
	while (rangeN < n)
	{
		for (int i = 0; i < n; i += 2 * rangeN)
		{
			//这里面要实现两个组数据的归并
			// [begin1,end1][begin2,end2] 归并

			int begin1 = i, end1 = i + rangeN - 1;//归并区间1
			int begin2 = i + rangeN, end2 = i + 2 * rangeN - 1;//归并区间2，加上2倍的rangeN之后，就跳到下一组了，-1正好就是本组的最后一个元素
			printf("[%d,%d][%d,%d]\n", begin1, end1, begin2, end2);
			int j = i;
			//end1 begin2 end2越界
			if (end1 >= n)
			{
				//如果你不修正直接走break，那你是不能整体拷贝的，因为tmp中有一部分值会是随机值，
				break;
			}
			else if (begin2 >= n)
			{
				break;
			}
			else if (end2 >= n)
			{
				end2 = n - 1;//对end2进行修正
			}
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (arr[begin1] <= arr[begin2])//加个等号，保证归并排序是稳定的，遇到相同数字，我们取前一个
				{
					tmp[j++] = arr[begin1++];
				}
				else
				{
					tmp[j++] = arr[begin2++];
				}
			}

			while (begin1 <= end1)
			{
				tmp[j++] = arr[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[j++] = arr[begin2++];
			}
			
			memcpy(arr + i, tmp + i, sizeof(int) * (end2 - i + 1));
			//拷贝的个数是2*rangeN是不可以的，因为数据有可能不是恰好分成整数个组，我们有时可能只拷贝一个数据。
		}
		rangeN *= 2;
	}
	free(tmp);//防止内存泄露
	tmp = NULL;
}

2.代码细节说明：
a. 正因为分成的归并组的情况是未知的，所以我们才会出现多种多样的越界情况，又由于每种越界情况不同，所以我们要单独拉出来每一种情况进行解决。

当我们有8个数据，并且没有对越界情况进行处理时，可以看到，有许多归并区间存在越界情况，所以我们不得不进行分批处理。

b. 我个人还是比较推荐前两种越界情况break解决的，因为这样还是比较省事，但是拷贝的时候我们只能在for循环里面进行拷贝，也就是部分拷贝，如果在for循环外面进行拷贝的话，arr中就会出现随机值，因为你break的时候，其实并没有给tmp数组进行赋值，所以tmp数组中的部分值是随机值。

c. 再给tmp数组进行尾插时，我们需要一个新的循环变量j，如果你不小心用i的话（没错就是博主本人😢😢😢），for循环的条件就被你改了，程序一定会出问题。

五、非比较排序—计数排序

1.计数排序思想：

我们利用一个统计数组来统计原数组中每个数字出现的次数，统计数组中非0元素的下标就是我们arr中所出现的元素。
所以我们最后再遍历一遍统计次数的数组，将每个元素赋值到arr数组即可。

总共需要遍历三遍数组。
第一遍：遍历arr数组，确定arr数组中的最大值和最小值，以此来确定一个范围，arr中的数据基本都在哪个范围，待会儿我们可以利用相对映射，通过countA数组的下标取到arr中出现的数据。
第二遍：遍历arr数组，将每个数字出现的次数统计出来并存到countA数组里面
第三遍：遍历countA数组，利用下标+相对映射的关系，从左到右，也就是从小到大将每个元素重新赋值到arr数组里面去。

void CountSort(int* arr, int n)
{
	int max = arr[0], min = arr[0];
	for (int i = 0; i < n; i++)
	{
		if (arr[i] > max)
		{
			max = arr[i];
		}
		if(arr[i]<min)
		{
			min = arr[i];
		}
	}
	int range = max - min + 1;//[0,2]左闭右闭的情况下，数据的个数一定是要+1的。如果是开区间自然不用，(0,2]数据个数为2。
	//统计次数
	int* countA = (int*)calloc(range, sizeof(int));
	if (countA == NULL)
	{
		perror("malloc fail\n");
		exit(-1);
	}
	for (int i = 0; i < n; i++)//再次遍历arr数组，统计其中数据出现的次数
	{
		countA[arr[i] - min]++;//这里就统计出数据出现的次数了
	}
	//遍历统计次数的数组，对原数组进行计数排序
	int j = 0;
	for (int i = 0; i < range; i++)
	{
		while (countA[i]--)//n--走n次，--n走n-1次。
		{
			arr[j++] = i + min;
			//这里又犯了一个严重的错误，利用了循环变量i，可千万不敢用循环变量i啊，要不然循环的情况就被你改了，代码又出问题了，你妹的。
		}
	}
	free(countA);
	countA = NULL;
}
//时间复杂度：O(N+range)，虽然有两层循环嵌套在一起，但不是×的关系，其实是加的关系。
//空间复杂度：O(range)
//适合数据范围集中，也就是range小
//只适合整型数据的排序，不适合浮点数、字符串等类型。

//如果数据较为集中的话，计数排序还是非常牛逼的，因为N大于range的话，我们的时间复杂度就是O(N)，老天爷，这性能不妥妥的很强么。

2.代码细节说明：

a. 最后一个遍历，对arr进型计数排序时，由于我们用的是相对映射，所以给arr赋值时，countA的每一个下标都要加上min来给arr进行赋值。
b. 在开辟countA数组时，对于它的大小，大家一定要牢记，左闭右闭开辟空间时一定要+1，就比如100到106有几种数字呢？答案是7种数字，所以我们在开辟空间时也要开辟max-min+1大小的空间。

六、排序总结

排序的稳定性：
a. 有很多人初次见到稳定性肯定想到的是，某个排序算法对于多种多样的数据分布能否呈现较稳定的效率，也就是某个算法能否在多种多样的数据里面仍然保持着高效的算法性能。包括我刚开始也是这么理解的，但其实并不是这样的。

b.定义： 如果某个排序算法在排序过程中，没有打乱原有序列中相同数据的相对位置关系，我们就称这个算法是稳定的。

七、时空复杂度

1.时间复杂度

时间是一去不复返的，累计的

时间复杂度算的就是基本操作的执行次数。

递归情况下就是算出每一个函数栈帧中的执行次数并且累加起来。

2.空间复杂度

空间是可以重复利用的，不累计
空间复杂度算的就是，这个算法在执行过程中所占用的最大存储空间。一般情况下都是O(1)，

我这里重点想说的是二叉树的空间复杂度，以前我一直以为画出来的一棵二叉树，它有多少个节点这个算法就要开辟多少个函数栈帧，但实际上不是这样的，他是边销毁边开辟函数栈帧，并且重新开辟函数栈帧利用的也是之前销毁的那块儿空间，这也就是为什么说空间是可以重复利用的，不累计。至于画出来的二叉树，那只是逻辑结构，具体的物理结构也是边销毁边开辟，二叉树只是我们人为想出来的逻辑结构，方便我们学习。
所以一棵二叉树的空间复杂度就是O(logN)，因为空间最大最大的时候，也就是顶满了，使用的也是二叉树高度个函数栈帧，后面的每一棵子树或节点都是利用之前递归到最深开始返回时，这一过程中所开辟的函数栈帧。
空间复杂度算的就是利用空间的峰值，也就是递归最深总共开辟logN个函数栈帧，那这颗二叉树的空间复杂度就是O(logN)。
比如某个算法空间复杂度是O(1),另一个算法是O(N),因为峰值那一下所需空间是O(N)，如果栈很小或者其他条件下，那O(1)的算法就可以跑过，O(N)的就无法跑过。文章来源地址https://www.toymoban.com/news/detail-789898.html

到了这里，关于【数据结构初阶】八大排序算法+时空复杂度的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！