文章目录

1 排序的概念及其运用
- 1.1 排序的概念
- 1.2 常见的排序算法
2 常见排序算法的实现

1 排序的概念及其运用

1.1 排序的概念

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i] = r[j]，且 r[i] 在 r[j] 之前，而在排序后的序列中，r[i] 仍在 r[j] 之前，则称这种排序算法是稳定的；否则称为不稳定的。

内部排序：数据元素全部放在内存中的排序。

外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

1.2 常见的排序算法

各排序算法的时间复杂度、空间复杂度及稳定性：

排序法	平均时间	最好情况	最坏情况	稳定度	额外空间	备注
冒泡排序	O( $n^2$ )	O( $n$ )	O( $n^2$ )	稳定	O(1)
插入排序	O( $n^2$ )	O( $n$ )	O( $n^2$ )	稳定	O(1)	元素集合越接近有序，直接插入排序算法的时间效率越高
希尔排序	O( $n l o g n$ )~O( $n^2$ )	O( $n^{1.3}$ )	O( $n^2$ )	不稳定,相同的值在预排时分到不同的组里面	O(1)	gap越小，越接近有序，时间复杂度越高
选择排序	O( $n^2$ )	O( $n^2$ )	O( $n^2$ )	不稳定	O(1)
堆排序	O( $n l o g n$ )	O( $n l o g n$ )	O( $n l o g n$ )	不稳定	O(1)	升序建大堆，降序建小堆
快速排序	O( $n l o g n$ )	O( $n l o g n$ )	O( $n^2$ )	不稳定	O( $n l o g n$ )~O(n)
归并排序	O( $n l o g n$ )	O( $n l o g n$ )	O( $n l o g n$ )	稳定	O(n)
计数排序	O(n+k)	O(n+k)	O(n+k)	稳定	O(n+k)	k为数值范围

与初始序列排序无关的三种情况：

元素的移动次数与关键字的初始排列次序无关的是：基数排序

元素的比较次数与初始序列无关是：选择排序

算法的时间复杂度与初始序列无关的是：选择排序

2 常见排序算法的实现

2.1 冒泡排序

基本思想

在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。每一趟排序后的效果都是将没有沉下去的元素给沉下去。

算法流程 （递增为例）

比较相邻的元素。如果第一个比第二个大，就交换他们两个
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。第一次遍历时，最后的元素应该会是最大的数
针对所有的元素重复以上的步骤
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

复杂度分析

第一次排序的比较次数：$ n-1$， n个元素相邻两两比较，需要n-1次比较;

第二次排序的比较次数：$ n-2$ ，第一次排序后最后一个元素可以确定为最大值，不需要参与第二次排序;

第三次排序的比较次数： n − 3 ，同理，最后两个数已经确定，不再需要参与排序;

第 n-1 次排序的比较次数： 1

所以冒泡排序的时间复杂度是O( $n^2$ )。空间复杂度是O(1)，稳定 。

算法实现

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
// 冒泡排序
void BubbleSort(int* a, int n)//a为待排数组，n为元素个数
{
	for (int j = n; j > 0; j--)
	{
        int flag = 0;	//表示本趟排序是否发生交换的标志
		for (int i = 1; i < j; i++)
		{
			if (a[i - 1] > a[i])
			{
				Swap(&a[i - 1], &a[i]);
                flag = 1;
			}
		}
        if(flag == 0)
        {
            break;
        }
	}
}

2.2 插入排序

基本思想

直接插入排序是一种简单的插入排序法，其基本思想是：将待排序的无序数列看成是一个仅含有一个元素的有序数列和一个无序数列，将无序数列中的元素按其关键码值的大小逐个插入到有序数列中，直到所有的记录插入完为止，得到一个新的有序序列。

算法流程

以排升序为例，依次选择每一个数，然后和这个数前面的数比较，若比前面的数小则交换，否则break，选后面一个数重复上述操作。

复杂度分析：
第1个元素，需要进行 0 次比较;
第2个元素，需要进行 1 次比较;
第3个元素，需要进行 2 次比较;
第n个元素，需要进行n-1次比较;

