[数据结构与算法]【C语言】-- 数据结构 -- 排序(超详解+动图+源码)

常见排序：

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

目录

一 、插入排序类：

1、?直接插入排序：

1. 1 直接插入排序的特性：

1.1.1 时间复杂度:

1.1.2?空间复杂度：

1.1.3 稳定性：

? 2、 希尔排序：

2.1?希尔排序的特性总结：

2.1.1 空间复杂度：

2.1.2 稳定性：

二、交换排序类

? 1、冒泡排序

1.1?冒泡排序的特性总结：

1.1.1 时间复杂度：

1.1.2 空间复杂度：?

2.1.2 稳定性：

??2、快速排序：

? 1.??hoare版本：

hoare版本易错点：

? ? ????????1.对于比较时：

? ? ? ? ? ? 2. 选择将key选择在左边后，选择右边先走的意义：

? 2.??挖坑版本：

挖坑版本易错点

? 3.?前后指针版本：

2.1. 快速排序的特性总结：

2.1.1 时间复杂度：

2.1.2 空间复杂度：

2.1.3 稳定性：

2.2?快速排序的优化：

2.2.1?时间复杂度的优化：

2.2.2?空间复杂度的优化：

三 、选择排序类：?

? 1、?直接选择排序：

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

1.1.1 时间复杂度:

1.1.2?空间复杂度:

1.1.3 稳定性：?

??2、 堆排序：

1.?堆排序的要点分两步：

1.1?建立大小堆：

1.2 利用大小堆排序：

2.1?堆排序的特性总结：

2.1.1?时间复杂度:

2.1.2?空间复杂度:

2.1.3?稳定性:

四 、归并排序类：

? 1、归并排序：

1.1 书写方式

1.1 递归方式：

1.2 非递归方式：

2. 归并排序的特性总结：

2.1?时间复杂度：

2.2?空间复杂度：

2.3?稳定性：

五 、非比较排序类：

? 1、?计数排序：

1. 计数排序的局限性：

1.1 如果是浮点数或者字符串就不能排序了

1.2?如果数据范围很大，空间复杂度就会很高，相对不适合

2. 计数排序的特性总结：

2.1 时间复杂度：

2.1 空间复杂度：

2.1 稳定性：

一 、插入排序类：

? ? ? ? 就如，玩扑克牌时，通过抽出扑克牌然后移动再插入的操作。是从排序2张，3张，4张……一样。

1、?直接插入排序：

//直接插入排序
void InsertSort(int* a, int n)
{
	assert(a);
    
    //i循环：对每个数据排序
	for (int i = 0; i < n - 1; ++i) //（将需要调整的数据定义为 i + 1, 而第一个元素由于为单，所以不需要排序，所以i[0, n-1]）
	{
		int end = i;
        //tmp：所需要调整的数据
		int tmp = a[end + 1];
		while (end >= 0)
		{
            //<是升序，>是降序
			if (tmp < a[end])
			{
				//如果符合条件，就向后移动数据
				a[end + 1] = a[end];
				--end;
			}
			else
			{
				break;
			}
		}
		//当出循环就找到，其所应该存在的位置，即放入数据
		a[end + 1] = tmp;
	}
}

//希尔排序
/* 调整，下标 0～n 的数据，当调整下标为 X 的数据时，0～X-1 的数据已经排序完成 */
/* 平移数据: 当大于（小于），则将元素向后调整。*/
void ShellSort(int* a, int n)
{
	assert(a);

	int gap = n;
	while (gap > 1)
	{
		// +1防止gap无法到1，当之前gap = 2时，变为3 / 2 = 0,(即由2步变为了0)
		gap = gap / 3 + 1;
		/*gap = gap / 2*/

		//j:代表与i同一组（根据gap划分）的数组元素下标
		//i:代表即将调整的元素下标，作为每一组比较数据的最后一个元素下标 

		for (int j = 0; j < gap; j++)
		{
			for (int i = j; i < n - gap; i += gap)
			{
				int end = i;

				//tmp:调整的数据
				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;
			}
		}
	}
}

//希尔排序
void ShellSort(int* a, int n)
{
	assert(a);

	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		/*gap = gap / 2*/

		for (int i = 0; i < n - gap; ++i)
		{
			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;
		}
	}
}

2.1?希尔排序的特性总结：

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

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

• 稳定性：不稳定
• 空间复杂度：O(1)

