排序算法讲解

1）排序思想：

2）排序代码：

3）注意点：

4）时间/空间复杂度和稳定性

下面的排序是以实现升序讲解的。

（一）直接插入排序

1）排序思想：

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列

2）排序代码：

void InsertSort(int* a, int n)
{
    for(int i = 0;i < n - 1;i++)
    {
        // 第一趟排序
        int end = i;
        int temp = a[end + 1];
        while(end >= 0 && temp < a[end])
        {
            // 向后移动数据，直到找到合适的位置
            a[end + 1] = a[end];
            end--;
        }
        // 找到合适的位置，进行插入
        a[end + 1] = temp;
    } 

}

3）注意点：

????????a) 总趟排序的end小标的范围是[0, n-1]，而不是[0, n], 因为如果是[0, n], temp = a[end+1]会造成越界访问;

????????b) 在内部while循环的循环条件要保证end不能小于0，因为当end减到-1时，在进行a[end]会造成越界访问。

4）时间/空间复杂度和稳定性

直接插入排序的时间复杂度：当要排序的数据是逆序时，时间复杂度为O(N^2); 当要排序数据是顺序的时，时间复杂度为O(N)。

空间复杂度：O(1).

稳定性：

算法的稳定性指的是在排序算法中，具有相同键值的元素在排序前后的相对位置是否保持不变。

在某些排序场景中，可能存在相同键值的元素，比如多个学生按照成绩进行排序。如果排序算法是稳定的，那么具有相同成绩的学生，就要以交卷时间进行排名（花费时间少的排名高）在排序后仍然保持原来的顺序，并且排序后的结果是稳定的。

插入排序算法的基本思想是将待排序的元素逐个插入已排序部分的合适位置。在插入过程中，如果存在相同键值的元素，就会将新元素插入到已存在的元素之后，从而保持相同键值元素的相对顺序不变。

所以插入排序算法是稳定的。

与冒泡排序的横向比较：

冒泡排序是严格的n-1+(n-2)+(n-3)+(n-4)+……+2+1，无论数据是什么样子的。

而对于插入排序来说，只有当数据是完全逆序是（从前向后插入）才是这么多次的比较次数：1+2+……+(n-2)+(n-1)，如果插入数据时，其前面已经是有序的或者有几个不是有序的，那么这个数据就不需要进行完全的比较就可以确定其位置。例如：1 2 3 4 ，中插入一个5，就可以直接将5插入到该序列的后面就能保证数据是有序的；或者是：1 2 4 5中插入一个3，只需要比较依次比较5 和 4两次后就能确定3的位置，保证数据是有序的。

而如果对于 1 2 4 5 3，使用冒泡排序的话，就需要1 2和2 4 和4 5和5 3、1 2和2 4和4 3和4 5

这么多次比较才能将插入的3放到相应的位置。

（二）希尔排序

1）排序思想：

先选定一个整数作为分割距离，把待排序文件中所有记录分成几个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后取重复上述分组和排序的工作。当距离到达1时，所有记录在统一组内排好序。

2）排序代码：

void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap /= 2;
		for (int i = 0; i < n - gap; i++) // i<n,在第一趟时end=i=n-1，此时temp会越界
		{
			int end = i;
			int temp = a[end + gap];
			if (temp < a[end])
			{
				while (end >= 0 && a[end] > temp) 
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				a[end + gap] = temp;
			}
		}
	}
}

3）注意点：

1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快，最后一次排序的时间复杂度为O(N)。这样整体而言，可以达到优化的效果。
?

这里的注意点和直接插入排序算法要注意的是一样的。直接插入排序的实现就相当于希尔排序算法的gap间距为1.

4）时间/空间复杂度和稳定性

时间复杂度：

空间复杂度：O(1)

稳定性：

在希尔排序的过程中，相同键值的元素可能会因为间隔的不同而被分散到不同的分组中。当进行插入排序时，不同分组内的元素会交替进行比较和移动，这可能导致相同键值的元素之间的相对顺序发生变化。

因此，由于希尔排序采用间隔分组的方式，相同键值元素可能跨越不同的分组，排序后的结果可能会改变相同键值元素的相对位置，所以希尔排序是不稳定的。