所以插入排序的时间复杂度是O( $n^2$ )。空间复杂度是O(1)，稳定 。

算法实现

// 插入排序
void InsertSort(int* a, int n)
{
    int i, j;
	for (i = 0; i < n; i++)//遍历每一个元素
	{
		int tmp = a[i];//保存要比较的值
		for (j = i-1; j >= 0; j--)//从后向前查找待插入位置
		{
			if (tmp < a[j])	//挪位
			{
				a[j + 1] = a[j];
			}
			else
			{
				break;
			}
		}
        a[j] = tmp; //复制到插入位置
	}
}

2.3 希尔排序

算法思想

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

希尔排序是对直接插入排序的优化。当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。

gap越大，大的和小的数可以更快的挪到对应的方向去，但是越不接近有序

gap越小，大的和小的数可以更慢的挪到对应的方向去，但是越接近有序

算法实现

// 希尔排序
void ShellSort(int* a, int n)
{
	//gap>1的时候是预排序
	//gap==1的时候是直接插入排序
	int gap = n;
	while (gap > 1)
	{
		gap = (gap / 3 + 1);//+1是为了保证gap最后为1，避免出现gap==0的情况
		//最坏的情况：逆序，gap很大时-》O（N）
		//...
		//gap很小时本来应该是O（N^2）,但是经过前面的预排序，已经接近有序，所以是O（N）
		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.4 选择排序

算法思想

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

算法流程

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

算法实现

//选择排序
void SelectSort(int* a, int n)
{
	int left = 0, right = n - 1;

	while (left < right)
	{
		//最大的值和最小的值的下标
		int minIndex = left, maxIndex = right;
		for (int i = left; i <= right; i++)
		{
			if (a[i] < a[minIndex])
			{
				minIndex = i;
			}
			if (a[i] > a[maxIndex])
			{
				maxIndex = i;
			}
		}
		Swap(&a[left], &a[minIndex]);
		//如果max和left的位置重叠，max指向的值被换走了，要修正一下max的位置
		if (left == maxIndex)
		{
			maxIndex = minIndex;
		}
		Swap(&a[right], &a[maxIndex]);
		left++;
		right--;
	}
}

2.5 堆排序

算法思想

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。

在这里插入图片描述
同时，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子

需要注意的是排升序要建大堆，排降序建小堆。
排升序为什么不能建小堆呢？建堆选出最小的数花时间N，建好堆后剩下的数父子关系全乱了，又要重新花时间N去建堆，效率太低。

算法流程

升序：大堆排序后，将最大的数和最后一位数交换，紧接着选次大的，通过控制数组的大小就能不把最后一个数看作堆里面的，向下调整就能选出次大的（父子间的关系不变，左右子树仍然是大堆排列）。（小堆排序同理）

在这里插入图片描述

算法实现

//向下调整算法
void AdjustDown(int* a, int n, int parent)
{
	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)
{
	//先建堆，升序建大堆，降序建小堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
	//第一个和最后一个数交换，树节点减一，重新建堆
	for (int i = n - 1; i > 0; i--)
	{
		Swap(&a[0], &a[i]);
		AdjustDown(a, i, 0);
	}
}

算法性能
建堆的时间复杂度分析：
在这里插入图片描述

黑色框圈住的代表的是每层有的节点的个数

第一层有2^(1-1) 个，第二层有 2^(2-1)个，第h-1层有2^(h-1-1)个，第h层有2^(h-1)个

红色框圈住的代表的是每一层的字树最多需要向下调整的次数

我们假设这个二叉树有四层，第一层需要向下调整的次数是3次，第二层是两次，第三层是1次，第四层是0次，推广到这个二叉树有h层,第一层就是h-1次，第二层是h-2次…第h-1层就是1次，第h层就是0次。

黑色框中的数乘以红色框中的数，代表着，每层的节点一共需要向下调整的次数。

假设这个满二叉树有四层
以第三层为例，第三层有4个结点，一个节点最多需要向下调整1次，那么4个节点一共需要向下调整4次

最后将每层节点需向下调整的次数相加就是最终的时间复杂度。
也就是下图:
在这里插入图片描述利用错位相减法计算

最终结果是 N-log(N+1) ，由于当N趋于很大时，log(N+1)可以忽略，
所以建堆的时间复杂度就是 O(N) ；

堆排序时间复杂度分析：
以最后一层为例，最后一层总共有 N/2 个节点，将最大节点（下标为0的元素）换到最后一共要运行树的高度次即 logN 次，所以最后一层的所有节点被交换就需要 ${N/2}*logN$ 次，由此不难看出总的时间复杂度为 $N * l o g N$

2.6 快速排序

算法思想

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

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

hoare版本
挖坑法
前后指针版本

①hoare版本

单趟排序，选出一个key，一般是最左边的或者是最右边的

目标：把key放到他正确的位置上去，左边的比key小，右边的比key大

设置左右left和right两个指针，如果选左边的值做key，right先走（右边做key，左边先走），right 找小于等于key的值，找到后停下，让left走，left找大于等于key的值，找到后停下，交换left和right指向的值，重复上述操作直到left和right相遇，相遇时将指向的值和key交换。

// 快速排序hoare版本
int PartSort1(int* a, int left, int right)
{
	int midIndex = MidIndex(a, left, right);
	Swap(&a[midIndex], &a[left]);
	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]);
	}
	//left和right相遇
	Swap(&a[left], &a[keyi]);
	return left;
}
//快排
void QuickSort(int* a, int begin, int end)
{
	if (begin > end)
	{
		return;
	}
	//小区间排序优化
	if (begin - end > 10)
	{
		int keyi = PartSort1(a, begin, end);
		QuickSort(a, begin, keyi - 1);
		QuickSort(a, keyi + 1, end);
	}
	else
	{
		InsertSort(a + begin, end - begin + 1);
	}
}