2.1.1 空间复杂度：

? ? ? ? ? ?即：空间复杂度为O(1)

2.1.2 稳定性：

?二、交换排序类

? 1、冒泡排序

? ? ? ? 冒泡排序的基本思想：比较相邻的元素。如若后者大（小），就交换二者。对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。即最后一个元素是排序区间的最大值。（依次往复直至完成）

//数据交换
void Swap(int* e1, int* e2)
{
	int tmp = *e1;
	*e1 = *e2;
	*e2 = tmp;
}

//冒泡排序
void BubbleSort(int* a, int n)
{
	assert(a);

	//用于判断是否交换
	int compare = 0;	
	
	//j循环: 序列到数第j个位置，是所需要用元素填补的位置，由于第一个元素最后为单，所以j < n
	//i循环：将其余未排序的数据(范围[0 , n - j])进行比较排序
	int j = 0;
	for (j = 1; j < n; j++)
	{
		int i = 0;
		for (i = 0; i < n - j; i++)
		{
            //>是升序，<是降序
			if (a[i] > a[i + 1])
			{
				compare = 1;
				Swap(&a[i], &a[i + 1]);
			}

		}

		if (compare == 0)	//排序是进行在未排序区的，如果一次交换都没有进行，那就证明未排序区是有序的
		{
			return;
		}
	}
}

1.1?冒泡排序的特性总结：

• 冒泡排序是一种非常容易理解的排序
• 时间复杂度：O(N^2)（最好为O(N) ~ 最差为O(N^2)）
• 空间复杂度：O(1)
• 稳定性：稳定

1.1.1 时间复杂度：

????????????????最好O(N)的情况：

? ? ? ? ? ? ? ? ? ? ? ??（有序即为最好）只有待排序值的前值皆与其有序，全程不需要交换，那么就可以直接退出，所以只需要比较一轮，即只需要判断，即O(N)。

?

????????????????最差O(N^2)的情况：

? ? ? ? ? ? ? ? ? ? ? ??（反序即为最差）每轮比较都需要移动，那这样就是一个等差数列：N-1 +? … + 3 + 2 + 1，则是：n (n-1+1)/2 则~O(n^2)?。即需要每个元素的一次判断，并移动的次数为最大，即O(N^2)。?

1.1.2 空间复杂度：?

?? ? ? ? ? ?即：空间复杂度为O(1)

2.1.2 稳定性：

??2、快速排序：

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

所运用的主要操作（为快速排序递归实现的主框架）：

而对于，将区间按照基准值划分为左右两半部分的常见方式有：

1. hoare版本
2. 挖坑版本
3. 前后指针版本

• 三个的执行方式不同，但是核心思想是不变的，版本的更改只是为了更加便于理解。

? 1.??hoare版本：

//数据交换
void Swap(int* e1, int* e2)
{
	int tmp = *e1;
	*e1 = *e2;
	*e2 = tmp;
}

//hoare版本（分治法）
//将right边的数据调整至皆小于或大于所调整的数据，left边同理反之。即有序
void QuickSort1(int* a, int begin, int end)
{
	assert(a);

	if (begin >= end)
		return;

	//keyi:所需要调整的数据下标
	int right, left, keyi;
	left = begin, right = end;
	keyi = begin;

	//根据大小将左右元素交换
	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;

	//分治管理其左与右
	//[begin, keyi - 1] keyi [keyi + 1, end]
	QuickSort1(a, begin, keyi - 1);
	QuickSort1(a, keyi + 1, end);
}

hoare版本易错点：

????????（同样的后面的挖坑版，也具同样的问题 ）

? ? ????????1.对于比较时：

??????????????假如，没有等于：

? ? ? ? ? ? 2. 选择将key选择在左边后，选择右边先走的意义：

????????原因：因为要确保相遇位置的值，比key小或者就是key的位置。

????????会出现两种情况：

? ? ? ? ? ? ? ? 1.?L先走，L停下来，R去遇到L。

? ? ? ? ? ? ? ??2.?L先走，直接与R相遇

? 2.??挖坑版本：

//数据交换
void Swap(int* e1, int* e2)
{
	int tmp = *e1;
	*e1 = *e2;
	*e2 = tmp;
}