这个分析方法是按照，每次排序后数据还是逆序的进行分析。实际上效率会比下面的分析得到的结果高。

（三）选择排序

A. 直接选择排序

1）排序思想：

它的基本思想是：每次从待排序序列中选择最小的元素，将其放到序列的开头；从排序序列中选择最大的元素，将其放到序列的结尾。

2）排序代码：

void SelectSort(int* a, int n)
{
	int begin = 0, end = n - 1;
	while (begin < end)
	{
		int maxi = begin, mini = begin;
		// 找到最大值和最小值的下标
		for (int i = begin + 1; i <= end; i++)
		{
			if (a[i] > a[maxi])
			{
				maxi = i;
			}

			if (a[i] < a[mini])
			{
				mini = i;
			}
		}
		// 交换
		Swap(&a[maxi], &a[end]);
		// 如果最小值在序列结尾，将最大值与最小值交换后，最小值已经不在序列结尾处了
		// 所以要记录下最小值的位置
		if (mini == end)
		{
			mini = maxi;
		}
		Swap(&a[mini], &a[begin]);

		begin++;
		end--;
	}
}

3）注意点：

一要注意更新每一次最大值和最小值，以便能够找到正确的最大值和最小值；

二要注意最大值放到序列最后时，可能会导致最小值的下标指向的不再是最小值。

4）时间/空间复杂度和稳定性

时间复杂度：选择排序的外层循环执行了 n-1 次，内层循环在最坏情况下需要执行 (n-1) + (n-2) + ... + 1 = n(n-1)/2 次比较操作。同时，每次外层循环还需要进行两次元素交换操作。 因此，整个选择排序的时间复杂度为 O(n^2)。

空间复杂度：选择排序只需要使用常数级别的额外空间用于存储临时变量，因此空间复杂度为 O(1)。

稳定性：

稳定性分析： 如果序列中存在相同键值的元素，并且该值是最大值（在从前向后寻找最大值时，会选择前面一个值作为最大值并交换到本次序列的最后；在第二次寻找最大值时，会选择这个相等的值，并放到本次序列的最后，但是本次序列的最后是上一次序列最后的前一个），在排序完成后它们的相对位置发生变化，导致算法不稳定。所以直接选择排序是不稳定的。

选择排序是一种简单的排序算法，它的基本思想是每次从未排序部分选择最小（或最大）的元素，放到已排序部分的末尾。在对长度为n的数组进行选择排序时，需要进行n-1轮比较和交换。

在第一轮比较中，需要将第一个元素与后面n-1个元素进行比较，共需要n-1次比较。 在第二轮比较中，需要将第二个元素与后面n-2个元素进行比较，共需要n-2次比较。 以此类推，最后一轮比较只需要将倒数第二个元素与最后一个元素进行比较，共需要1次比较。

因此，总的比较次数可以计算为：(n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2。

对于长度为100的数组进行选择排序，比较的次数为100(100-1)/2 = 4950次。

B. 堆排序

1）排序思想：

用向下调整法建一个大堆，将根节点和最后一个节点进行交换，然后再对根节点进行向下调整使新的根节点到达合适的位置。每完成一次排序，堆的节点个数减一，以此类推，直到堆的节点个数为1的时候，完成排序。

2）排序代码：

// 向下调整法
void AdjustDwon(int* a, int n, int root)
{
	int child = root * 2 + 1;
	while (child < n)
	{
		// 找到较大的孩子节点
		if (child + 1 < n && a[child] < a[child + 1])
		{
			child++;
		}
		if (a[root] < a[child])
		{
			// 交换
			Swap(&a[root], &a[child]);
			root = child;
			child = root * 2 + 1;
		}
		else
		{
			break;
		}
	} 	
}

void HeapSort(int* a, int n)
{
	// 利用大堆实现升序

	// 使用向下调整法将数组调整成为大堆
	int end = n - 1; // 最后一个叶子节点的下标
	for (int i = (end - 1) / 2; i >= 0; i--)
	{
		AdjustDwon(a, n, i);
	}

	// 排序
	// 根节点与最后一个节点交换，根节点向下调整，堆的数据量减一；直到堆的数据量为0时结束排序
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDwon(a, end, 0);
		end--;
	}
}