为什么相遇位置的值一定比key要小？为什么选左边的值做key，right先走？

right先走，相遇时，无论是left遇到right还是left遇到right，都是在比key小的值那里停下。

②挖坑法

先定义一个key，一般选左边或是右边，假如选左边，把这个key保存下来，left指向的位置就是一个“坑”，右边right往前走找小于等于key的值，找到后把这个值放到左边的坑里，此时right指向的位置是一个坑，然后让left往后走，找大于等于key的值，把这个值放到右边的坑里，重复上述操作，直到 left和right相遇，left和right指向同一个坑，把保存的key放到坑里。

left = 0，right = n-1，将基准数挖出形成第一个坑 $a [l e f t]$ ；
right–，由后向前找出比它小的数，找到后挖出此数 $a [r i g h t]$ 填到前一个坑 $a [l e f t]$ 中；
left++，从前向后找出比它大的数，找到后也挖出此数填到后一个坑 $a [r i g h t]$ 中；
再重复2,3，直到 left == right，将基准数填到 $a [l e f t]$ 。

然后递归左右区间

// 快速排序挖坑法
int PartSort2(int* a, int left, int right)
{
	int midIndex = MidIndex(a, left, right);
	Swap(&a[midIndex], &a[left]);
	int tmp = a[left];
	while (left < right)
	{
		//右边找小
		while (left < right && a[right] >= tmp)
		{
			--right;
		}
		//放到左边的坑里
		a[left] = a[right];
		//左边找大
		while (left < right && a[left] <= tmp)
		{
			++left;
		}
		//放到右边的坑里
		a[right] = a[left];
	}
	//left和right相遇
	a[left] = tmp;
	return left;
}
//快排
void QuickSort(int* a, int begin, int end)
{
	if (begin > end)
	{
		return;
	}
	//小区间排序优化
	if (begin - end > 10)
	{
        //调用函数
		int keyi = PartSort2(a, begin, end);
		QuickSort(a, begin, keyi - 1);
		QuickSort(a, keyi + 1, end);
	}
	else
	{
		InsertSort(a + begin, end - begin + 1);
	}

}

③前后指针法

prev 最开始是cur的前一个位置，cur去找比keyi位置小的值，找到小的值以后，++prev，再交换prev和cur位置的值，直到cur走到数组末尾后面，交换keyi 和prev位置的值。

本质是把大于key的值往右边推
在这里插入图片描述