//挖坑版本
//将right边的数据调整至皆小于或大于所调整的数据，left边同理反之。即有序
void QuickSort2(int* a, int begin, int end)
{
	assert(a);

	if (begin >= end)
		return;

	//keyi：坑的下标
	//key: 所需要调整的数据
	int right, left, keyi, key;
	keyi = left = begin;
	right = end;
	key = a[keyi];

	//根据大小将坑进行填补
	while (left < right)
	{
		while (left < right && a[right] >= key) //>=是升序，<=是降序
			--right;

		Swap(&a[keyi], &a[right]);
		keyi = right;

		while (left < right && a[left] <= key) //<=是升序，>=是降序
			++left;

		Swap(&a[keyi], &a[left]);
				keyi = left;
	}
	a[left] = key;
	keyi = left;//此时keyi为已经调整好的数据

	//[begin, keyi - 1] keyi [keyi + 1, end]
	QuickSort2(a, begin, keyi - 1);
	QuickSort2(a, keyi + 1, end);
}

挖坑版本易错点

（与前面所提的：hoare版易错点，大同小异）

? 3.?前后指针版本：

//数据交换
void Swap(int* e1, int* e2)
{
	int tmp = *e1;
	*e1 = *e2;
	*e2 = tmp;
}

//为下标为keyi的key排序
int Pointer_QSort(int* a, int begin, int end)
{
	assert(a);

	//keyi:所需要调整的数据下标
	int keyi = begin;
	int prev, cur;
	prev = begin, cur = begin + 1;

	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;
}

//前后指针版本
void QuickSort3(int* a, int begin, int end)
{
	assert(a);

	if (begin >= end)
		return;

	int keyi = Pointer_QSort(a, begin, end);

	//[begin, keyi - 1] keyi [keyi + 1, end]
	QuickSort3(a, begin, keyi - 1);
	QuickSort3(a, keyi + 1, end);
}

2.1. 快速排序的特性总结：

• 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
• 时间复杂度：O(N*logN)（最好为O(N*logN) ~ 最差为O(N^2)）
• 空间复杂度：O(logN)（最好为O(logN) ~ 最差为O(N)）
• 稳定性：不稳定

2.1.1 时间复杂度：

????????????????最好O(N*logN)的情况：

? ? ? ? ? ? ? ? ? ? ? ?快速排序是分治法实现的，那么最完美的时间就是，次次完美二分，直到完成排序。

? ? ? ? ? ? ? ? ? ? ? ?即：O(N*logN)

????????????????最差O(N^2)的情况：?

? ? ? ? ? ? ? ? ? ? ? ?快速排序是分治法实现的，那最差的情况就是：

? ? ? ? ? ? ? ? ? ? ? ?即：O(N^2)

2.1.2 空间复杂度：

????????????????主要是递归造成的栈空间的使用。

????????????????最好O(logN)的情况：

? ? ? ? ? ? ? ? ? ? ? ?需要进行logn递归调用，其空间复杂度为?O(logn)。

????????????????最差O(N)的情况：

? ? ? ? ? ? ? ? ? ? ? ?需要进行n‐1递归调用，其空间复杂度为O(n)。

2.1.3 稳定性：

2.2?快速排序的优化：

? ? ? ? 优化：时间复杂度的最坏情况与空间复杂度的最坏情况。

2.2.1?时间复杂度的优化：

//三数取中
int GetMidIndex(int* a, int begin, int end)
{
	int midi = (begin + end) / 2;

	if (a[begin] < a[midi])
	{
		if (a[end] < a[begin])
			return begin;
		else if (a[end] < a[midi])
			return end;
		else
			return midi;
	}
	else if (a[midi] < a[begin])
	{
		if (a[end] < a[midi])
			return midi;
		else if (a[end] < a[begin])
			return end;
		else
			return begin;
	}
}

? ? ? ? 正如此，当key是排序区间的最大值或最小值的时候时间复杂度为O(n^2)，那么，就利用三数取中防止此情况的发生。

2.2.2?空间复杂度的优化：

? ? ? ? 函数的递归会每增加一层，为2倍递增。所以理论上只要我们减少最后一层，就可以直接减少一半的空间的运用。所以，选择在一定的时候就不使用递归，而使用直接插入排序就是最好的选择。

三 、选择排序类：?

? 1、?直接选择排序：

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

//直接插入排序
// 对比 插入排序，谁更小。
void SelectSort(int* a, int n)
{
	assert(a);

	int begin = 0, end = n - 1;
	while (begin < end)
	{
		int mini = begin;
		for (int i = begin + 1; i <= end; ++i)
		{
			if (a[i] < a[mini])
				mini = i;
		}

		Swap(&a[begin], &a[mini]);
		++begin;
	}
}

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