3）注意点：

注意向下调整的实现方法。

4）时间/空间复杂度和稳定性

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

空间复杂度：O(1)

稳定性：

使用向下调整时，如果一个节点的两个孩纸节点的值相同的并且为最大值，我们默认实现的是左孩子结点与其父节点进行交换，最终这个左孩子结点会被交换到根节点的位置，然后进行根节点和最后一个叶子节点进行交换，堆的节点数减一；第二次进行向下调整时，右孩子节点为最大值会被移动到根节点，然后再与本次最后一个叶子节点进行交换，但此时最后一个叶子节点是上一次排序的最后一个叶子节点的前一个。起初，这两个节点的顺序是AB == 最大值，但排序过后的顺序变成BA == 最大值。

所以，堆排序是不稳定的。

（四）交换排序

A. 冒泡排序法

1）排序思想：

它的基本思想是：比较相邻的元素，如果前面的元素大于后面的元素，则将它们互换位置。重复进行这个过程，直到不能再交换为止。

具体来说，冒泡排序的过程如下：

1. 依次比较相邻的元素，如果前面的元素大于后面的元素，则将它们互换位置。

2. 对所有相邻的元素进行一次遍历后，最后一个元素一定是当前未排序部分中最大的元素。

3. 对剩余的元素继续进行第1、2步操作，直到整个序列有序为止。

2）排序代码：

void Swap(int* x, int* y)
{
    int temp = *x;
    *x = *y;
    *y = temp;
}

void BubbleSort(int* a, int n)
{
	// 整趟排序逻辑
	for (int i = 0; i < n - 1; i++)
	{
		// 一趟排序
		int Isexchange = 0;
		for (int j = 1; j < n - i;j++)
		{
			if (a[j - 1] > a[j])
			{
				Swap(&a[j - 1], &a[j]);
				Isexchange = 1;
			}
		}
		if (Isexchange == 0) // 如果没有发生交换，则说明数组已经是有序的了，此时不需要再进行下去了
		{
			break;
		}
	}
}

3）注意点：

内部循环的范围：第一次范围是[1, n-1]；此时最后一个数已经到最后要到的位置，第二次排序不需要再对最后一个数进行排序，所以第二次范围是[1, n-1-1]……

4）时间/空间复杂度和稳定性

时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：相同键值的元素不会发生交换，所以在排序前后两者相对位置不会发生变化，所以冒泡排序算法是稳定的。

B. 快速排序

1）排序思想：

任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

一趟排序逻辑：key左边的值小于key，key右边的值大于key-->最终左右序列中间中间部分就是key值排序完成的位置。就相当于一次单趟排序将基准值移动到其最终的位置。

当右边指针先移动时， 左右指针在找大和找小过程中最终相遇位置一定是比key值小的：

如果右指针先走，最终相遇前有两种情况：

a)? R动L不动，R与L相遇在L的位置上；

b）L动R不动，L与R相遇在R的位置上。

a）R先走，左边没有比key值小的，就一直向左移动，直到与L指针相遇，而由于上一轮L和R交换后（R值是小于key值的），L指针指向的值就是小于key值的

b) R先走找到小于key的值后停下来，接着L向后走直到找到大于key的值或与R相遇，而R最后停下的地方就是小于key值的。

这里补充一下：如果是实现降序，那就是左边找小，右边找大。

先让左边先走还是先让右边先走却决于key值的位置：如果key值在左边，那就让右边先后；如果key值在右边，那就让左边先走。

总之就是让key对面的指针先走才能保证两指针相遇的位置是小于key值的。

2）排序代码：

// 单趟排序
int PartSort1(int* a, int left, int right)
{
	int keyi = left;
	while (left < right)
	{
		// 左边找大
		while (left < right && a[left] <= a[keyi])
		{
			++left;
		}
		// 右边找小
		while (left< right && a[right] >= a[keyi])
		{
			right--;
		}
	}
	Swap(&a[keyi], &a[left]);
	return left;
}


void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;
	int keyi = PartSort1(a, begin, end);
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