// 快速排序前后指针法
int PartSort3(int* a, int left, int right)
{
	int midIndex = MidIndex(a, left, right);
	Swap(&a[midIndex], &a[left]);
	int key = a[left];
	int prev = left, cur = left + 1;
	while (cur <= right)
	{
		//prev用来保证前面的值能挨个被替换
		//cur找小，找到了就和prev的值交换
		//prev++后如果等与cur，自己和自己交换，无意义。
		if (a[cur] < key && ++prev != cur)
		{
			Swap(&a[cur], &a[prev]);
		}
		cur++;
	}
	Swap(&a[prev], &a[left]);
	return prev;
}
//快排
void QuickSort(int* a, int begin, int end)
{
	if (begin > end)
	{
		return;
	}
	//小区间排序优化
	if (begin - end > 10)
	{
		int keyi = PartSort3(a, begin, end);
		QuickSort(a, begin, keyi - 1);
		QuickSort(a, keyi + 1, end);
	}
	else
	{
		InsertSort(a + begin, end - begin + 1);
	}

}

快排的时间复杂度 $O(log_2(N)*N)$ – $O(N^2)$

如果要排的是一组有序数组，他的时间复杂度就会很高，针对这种情况有以下优化方法：

快排针对性优化

三数取中

找一组数中的中间值，一般是比较数组的首尾和中间位置的元素，取他们的中间值，将中间值与数组首元素交换位置。这样即使是有序的区间，它也会将这个值再换到中间并将该区间从接近中间的位置划分开来。选靠中间的值，有利于划分区间的时候更像一个完全二叉树，降低树的高度，提高效率。

本质是防止最坏的情况发生，即数组本身就是有序的，每一次只能分出一个区间，比如排升序，选左值，如果数组本身有序，每一次递归都只能分出右区间，每一个子区间都只是比父区间少了一个元素，所以时间复杂度是 $N^2$

小区间排序优化
如果这个子区间数据较多，继续选key单趟，分割子区间分治递归
如果这个子区间数据较少，递归到最下面几层，会有很多子区间，分治递归效率低。这个时候可以直接用插入排序法对他们排序
递归调用的最后一层会占用很多栈帧。所以当区间的长度小于一定数值后可以直接采用插入排序或者其他排序至今对该区间进行排序。
本质是减少递归树的最后几层，减少递归调用的次数，但是使用插入排序也是有时间消耗的。

非递归实现快排

最大的问题是递归深度太深，程序本身没问题，但是栈空间不够，导致栈溢出

只能改成非递归，改成非递归有两种方式

直接改循环-》比如斐波那契数列求解
树遍历非递归和快排非递归等等，只能用Stack存储数据模拟递归过程

快速排序的非递归遍历可以使用栈模拟二叉树的前序遍历的方式实现：

// 快速排序 非递归实现，需要使用栈
void QuickSortNonR(int* a, int left, int right)
{
	Stack s;
	stack_init(&s);
	stack_push(&s, left);
	stack_push(&s, right);
	//栈内有索引就继续排列
	while (!stack_empty(&s))
	{
		right = stack_get_top(&s);
		stack_pop(&s);
		left = stack_get_top(&s);
		stack_pop(&s);
		int keyi = PartSort3(a, left, right);
		//左区间小于标记点，入栈，排列左子区间
		if (left < keyi - 1)
		{
			stack_push(&s, left);
			stack_push(&s, keyi-1);
		}

		//右区间大于标记点，入栈，排列右子区间
		if (right > keyi + 1)
		{
			stack_push(&s, keyi + 1);
			stack_push(&s, right);
		}
	}
}

2.7 归并排序

算法思想

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

算法流程

把长度为n的输入序列分成两个长度为n/2的子序列；
对这两个子序列分别采用归并排序；
将两个排序好的子序列合并成一个最终的排序序列。

递归实现归并排序