• 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
• 时间复杂度：O(N^2)
• 空间复杂度：O(1)
• 稳定性：不稳定

1.1.1 时间复杂度:

????????????????时间复杂度：O(N^2)

? ? ? ? ? ? ? ? ? ? ? ?是常见的等差数列：n, n-1, n-2, …… 1。

1.1.2?空间复杂度:

????????????????空间复杂度：O(1)

1.1.3 稳定性：?

?

??2、 堆排序：

//数据交换
void Swap(int* e1, int* e2)
{
	int tmp = *e1;
	*e1 = *e2;
	*e2 = tmp;
}

//向下调整
void AdjustDown(int* a, int n, int root)
{
	int parent = root;
	int child = parent * 2 + 1;
	while (child < n) 
	{							//>大堆，<小堆
		if (child + 1 < n && 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);

	// 建堆，先从最后两个叶子上的根(索引为(n - 2) / 2开始建堆
	// 建最小的堆(最大的堆)
	for (int i = (n - 2) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);
	}


	//end:表示最后一个位置
	int end = n - 1;
	//只剩一个数时，就不需要调整了
	while (end > 0)
	{
		//0位置和最后一个位置交换
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}

1.1?建立大小堆：

? ? ? ? ? 对于向下调整，需要根节点的堆成立大小堆，否则会导致堆的混乱，而针对于一个未排序为堆的数组，如果以a[0]为父节点，会导致堆的混乱。

• 用于排序的父节点
• 代比较的子节点
• 比较后挑选出的子节点
• 对于当时的根节点，已排序好的节点

1.2 利用大小堆排序：

2.1?堆排序的特性总结：

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

2.1.1?时间复杂度:

????????首先，我们需要知道向下建堆的时间复杂度：

? ? ? ?即：O(N)。

? ? ? ?建立大小堆的时间复杂度：

? ? ? ? 于是，时间复杂度为：?O(N)。

(倒过来看，原来是从第1层向其他层看，而这个建队是从最后一个父节点开始，于是就从第h-1层看)

???????利用大小堆排序的时间复杂度：

?? ? ? 于是，时间复杂度为：?O(N*logN)。

? 单趟：

? ? ? ?在之前，我们已经建堆完成，其的无序是因为我们将最后一个元素与第一个元素交换位置。然后 n-1 ,于是唯一一个堆无序的就是第一个元素。而最差的情况就是其需要调到最底层，于是时间复杂度为O(logN)。

? 全趟：

? ? ? ?单趟是O(logN)，一共有n个元素，所以就是：O(N*logN)。

2.1.2?空间复杂度:

? ? ? ?没有使用递归，并且变量的创建也是常数。所以是O(1)。

2.1.3?稳定性:

• 用于排序的父节点
• 代比较的子节点
• 比较后挑选出的子节点
• 对于当时的根节点，已排序好的节点

? ? ? ?

四 、归并排序类：

? 1、归并排序：

//归并排序的核心实现
void _MerceSort(int* a, int begin, int end, int* tmp)
{
	assert(a && tmp);

	if (begin >= end)
		return;

	//利用递归
	int midi = (begin + end) / 2;

	_MerceSort(a, begin, midi, tmp);
	_MerceSort(a, midi + 1, end, tmp);

	// [begin, mid] [mid+1, end] 分治递归，让子区间有序
	int begin1 = begin, end1 = midi;
	int begin2 = midi + 1, end2 = end;

	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)
	{
		tmp[j++] = a[begin1++];
	}

	while (begin2 <= end2)
	{
		tmp[j++] = a[begin2++];
	}
	
	//覆盖拷贝回去
	memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}
//归并排序
void MerceSort(int* a, int n)
{
	assert(a);

	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}

	_MerceSort(a, 0, n - 1, tmp);

	free(tmp);
}

//归并排序
void MerceSortRone(int* a, int n)
{
	assert(a);

	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)
		{
			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)
			{
				tmp[j++] = a[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[j++] = a[begin2++];
			}
			//覆盖拷贝回去
			memcpy(a + i, tmp + i, sizeof(int) * m);
		}
		gap *= 2;
	}
	free(tmp);
}

//计数排序
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);

	// 统计次数
	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;
		}
	}
}