【数据结构】排序（插入、选择、交换、归并） -- 详解_关于插入交换选择和归并排序算法比较

一、排序的概念及其运用

1、排序的概念

• 排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
• 稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i] = r[j]，且 r[i] 在 r[j] 之前，而在排序后的序列中，r[i] 仍在 r[j] 之前，则称这种排序算法是稳定的；否则称为不稳定的。
• 内部排序：数据元素全部放在内存中的排序。
• 外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

---

2、常见的排序算法

---

二、常见排序算法的实现

1、插入排序（Insertion Sort）

（1）基本思想

直接插入排序是一种简单的插入排序法，其基本思想是： 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中。重复这个过程，直到所有的记录插入完为止，得到一个新的有序序列 。

---

（2）直接插入排序（InsertSort）

当插入第 i (i >= 1) 个元素时，前面的 array[0]，array[1]，…，array[i-1] 已经排好序，此时用 array[i] 的排序码与 array[i-1]，array[i-2]，… 的排序码顺序进行比较，找到插入位置即将 array[i] 插入，原来位置上的元素顺序后移。

// 直接插入排序
void InsertSort(int* a, int n)
{
    assert(a);
 
	for (int i = 0; i < n - 1; ++i)
	{
		// [0,end]有序，把end+1位置的值插入，保持有序
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp < a[end])//升序
			{
				a[end + 1] = a[end];
				--end;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

---

a.插入排序是原地排序算法吗？

从实现过程可以很明显地看出，插入排序算法的运行并不需要额外的存储空间，所以 空间复 杂度是 O(1) ，也就是说，这是一个 原地排序算法 。

b.插入排序是稳定的排序算法吗？ 

在插入排序中，对于值相同的元素，我们可以选择将后面出现的元素，插入到前面出现元素

的后面，这样就可以保持原有的前后顺序不变，所以插入排序是 稳定 的排序算法。

c.插入排序的时间复杂度是多少？ 

如果要排序的数据已经是 有序 的，我们并不需要搬移任何数据。如果我们从尾到头在有序数据组里面查找插入位置，每次只需要比较一个数据就能确定插入的位置。所以这种情况下，最好是时间复杂度为 O(n) 。注意，这里是 从尾到头遍历已经有序的数据 。

如果数组是 倒序 的，每次插入都相当于在数组的第一个位置插入新的数据，所以需要移动大量的数据，所以最坏情况时间复杂度为 O(n²) 。

还记得在数组中插入一个数据的平均时间复杂度是多少吗？没错，是 O(n)。所以，对于插入排序来说，每次插入操作都相当于在数组中插入一个数据，循环执行 n 次插入操作，所以 平均时间复杂度为 O(n²) 。

---

（3）希尔排序（ShellSort）（缩小增量排序）

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

// 希尔排序
void ShellSort(int* a, int n)
{
    assert(a);
 
	int gap = n;
 
    //时间复杂度：O（n*log3n）
    // 时间复杂度：O(log3n)（以3为底的对数）
	while (gap > 1) // 不能写成gap>0,因为gap的值始终>=1
	{
		gap = gap / 3 + 1;
		//gap = gap / 2;
 
		for (int i = 0; i < n - gap; ++i) // 时间复杂度：O(n)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}

---

【关于 gap 的取值】

最初希尔提出的增量是 gap = n / 2，每一次排序完让增量减少一半 gap = gap / 2，直到 gap = 1 时排序相当于直接插入排序。直到后来 Knuth 提出的 gap = (gap / 3) + 1，每次排序让增量成为原来的三分之一，加一是防止 gap <= 3 时 gap = gap / 3 = 0 的发生，导致希尔增量最后不为1，无法完成插入排序。

选择 gap = (gap / 3) + 1 更稳定，能够尽可能地减少比较和交换的次数，以提高排序的效率。通过采用这种递减的方式，可以更好地分组元素，使得在每一轮排序中能够更快地将较小的元素移动到前面。序列被划分为较小的子序列，并通过插入排序的方式对每个子序列进行排序。这样做的好处是在初始阶段，较大的元素可以更快地向后移动，从而减少了后续比较和交换的次数。

希尔排序的特性总结：

1. 希尔排序是对直接插入排序的优化。
2. 当 gap > 1 时都是预排序，目的是让数组更接近于有序。当 gap == 1 时，数组已经接近有序的了，相当于直接插入，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
3. 希尔排序的时间复杂度并不好计算，因为 gap 的取值方法很多，导致很难去计算，因此在好些书中给出的希尔排序的时间复杂度都不固定，官方给出的时间复杂度是 O(N^1.3) 。
4. 稳定性：不稳定。

《数据结构 (C 语言版 ) 》 --- 严蔚敏

《数据结构-用面相对象方法与C++描述》--- 殷人昆

---

【总结】

希尔排序在越大的数组上相较于直接插入排序更能发挥优势，因为步子迈的更大，减少插入排序的移动次数更多。比如10w个数据，直接插入排序复杂度为O(N^2),计算10w *10w=100亿次，而希尔排序复杂度为O(NlogN),计算10w *17 = 170w次。（2 ^17 约等于10w）。

---

2、选择排序

（1）基本思想

选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序

每一次从待排序的数据元素中选出 最小(升序) / 最大(降序) 的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。

---

（2）直接选择排序（SelectSort）

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

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
 
void SelectSort(int* a, int n)
{
    assert(a);
 
	int begin = 0;
	while (begin < n)
	{
		int mini = begin;
		for (int i = begin; i < n; i++)
		{
			if (a[i] < a[mini])
			{
				mini = i;
			}
		}
		Swap(&a[begin], &a[mini]);
		begin++;
	}
}

// 优化后的代码：(一次选出两个数)
void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
 
// 直接选择排序
void SelectSort(int* a, int n)
{
	assert(a);
 
	int begin = 0, end = n - 1;
	while (begin < end) // 奇数个会相遇 偶数个会错过
	{
		int mini = begin, maxi = begin;
		for (int i = begin + 1; i <= end; ++i)
		{
			if (a[i] < a[mini])
			{
				mini = i;
			}
			if (a[i] > a[maxi])
			{
				maxi = i;
			}
		}
		Swap(&a[begin], &a[mini]);
 
		// 如果begin和maxi重叠，那么要修正maxi的位置
		if (begin == maxi)
		{
			maxi = mini;
		}
		Swap(&a[end], &a[maxi]);
		++begin;
		--end;
	}
}

a.选择排序是原地排序算法吗？

选择排序空间复杂度为 O(1) ，是一种原地排序算法。

b.选择排序是稳定的排序算法吗？ 

答案是否定的，选择排序是一种 不稳定 的排序算法。选择排序每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样破坏了稳定性。 比如 4，9，4，1，8 这样一组数据，使用选择排序算法来排序的话，第一次找到最小元素 1 ，与第一个 4 交换位置，那第一个 4 和中间的 4 顺序就变了，所以就不稳定了.

c.选择排序的时间复杂度是多少？ 

 选择排序的最好情况时间复杂度为 n+(n-2)+(n-4)+...（优化后的做法）相当于 n²，最坏情况和平均情况时间复杂度都为 O(n²)。

直接选择排序的特性总结：

1. 效率不是很好，实际中很少使用，不建议使用。
2. 时间复杂度：O(N²)。
3. 空间复杂度：O(1)。
4. 稳定性：不稳定。

---

（3）堆排序（HeapSort）

有关堆（Heap）的相关内容详解，具体请看：【数据结构】堆（Heap）_炫酷的伊莉娜的博客-CSDN博客 

堆排序 (Heapsort) 是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是 排升序要建大堆，排降序建小堆 。

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
 
void AdjustDown(int* a, int size, int parent)
{
	int child = parent * 2 + 1;
	while (child < size)
	{
		//选出左右孩子中大的那个
		if (child + 1 < size && a[child + 1] > a[child])
		{
			++child;
		}
 
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
 
// 堆排序
void HeapSort(int* a, int n)
{
    assert(a);
 
    // botto-top(自底向上)，依次遍历完所有子树，分别对其进行调整
	for (int i = ((n - 1) - 1) / 2; i >= 0; i--) // 从最后一个叶子节点的父亲的下标开始
	{
		AdjustDown(a, n, i);
	}
 
    // 升序
	int end = n - 1; // 记录堆中最后一个元素的下标
	while (end > 0)
	{
		Swap(&a[0], &a[end]); // 将堆顶元素和堆中最后一个元素交换，把最大的数(堆顶)放到最后
		AdjustDown(a, end, 0);
		--end;
	}
}

直接选择排序的特性总结：

1. 堆排序使用堆来选数，效率就高了许多。
2. 时间复杂度：O(N*logN)。
3. 空间复杂度：O(1)。
4. 稳定性：不稳定。

---

3、交换排序

（1）基本思想

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

---

（2）冒泡排序（Bubble Sort）

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。

// 冒泡排序
void BubbleSort(int* a, int n)
{
	assert(a);
 
	for (int j = 0; j < n - 1; ++j)
	{
		int exchange = 0; // 提前退出冒泡循环的标志
		for (int i = 1; i < n - j; ++i)
		{
			if (a[i - 1] > a[i])
			{
				Swap(&a[i - 1], &a[i]);
				exchange = 1; // 表示有数据交换
			}
		}
		if (exchange == 0) // 没有数据交换，提前退出
		{
			break;
		}
	}
}

a.冒泡排序是原地排序算法吗？

冒泡的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，所以它的空间复杂度为 O(1) ，是一个原地排序算法。

b.冒泡排序是稳定的排序算法吗？

在冒泡排序中，只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定 性，当有相邻的两个元素大小相等的时候，我们不做交换，相同大小的数据在排序前后不会改变顺序，所以冒泡排序是 稳定 的排序算法。

c.冒泡排序的时间复杂度是多少？

最好情况下，要排序的数据已经是有序的了，我们只需要进行一次冒泡操作，就可以结束 了，所以最好情况时间复杂度是 O(n) 。而最坏的情况是，要排序的数据刚好是倒序排列的，我们需要进行 n 次冒泡操作，所以最坏情况时间复杂度为 O(n²) 。

d.冒泡排序与插入排序相比哪个更好？

两种排序在最好、最坏情况下的时间复杂度相同。但在相对有序的情况下，选择插入排序更好。比如：1 2 3 5 4 6 这个排序，冒泡排序需要 ((N-1)+(N-2)) 比较，插入排序需要 N 次比较。因为冒泡排序排好后，还需要再排多一次。

冒泡排序的特性总结：

1. 冒泡排序是一种非常容易理解的排序。
2. 时间复杂度：O(N²)。
3. 空间复杂度：O(1)。
4. 稳定性：稳定。

---

（3）快速排序法（Quicksort）

快速排序算法（Quicksort），我们习惯性把它简称为“快排”。快排利用的是分治思想。快速排序是 Hoare 于 1962 年提出的一种二叉树结构的交换排序方法，其基本思想为： 任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止 。

快排的处理过程是由上到下 的，先分区，然后再处理子问题。

// 假设按照升序对array数组中[left, right)区间中的元素进行排序
void QuickSort(int array[], int left, int right)
{
    if(right - left <= 1)
    {
        return;
    }
 
    // 按照基准值对array数组的[left, right)区间中的元素进行划分
    int div = partion(array, left, right); // 分区函数
 
    // 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div+1, right)
    // 递归排[left, div)
    QuickSort(array, left, div);
 
    // 递归排[div+1, right)
    QuickSort(array, div+1, right);
}

上述为快速排序递归实现的主框架，发现与二叉树前序遍历规则非常像，同学们在写递归框架时可想想二叉树前序遍历规则即可快速写出来，后续只需分析如何按照基准值来对区间中数据进行划分的方式即可。

快排在有序的情况下时间复杂度最坏，n+(n-1)+(n-2)+... 为 O(n²) 。

a.hoare 版本

选出一个关键字 key，一般是头或者尾。经过一次单趟后，key 放到了正确的位置，key 左边的值比 key 小，key 右边的值比 key 大。再让 key 的左边区间有序、key 的右边区间有序。

如何保证相遇位置的值小于 key ？ 

这个算法右边先走可以保证相遇位置小于 key。

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
 
// Hoare
int PartSort1(int* a, int begin, int end)
{
	int left = begin, right = end;
	int keyi = left;
	while (left < right)
	{
		// 右边先走，找小 -- 升序
		while (left < right && a[right] >= a[keyi])
		{
			--right;
		}
	
		// 左边再走，找大
		while (left < right && a[left] <= a[keyi])
		{
			++left;
		}
 
		Swap(&a[left], &a[right]);
	}	
	Swap(&a[keyi], &a[left]);
	keyi = left;
 
	return keyi;
}

这里的 while 要加等号的原因是避免出现死循环的情况。

---

b.挖坑法

// 挖坑法
int PartSort2(int* a, int begin, int end)
{
	int key = a[begin];
	int piti = begin;
	while (begin < end)
	{
		// 右边找小，填到左边的坑里面去。这个位置形成新的坑
		while (begin < end && a[end] >= key)
		{
			--end;
		}
		a[piti] = a[end];
		piti = end;
 
		// 左边找大，填到右边的坑里面去。这个位置形成新的坑
		while (begin < end && a[begin] <= key)
		{
			++begin;
		}
		a[piti] = a[begin];
		piti = begin;
	}
	a[piti] = key;
	return piti;
}

注意：如果在 while 循环中去掉等号，即将 a[end] >= key 改为 a[end] > key，a[begin] < key 改为 a[begin] <= key，那么当数组中存在与 key 相等的元素时，会导致划分出的两部分不再严格符合小于等于 key 和大于等于 key 的条件，而是可能存在相等的元素分布在两部分中，从而导致排序结果不正确。

因此，在挖坑法中，保持 a[end] >= key 和 a[begin] <= key 的等号是非常重要的，以确保元素能够正确地被划分到两个部分中。

---

c.前后指针版本

// 前后指针法
int PartSort3(int* a, int begin, int end)
{
	int prev = begin;
	int cur = begin + 1;
	int keyi = begin;
 
	// 加入三数取中的优化
	//int midi = GetMidIndex(a, begin, end);
	//Swap(&a[keyi], &a[midi]);
 
	while (cur <= end)
	{
		// a[cur]比a[keyi]大时，prev不会++且排除了自己交换自己这种情况
		if (a[cur] < a[keyi] && ++prev != cur)
		{
			Swap(&a[prev], &a[cur]);
		}
		++cur;
	}
	Swap(&a[prev], &a[keyi]);
	keyi = prev;
 
	return keyi;
}

如果将 if 里面的条件改为 a[cur] <= a[keyi]，虽然不会导致排序结果出错，但是可能会改变相等元素的相对顺序，所以还是应该写成 a[cur] < a[keyi]，不要加上等号。

---

（4）快速排序优化 · 三数取中法

• 三数取中法依然无法完全解决针对某种特殊序列（比如元素全部相同）复杂度变为 O(n) 的情况。
• 三数取中法一般选取首、尾和正中三个数进行取中。

• 该方法的基本思想是从待排序数组中随机选择三个元素，并将它们按升序排列。然后，选择中间位置的元素作为 mid 。

这样处理的方式有几个优点，可以提高排序算法的效率：

1. 减少最坏情况：选择中间位置的元素，可以避免最坏情况的发生。最坏情况是在每次划分过程中总是选择了最大或最小的元素，导致划分不平衡，使得排序算法的时间复杂度变为 O(n²) 。而三数取中法可以减少最坏情况的发生，提高划分的平衡性。
2. 提高划分效率：选择适当的中间元素可以增加划分的平衡性，使得每次划分都能将数组分为近似相等大小的两个部分。这样，在后续的排序过程中，可以减少比较和交换的次数，提高排序算法的效率。
3. 三数取中法可以有效地应对一些特殊情况，如数组已经有序或部分有序的情况。在这些情况下，选择中间位置的元素可以避免不必要的划分和比较操作。

• 总的来说，三数取中法通过选择合适的中间元素，可以减少最坏情况的发生，提高划分的平衡性和效率，从而提高排序算法的整体效率。

// 三数取中法
int	GetMidIndex(int* a, int begin, int end)
{
	//int mid = (begin + end) / 2;
    int mid = left + (right - left) / 2; // 防止溢出版本
 
	if (a[begin] < a[mid])
	{
		if (a[mid] < a[end])
		{
			return mid;
		}
		else if (a[begin] < a[end])
		{
			return end;
		}
		else
		{
			return begin;
		}
	}
	else // (a[begin] >= a[mid])
	{
		if (a[mid] > a[end])
		{
			return mid;
		}
		else if (a[begin] < a[end])
		{
			return begin;
		}
		else
		{
			return end;
		}
	}
}

1. 三数取中法选 key。
2. 递归到小的子区间时，可以考虑使用插入排序。

优化后的代码：

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
 
// Hoare
int PartSort1(int* a, int begin, int end)
{
	int left = begin, right = end;
	int keyi = left;
 
    // 加入三数取中的优化
	int midi = GetMidIndex(a, begin, end);
	Swap(&a[keyi], &a[midi]);
 
	while (left < right)
	{
		// 右边先走，找小 -- 升序
		while (left < right && a[right] >= a[keyi])
		{
			--right;
		}
	
		// 左边再走，找大
		while (left < right && a[left] <= a[keyi])
		{
			++left;
		}
 
		Swap(&a[left], &a[right]);
	}	
	Swap(&a[keyi], &a[left]);
	keyi = left;
 
	return keyi;
}

// 挖坑法
int PartSort2(int* a, int begin, int end)
{
	int key = a[begin];
	int piti = begin;
 
    // 加入三数取中的优化
	int midi = GetMidIndex(a, begin, end);
	Swap(&a[keyi], &a[midi]);
 
	while (begin < end)
	{
		// 右边找小，填到左边的坑里面去。这个位置形成新的坑
		while (begin < end && a[end] >= key)
		{
			--end;
		}
		a[piti] = a[end]; // 填坑
		piti = end; // 新坑
 
		// 左边找大，填到右边的坑里面去。这个位置形成新的坑
		while (begin < end && a[begin] <= key)
		{
			++begin;
		}
		a[piti] = a[begin]; // 填坑
		piti = begin; // 新坑
	}
	a[piti] = key; // 将key填到最后一个坑里
	return piti;
}

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
 
// 前后指针法
int PartSort3(int* a, int begin, int end)
{
	int prev = begin;
	int cur = begin + 1;
	int keyi = begin;
 
	// 加入三数取中的优化
	//int midi = GetMidIndex(a, begin, end);
	//Swap(&a[keyi], &a[midi]);
 
	while (cur <= end)
	{
		// cur位置的值小于keyi位置的值
		if (a[cur] < a[keyi] && ++prev != cur)
		{
			Swap(&a[prev], &a[cur]);
		}
		++cur;
	}
	Swap(&a[prev], &a[keyi]);
	keyi = prev;
 
	return keyi;
}

快速排序是一种高效的排序算法，通常在处理大规模数据时表现良好。然而，当递归到较小区间时，快速排序可能会变得相对较慢。这是因为递归调用本身会带来一定的开销，而对于较小的区间，插入排序可能更加高效。 

插入排序是一种简单但有效的排序算法，对于小规模的数据集表现出色。它的时间复杂度为O(n²)，但在实际应用中，由于具有低的常数因子和良好的局部性，插入排序通常会比其他 O(n²) 复杂度的排序算法更快。

因此，当快速排序递归到较小区间时，我们可以切换到插入排序。这样可以减少递归调用的次数，降低开销，并且利用插入排序的优势来提高整体性能。

void InsertSort(int* a, int n)
{
	for (int i = 0; i < n - 1; ++i)
	{
		// [0,end]有序，把end+1位置的值插入，保持有序
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp < a[end]) // 升序
			{
				a[end + 1] = a[end];
				--end;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}
 
// 快速排序（递归）
void QuickSort(int* a, int begin, int end)
{
 
	// 区间不存在，或者只有一个值则不需要再处理
	if (begin >= end)
	{
		return;
	}
 
	if (end - begin > 10)
	{
		int keyi = PartSort3(a, begin, end);
 
		// [begin, keyi-1] keyi [keyi+1, end]
		QuickSort(a, begin, keyi - 1);
		QuickSort(a, keyi + 1, end);
	}
	else // 递归到小的子区间时，可以考虑使用插入排序
	{
		InsertSort(a + begin, end - begin + 1);
	}
}

---

（5）快速排序非递归

递归的大问题是在极端场景下，如果栈帧深度太深，栈空间不够用，会出现栈溢出。下面用非递归实现快速排序：

递归改成非递归一般有两种方法：

1. 直接改循环（简单）；
2. 借助数据结构栈模拟递归过程（复杂） 。

• 快速排序的非递归遍历可以使用栈模拟二叉树的前序遍历的方式实现，也可以使用队列模拟二叉树的层序遍历的方式实现。
• 快排的非递归是在模拟递归的过程，所以时间复杂度并没有本质的变化，但是没有递归，可以减少栈空间的开销。

// 快速排序非递归（栈）
void QuickSortNonR(int* a, int begin, int end)
{
	ST st;
	StackInit(&st);
	StackPush(&st, end);
	StackPush(&st, begin);
 
	while (!StackEmpty(&st)) // 栈不为空
	{
        // 取栈顶left，并Pop
		int left = StackTop(&st);
		StackPop(&st);
 
        // 再取栈顶right，并Pop
		int right = StackTop(&st);
		StackPop(&st);
 
		int keyi = PartSort3(a, left, right); // 这里用前后指针单趟排
		// [left, keyi-1] keyi [keyi+1, right]
 
		if (keyi + 1 < right) // 至少还有一个以上的值
		{
			StackPush(&st, right);
			StackPush(&st, keyi + 1);
		}
 
		if (left < keyi - 1) // 至少还有一个以上的值
		{
			StackPush(&st, keyi - 1); // 先入右，再入左 -- 先出左，再出右
			StackPush(&st, left);
		}
	}
	StackDestroy(&st);
}

需要入栈的是数组的下标区间，且先入右再入左，因为栈是先进后出，条件是栈不为空。

依次把需要进行单趟排的区间入栈，依次取栈里的区间出来单趟排，再把需要处理的子区间入栈。

快速排序的特性总结：（ 前序遍历 ）（ 层序遍历 ）

1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序。
2. 时间复杂度：O(N*logN)。
3. 空间复杂度：O(logN)。
4. 稳定性：不稳定。

---

4、归并排序

（1）基本思想

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。分治，顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决。小的子问题解决了，大问题也就解决了 。

分治思想跟我们前面讲的递归思想很像。是的，分治算法一般都是用递归来实现的。分治是一种解决问题的处理思想，递归是一种编程技巧 ，这两者并不冲突。

将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 

（2）归并排序（MergeSort）

归并排序的核心思想还是蛮简单的。如果要排序一个数组，我们先把数组从中间分成前后两

部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有

序了。

void _MergeSort(int* a, int begin, int end, int* tmp)
{
	if (begin >= end)
	{
		return;
	}
 
	//int mid = (begin + end) / 2;
    int mid = begin + (end - begin) / 2; // 防止溢出版本
 
	// [begin, mid] [mid+1, end] 分治递归，让子区间有序
	_MergeSort(a, begin, mid, tmp);
	_MergeSort(a, mid + 1, end, tmp);
 
	// 归并[begin, mid] [mid+1, end]
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int i = begin1;
	while (begin1 <= end1 && begin2 <= end2) // 其中一个结束就结束
	{
		if (a[begin1] <= a[begin2]) // 等于可以保证稳定性
		{
			tmp[i++] = a[begin1++];
		}
		else
		{
			tmp[i++] = a[begin2++];
		}
	}
 
    // 将剩余的数字直接填入tmp数组里
	while (begin1 <= end1) // begin2结束了，拷贝剩下的begin1
	{
		tmp[i++] = a[begin1++];
	}
 
	while (begin2 <= end2) //begin1结束了，拷贝剩下的begin2
	{
		tmp[i++] = a[begin2++];
	}
 
    // 归并后的结果，拷贝到原数组
	memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
 
    //for(int i = begin; i <= end; ++i)
    //{
    //    a[i] = tmp[i];
    //}
}
 
// 归并排序
void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n); // 临时数组
	if (tmp == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	_MergeSort(a, 0, n - 1, tmp); // 子函数递归
 
	free(tmp);
}

a.归并排序是稳定的排序算法吗？

在合并的过程中，如果 a[p…q] 和 a[q+1…r] 之间有值相同的元素，先把 a[p…q] 中的元素放入 tmp 数组，这样就保证了值相同的元素，在合并前后的先后顺序不变。所以，归并排序是一个稳定的排序算法。

b.归并排序的时间复杂度是多少？  

归并排序的执行效率与要排序的原始数组的有序程度无关，所以其时间复杂度是非常稳定的，不管是最好情况、最坏情况，还是平均情况，时间复杂度都是 O(n*logn) 。

c.归并排序的空间复杂度是多少？

归并排序不是原地排序算法。这是因为归并排序的合并函数，在合并两个有序数组为一个有序数组时，需要借助额外的存储空间。

如果我们继续按照分析递归时间复杂度的方法，通过递推公式来求解，那整个归并过程需要 的空间复杂度就是 O(n*logn)。不过，类似分析时间复杂度那样来分析空间复杂度，这个思 路并不对。 实际上，递归代码的空间复杂度并不能像时间复杂度那样累加。刚刚我们忘记了最重要的一 点，那就是，尽管每次合并操作都需要申请额外的内存空间，但在合并完成之后，临时开辟 的内存空间就被释放掉了。在任意时刻， CPU 只会有一个函数在执行，也就只会有一个临 时的内存空间在使用。临时内存空间最大也不会超过 n 个数据的大小，所以空间复杂度是  O(n) 。

归并排序的特性总结：（ 后序遍历 ）

1. 归并的缺点在于需要 O(N) 的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
2. 时间复杂度：O(N*logN)。
3. 空间复杂度：O(N)。
4. 稳定性：稳定。

---

（3）归并排序非递归

非递归未必比递归简单，因为这里需要对边界进行精准控制。

// 归并排序（非递归）
void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
 
	int gap = 1;
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2 * gap)
		{
			// [i, i+gap-1][i+gap, i+2*gap-1]
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
 
			// end1越界或者begin2越界，则可以不归并
			if (end1 >= n || begin2 >= n)
			{
				break;
			}
			else if (end2 >= n) // 修正边界
			{
				end2 = n - 1;
			}
 
			int m = end2 - begin1 + 1; //实际归并的总体个数
			int j = begin1;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					tmp[j++] = a[begin1++];
				}
				else
				{
					tmp[j++] = a[begin2++];
				}
			}
 
			while (begin1 <= end1) // begin2结束了，拷贝剩下的begin1
			{
				tmp[j++] = a[begin1++];
			}
 
			while (begin2 <= end2) // begin1结束了，拷贝剩下的begin2
			{
				tmp[j++] = a[begin2++];
			}
			memcpy(a + i, tmp + i, sizeof(int) * m); // 拷贝回原数组
		}
		gap *= 2; // 迭代
	}
	free(tmp);
}

---

⚪非比较排序

（1）思想

• 计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。

---

（2）计数排序（CountSort）

// 计数排序
void CountSort(int* a, int n)
{
	int min = a[0], max = a[0];
    // 找出最大最小值
	for (int i = 1; i < n; ++i)
	{
		if (a[i] < min)
		{
			min = a[i];
		}
		
		if (a[i] > max)
		{
			max = a[i];
		}
	}
 
	// 统计次数的数组
	int range = max - min + 1;
	int* count = (int*)malloc(sizeof(int) * range);
	if (count == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	memset(count, 0, sizeof(int) * range); // 初始化为0
 
	//统计次数
	for (int i = 0; i < n; ++i)
	{
		count[a[i] - min]++;
	}
 
	//回写-排序
	int j = 0;
	for (int i = 0; i < range; ++i)
	{
		// 出现几次就要回写几个i+min
		while (count[i]--)
		{
			a[j++] = i + min;
		}
	}
    free(count);
}

• 如果要开 0~5000 个数据的数组，但其实小于 1000 的数据一个都没有，空间浪费严重，这种方式叫作绝对映射。
• 针对此情况，如果我们只需要 0~4000 个数据的数组即可，放数据时是 a[i] - min，这种方式叫作相对映射。  

注意 ：计数排序只能用在数据范围不大的场景中，如果数据范围 k 比要排序的数据 n 大很多，就不适合用计数排序了。而且，计数排序只能给非负整数排序，如果要排序的数 据是其他类型的，要将其在不改变相对大小的情况下，转化为非负整数。

计数排序的特性总结：

1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
2. 时间复杂度：O(MAX(N，range))。
3. 空间复杂度：O(range)。
4. 稳定性：稳定。

---

三、排序算法复杂度及稳定性分析