void _Merge(int* a, int *tmp ,int begin1, int end1, int begin2, int end2)
{
	int i = begin1;
	int j = begin1;
	//对子区间排序
	while ((begin1 <= end1) && (begin2 <= end2))
	{
		if (a[begin1] < a[begin2])
		{
			tmp[i++] = a[begin1++];
		}
		else
		{
			tmp[i++] = a[begin2++];
		}
	}
	while (begin1 <= end1)
		tmp[i++] = a[begin1++];
	while (begin2 <= end2)
		tmp[i++] = a[begin2++];

	for ( ;j <= end2; j++)
	{
		a[j] = tmp[j];
	}
}
// 归并排序递归实现，类似二叉树的后序遍历
void _MergeSort(int* a, int left, int right, int* tmp)
{
	if (left >= right)
	{
		return;
	}
	//划分区间
	int mid = (left + right) >> 1;
	_MergeSort(a, left, mid, tmp);
	_MergeSort(a, mid + 1, right, tmp);
	//对每个区间进行排序
	//两端有序子区间归并tmp，并拷贝回去
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	_Merge(a, tmp, begin1, end1, begin2, end2);
}
void MergeSort(int* a, int n)
{
	//需要一个数组保存排序后的内容
	int* tmp = (int*)malloc(sizeof(int) * n);
	_MergeSort(a, 0, n - 1, tmp);
	free(tmp);
}

迭代实现归并排序

void _Merge(int* a, int *tmp ,int begin1, int end1, int begin2, int end2)
{
	int i = begin1;
	int j = begin1;
	//对子区间排序
	while ((begin1 <= end1) && (begin2 <= end2))
	{
		if (a[begin1] < a[begin2])
		{
			tmp[i++] = a[begin1++];
		}
		else
		{
			tmp[i++] = a[begin2++];
		}
	}
	while (begin1 <= end1)
		tmp[i++] = a[begin1++];
	while (begin2 <= end2)
		tmp[i++] = a[begin2++];

	for ( ;j <= end2; j++)
	{
		a[j] = tmp[j];
	}
}
// 归并排序非递归实现
void _MergeSortNonR(int* a, int n, int* tmp)
{
	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 + gap + gap - 1;
            //最后一个小组归并时，第二个小区间不存在或者第一个小区间不够gap个，不需要归并了
			if (begin2 >= n)
			{
				break;
			}
            //最后一个小组归并时，第二个小区间存在，第二个区间不够gap个，区间不完整，第二个区间的结束位置越界，需要修正
			if (end2 >= n)
			{
				end2 = n-1;
			}
			_Merge(a, tmp, begin1, end1, begin2, end2);
		}
		gap *= 2;
	}
	free(tmp);
}
void MergeSortNonR(int* a, int n)
{
	//需要一个数组保存排序后的内容
	int* tmp = (int*)malloc(sizeof(int) * n);
	_MergeSortNonR(a, n, tmp);
}

2.8 计数排序

算法思想

计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

适合情况：一组数据，数据的范围比较集中，效率很高。但局限性高，且只适合整数，如果是浮点数、字符串等不行

算法流程

找出待排序的数组中最大和最小的元素；
统计数组中每个值为 i 的元素出现的次数，存入数组Count的第 i 项；
对所有的计数累加（从Count中的第一个元素开始，每一项和前一项相加）；
反向填充目标数组：将每个元素 i 放在新数组的第Count(i)项，每放一个元素就将Count(i)减去1。

在这里插入图片描述

算法实现

// 计数排序
void CountSort(int* a, int n)
{
	int min = a[0];
	int max = a[0];
	for (int i = 0; i < n; i++)
	{
		if (a[i] > max)
			max = a[i];
		if (a[i] < min)
			min = a[i];
	}
	int range = max - min + 1;//最小值到最大值有多少个数（闭区间）
	int* count = (int*)malloc(sizeof(int) * range);
	memset(count, 0, sizeof(int) * range);
	//每个数减去min就是对应的下标值
	for (int i = 0; i < n; i++)
	{
		count[a[i] - min]++;
	}
	//写回到数组，下标+min就是原值
	int i = 0;
	for (int j = 0; j < n; j++)
	{
		while (count[j]--)
		{
			a[i++] = j + min;
		}
	}
	free(count);
}

原文链接：https://blog.csdn.net/Y673789476/article/details/125461007