3）注意点：

hoare单趟排序：

a) 要求右指针先进行找小，在进行左指针找大（保证两者相遇位置的值小于key值）

b) 如果条件只是 大于或小于 key值，找小和找大过程中可能会死循环：当找大/找小过程中有值等于key值会跳出找大和找小循环，然后进行交换，再回到外层循环判断条件（begin<end）循环继续进入内部，由于当前值等于key值所以不会进入内部循环，会再次进行交换、外部条件判断……最后死循环；

c) 也可能会找不到小于key值和大于key值，导致越界

d) 递归结束条件：最后的情况是有一组两个数的数组：一个是key，另一个要么在key的左边（左边进行递归的参数为（begin，key-1），begin等于key-1；右边进行递归的参数为（key+1，key）该范围不存在）；要么在key的右边，那么其左边的范围不存在，右边范围两端点相等。

4）时间/空间复杂度和稳定性

时间复杂度：O(N^logN)

空间复杂度：O(1)

稳定性：如果待排序序列中存在相同关键字的元素，而它们在划分过程中被放置到不同的子序列中，那么它们的相对顺序就会改变，导致不稳定性。所以快速排序是不稳定的

5）对hoare快速排序的优化

在数据理想的情况下，如果每次选取的key值最终位置都在序列的中间那么时间复杂度为O(N^logN);

但如果数据接近有序的情况下，需要进行N次排序才能保证排序完成，最终时间复杂度为O(N^2);?

a) 优化方案一：三数取中

避免上图的第二种情况：key值在最左边，尽量保证key值最终在两序列的中间，

如何实现呢？ 我们发现当key值的大小接近最大值和最小值的中间值时，那么最终数据被分为左右序列时，左右序列的数据个数会比较平均，这样最后交换后key值最终就尽可能处于中间位置了。

而出现第二种情况的原因是数据基本已经接近有序了，这也就意味着序列中间位置的值接近中间值，所以可以选择中间位置的值作为key值。

但是如果选择中间位置的值作为key值后，在进行单趟排序时还要确定左右指针先走还是后走问题，为了不改变单趟排序的逻辑，我们可以将中间位置的值与最左边的值交换。

但是又不能对于所有将要排序的序列都交换中间值，要记住交换仅仅是为了应对数据接近有序这种极端情况。

所以，我们可以选择三个数中的中间值下标与左边交换，这样既能够应对极端情况，还能不影响普通情况。

int Getmidi(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] < a[right])
		{
			return right;
		}
		else
			return left;
	}
	else  //a[mid] < a[left]
	{
		if (a[right] < a[mid])
		{
			return mid;
		}
		else if (a[left] < a[right])
		{
			return right;
		}
		else
			return left;
	}
}

	int midi = Getmidi(a, left, right);
	Swap(&a[left], &a[midi]);

注意：

三数取中法的快速排序并不总是在任何情况下都是速度最快的排序方式。

快速排序的时间复杂度是平均情况下最好的，但在某些特殊情况下，例如已经有序或者逆序的序列，快速排序的性能会下降。三数取中法是一种优化手段，用于尽量避免这种情况。

三数取中法选择首、尾和正中三个数进行取中，选取它们的中间值作为基准值。这样可以有效避免快排单链的情况，尤其对已经有序的序列的速度改善明显。

但是仍然存在一些特殊序列，比如大量重复元素的序列，三数取中法也无法完全解决 每次划分操作的时间复杂度是O(n) 的情况，并且需要执行n次划分操作。这样，总的时间复杂度将是O(n * n)，即O(n^2)。

b）挖空法

由于hoare这种方法需要考虑左右指针先走问题，我们可以对这个进行改进：

当我们选取key值后，就在key值位置形成一个坑，这样就自然而然地让右面先走找到一个值填到这个坑中，右边的值填过去后，右边就会形成一个新的坑，接着让左边找值填坑。

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

所以挖坑法并不是对快速排序进行优化，而是让我们实现快速排序时逻辑更简单。

c）前后指针法

使用前后指针法会更容易实现快速排序。

主要思想是（实现升序）：让cur找小于key的值，++prev，交换prev和cur的值。

在移动过程中prev和cur的位置会有两种情况：

1. prev相邻，当cur找到小于key的值时，++prev后交换，相当于自己跟自己交换；

2. 当cur遇到大于key值时，cur和prev会拉开距离，当cur再次找到小于key值时，两指针中间的数值都是大于key值的，++prev，prev指向大于key的值，交换后，大于key的值被放到后面，小于key的值被放到前面。（本质类似于推箱子，将大于key的区间推到后面，小于key的区间推到前面）

3. 当cur移动到数组之外时，prev指向小于key的值

int PartSort3(int* a, int left, int right)
{
	int midi = Getmidi(a, left, right);
	Swap(&a[left], &a[midi]);

	int keyi = left;
	int pre = left;
	int cur = pre + 1;

	while (cur <= right)
	{
		if (a[cur] < a[keyi] && ++pre != cur) //尽量用这种方式
		{
			Swap(&a[cur], &a[pre]);
		}
		cur++;
	}
	Swap(&a[keyi], &a[pre]);
	return pre;
}

d) 递归深度的优化

由二叉树的知识可以知道：最后几层的节点个数占据整个树节点的大多数，所以对于后面几层的节点在使用快速排序（递归），消耗会比较大，我们可以使用插入排序进行排序，减少递归的消耗。

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end) 
		return;
	if ((begin - end + 1) > 10)
	{
		int key = PartSort3(a, begin, end);//第一趟排序
		QuickSort(a, begin, key - 1);//左边递归，排序
		QuickSort(a, key + 1, end);//右边递归，排序
	}
	else
	{
		InsertSort(a + begin, end - begin + 1);
	}
}

6）非递归实现快速排序

在使用递归算法时也存在一些消耗，包括：

1.内存消耗：递归算法需要使用系统栈空间来保存函数的执行现场和局部变量等信息，当递归深度较大时，占用的栈空间也会随之增加。如果递归深度过大，可能会导致栈溢出的异常，从而使程序崩溃。

2.时间消耗：递归算法一般需要进行多次函数调用，而函数调用的过程涉及到参数传递、现场保存和恢复等操作，这些操作都会耗费一定的时间。此外，在某些情况下，递归算法还可能存在重复计算的问题，造成额外的时间消耗。

3.维护复杂度：递归算法通常需要维护递归深度、参数传递等复杂度，增加了程序的复杂度和维护难度。

为了消除递归的消耗，我们可以用其他方法来模拟递归过程。

模拟实现递归的方法基本上有两种：一是用栈模拟；而是用循环模拟。

快排的思想是：第一次将key值移动到正确位置，并以key值位置将序列分割为两个序列，然后再对这两个序列进行key值的移动---这个过程类似于二叉树的前序遍历，可以用栈进行模拟实现。

入栈要保存的数据是要进行单趟排序的范围。

具体过程如下：

1. 先将数据的起始位置压入栈中，然后出栈得到第一次要进行排序的范围，进行第一次单趟排序；
2. 第一次排序结束后，key位置将序列分为两个部分：[left, key-1] 和 [key+1, right]；判断这两个范围是否合法：合法将这两个范围压入栈中；不合法（范围不存在 或左右端点相等）就不需要再排序了；
3. 之后出栈得到第二次排序的范围，进行第二次单趟排序的范围；
4. 重复上述过程，直到栈为空时，排序完成

void QuickSortNonR(int* a, int left, int right)
{
	// 创建栈
	Stack stack;
	StackInit(&stack);
	StackPush(&stack, right);
	StackPush(&stack, left);

	while (!StackEmpty(&stack))
	{
		int begin = StackTop(&stack);
		StackPop(&stack);

		int end = StackTop(&stack);
		StackPop(&stack);

		// 单趟排序
		int keyi = PartSort1(a, begin, end);
		// 右数组入栈
		if (keyi + 1 < end)
		{
			StackPush(&stack, end);
			StackPush(&stack, keyi + 1);
		}
		
		// 左数组入栈
		if (begin < keyi - 1)
		{
			StackPush(&stack, keyi - 1);
			StackPush(&stack, begin);
		}
		
	}

	StackDestroy(&stack);
}