常见排序算法详解_常用排序算法详解

目录

1：插入排序

1.1：直接插入排序

1.2：希尔排序

2：选择排序

2.1：直接选择排序

2.2：堆排序

3：交换排序

3.1：冒泡排序

3.2：快速排序

3.2.1：概念及递归实现

3.2.2：快速排序的几个优化点

3.2.3：非递归实现快速排序

3.2.4：快速排序的特性总结

4:归并排序

4.2：概念及递归实现

4.2：非递归实现

 4.3:  特性总结

5：计数排序

6：上述排序算法的复杂度和稳定性总结

---

1：插入排序

1.1：直接插入排序

  和整理扑克牌一样，直接插入排序的前提是：插入的序列是有序序列。

  如下动图：

  

  接着，我们总结这个算法的具体流程，再把它拆分为静态过程一步步分析，然后代码实现：

  对应的代码实现示例：

void InsertSort(int* arry, int size)
{
    assert(arry);
	for (int j = 1; j < size; j++)
	{
		int tmp = arry[j];
		int i = j - 1;
		while (i >= 0)
		{
			if (tmp < arry[i])
			{
				arry[i + 1] = arry[i];
			}
			else
			{
				break;
			}
			--i;
		}
		arry[i + 1] = tmp;
	}
	return;
}

  通过以上的分析可以容易得出这个算法的时间复杂度：

  当有N个数据时，如果这个数据集合原本就是升序，我们要排的也是升序，此时相当于对数据进行了一次遍历，没有进行数据位置的调整操作，所以对应的时间复杂度就是O(N)；

  而当数据原本是降序，而我们要排升序时，每次插入的数据都要调整到先前有序数据的开头，第二个数据调整1次，第三个数据调整2次，……，第N个数据调整N-1次，那么总的比较调整次数就是等差数列的和，即时间复杂度就是O(N^2)。

 而N和N^2的差距是属于数量级上差距，有时是远远超出我们想象的，比如，N = 1000, 那么N^2 = 100万；N =  1万，那么 N^2 = 1亿，……，所以当N不断增大时，这两种情况的时间效率将是天差地别。

  那么，也就是说：当原本的数据排列越接近有序，即越接近我们的预期排序（升序或降序），再对这组数据进行直接插入排序，此算法效率将大大提高。

  所以，基于上述分析，对直接插入排序优化就有了希尔排序，我们接着往下看。

1.2：希尔排序

  希尔排序又叫缩小增量排序，主要核心是：依次从原数据集合的前gap个数据为起点，把按照gap大小的间隔选出的数据当成一组进行直接插入排序，并且gap的值是由大到小变化的，当gap >= 2时，我们称为预排序。

  在每趟gap间隔排序中，gap越大，单次预排序相比较来说就越快，gap越小，单次预排序后就越接近有序。当gap = 1时，在前者大量的预排序后，理论上此次的直接插入排序的时间复杂度就很接近O(N)了。

  而关于gap的取法有多种。最初Shell提出：gap = n / 2，gap = gap / 2 （n是数据总个数），直到gap = 1; 后来，Knuth提出gap = gap / 3 + 1；还有人提出，gap都取奇数等，但都没有得到准确的数学分析证明谁是最优者。这里推荐可使用前两种。

  在Knuth所著的《计算机程序设计技巧》第3卷中,利用大量的实验统计资料得出,当n很大时,关键码平均比较次数和对象平均移动次数大约在n^1.25到1.6*n^1.25拖围内,这是在利用直接插入排序作为子序列排序方法的情况下得到的。

  上述文字叙述较难理解，所以可结合以下图示例多次理解：

  对应的代码实现示例：

void ShellSort(int* arry, int size)
{
    assert(arry);
	int gap = size / 2;
	while (gap >= 1)
	{
		for (int j = 0; j < gap; j++)
		{
			for (int k = j; k < size; k += gap)
			{
				int tmp = arry[k];
				int i = k - gap;
				while (i >= j)
				{
					if (tmp < arry[i])
					{
						arry[i + gap] = arry[i];
					}
					else
					{
						break;
					}
					i -= gap;
				}
				arry[i + gap] = tmp;
			}
		}
		gap = gap / 2;
	}
	return;
}

  值得注意的是：通过加上预排序这一优化后得到的希尔排序在对大量且乱序的数据进行排序时，效率得到了超出预期的极大提高，加之有些编译器在release模式下对算法优化的比较厉害，此算法的效率就更高了。

  为了验证希尔排序算法的效率，我们可以用下面的代码来验证：

int main()
{
	srand((size_t)time(NULL));
	int N = 10000000;//N可按需修改，但是为了效果明显，N尽量给大一些
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);
 
	for (int i = 0; i < N; i++)
	{
		a1[i] = rand() + i;
		a2[i] = a1[i];
	}
 
	int begin1 = clock();//clock()返回程序执行到此语句时消耗的处理器时间
	InsertSort(a1, N);
	int end1 = clock();
 
	int begin2 = clock();
	ShellSort(a2, N);
	int end2 = clock();
 
    //通过比较数值大小就看出两个算法的时间效率差异
	printf("InsertSort：%d\n", end1 - begin1);
	printf("ShellSort：%d\n", end2 - begin2);
 
	free(a1);
	free(a2);
	return 0;
}

  下面是小编用上面的代码做的参考示例：

  而接下来要说的几种排序算法，如果要进行效率对比的话，都会采用上面的方法，后面就不会再赘述，而是直接给对比结果了，由于测试会受多种因素影响，具有时效性，所以这里及其下面的测试对比结果都只做参考。

2：选择排序

2.1：直接选择排序

  基本思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，然后存放在序列的起始位置，接着对剩下的元素重复此过程，直到全部待排序的数据元素排完。

 如下动图：

  接着，我们将它拆分为静态，然后代码实现；

  

  此时就很容易得出时间复杂度就是：O(N^2)

  对应的代码实现示例：

void SelectSort(int* arry, int size)
{
    assert(arry);
	for (int i = 0; i < size; i++)
	{
		int min = i;
		for (int j = i + 1; j < size; j++)
		{
			if (arry[j] < arry[min])
			{
				min = j;
			}
		}
 
		if (min != i)
		{
			int tmp = arry[min];
			arry[min] = arry[i];
			arry[i] = tmp;
		}
	}
    return;
}

  既然每次都要遍历，那么就可以进行一下小优化：即每次遍历同时找到最大和最小，再按排序要求放到序列的起始和末尾，但有一些小细节要注意，如下：

对应优化后的代码为：

void Swap(int* px, int* py)
{
	int tmp = *px;
	*px = *py;
	*py = tmp;
}
 
void SelectSort(int* arry, int size)
{
	assert(arry);
	int left = 0;
	int right = size - 1;
	while (left < right)
	{
		int min = left, max = left;
		for (int i = left + 1; i <= right; i++)
		{
			if (arry[min] > arry[i])
			{
				min = i;
			}
			else if (arry[max] < arry[i])
			{
				max = i;
			}
		}
 
		//特别要注意的地方，由于max和min都是下标，值交换时，max和min的值却不会变，所以要加上条件处理
		Swap(&arry[min], &arry[left]);
		if (max == left)
		{
			max = min;
		}
		Swap(&arry[max], &arry[right]);
		++left;
		--right;
	}
	return;
}

   直接选择排序思考非常好理解，但是效率不是很好，实际中很少使用。

2.2：堆排序

   点击以下链接前往我的另一篇博客《二叉树详解》中，按目录提示可找到对应的堆排序讲解实现，此处不再赘述。

  https://blog.csdn.net/m0_74171054/article/details/133688019

  小编这里，在Release模式下用10万个随机数排序来对比一下直接选择排序和堆排序：

  差距还是很大的吧！

3：交换排序

  所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置。

3.1：冒泡排序

   这个算法的基本思路很简单：假设初始的待排序序列的总元素个数为N，那么总共进行N-1趟排序，每趟排序都遍历待排序序列，让相邻元素相互比较交换，一趟遍历排序后， 就会有一个元素像冒泡一样到达正确的位置，剩下的元素组成的新序列就是下一趟要冒泡排序的待排序序列。

  如下动图：

  相应的代码实现示例如下：

void BubbleSort(int* arry, int size)
{
	assert(arry);
	for (int i = 0; i < size - 1; i++)//一趟确定一个数
	{
        int flag = 0;
		for (int j = 0; j < size - i - 1; j++)//每趟比较对数
		{
			if (a5[j] > a5[j + 1])//此处以排升序为例
			{
				Swap(&a5[j], &a5[j + 1]);
                flag = 1;
			}
		}
        //小优化：如果一趟排序遍历后，没有元素位置的交换，说明当前的待排序序列已经有序，就退出
        if (flag == 0)
        break;
	}
    return;
}

  所以，不难得出它的时间复杂度是：O(N^2)

  就像直接选择排序一样，由于它的效率比较低，所以现实中很少会用，但这个算法却是我们大多数学习排序算法入门时被拿来做教学的经典例子。

  下面是对10万个随机数据在Debug模式下的测试比较：

3.2：快速排序

3.2.1：概念及递归实现

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

  如下动图：

  代码实现：

void QuickSort(int* arry, int begin, int end)
{
	//当begin >= end时：序列只有一个或没有数据，此时排序不再递归
	if (begin < end)
	{	
			int left = begin, right = end;
 
			while (left < right)
			{
				while (left < right && arry[right] >= arry[begin])
				{
					right--;
				}
				while (left < right && arry[left] <= arry[begin])
				{
					left++;
				}
				Swap(&arry[left], &arry[right]);
			}
			Swap(&arry[begin], &arry[left]);
    }
			//接着拆分为左右子序列，递归
			QuickSort(arry, begin, left - 1);
			QuickSort(arry, left + 1, end);
 
 
}

  基于上面Hoare的思想，还有两种不同的实现版本：分别是：挖坑法和前后指针法

  挖坑法：

  如下动图：

  代码实现：

void QuickSort(int *arry, int begin, int end)
{
    int left = begin, right = end;
	int key = arry[begin], hole = begin;
	while (left < right)
	{
		while (left < right && arry[right] >= key)
		{
			right--;
		}
		arry[hole] = arry[right];
		hole = right;
		while (left < right && arry[left] <= key)
		{
			left++;
		}
		arry[hole] = arry[left];
		hole = left;
	}
	arry[hole] = key;
 
 
	//接着拆分为左右子序列，递归
	QuickSort(arry, begin, left - 1);
	QuickSort(arry, left + 1, end);
}

前后指针法：

如下：

  代码实现：

void QuickSort(int *arry, int begin, int end)
{
    int left = begin, right = end;
 
    int prev = begin, cur = begin + 1;
    while (cur <= end)
    {
	    if (arry[cur] <= arry[begin])
	    {
		    Swap(&arry[++prev], &arry[cur]);
	    }
	    cur++;
    }
    Swap(&arry[begin], &arry[prev]);
 
    //接着拆分为左右子序列，递归
    QuickSort(arry, begin, prev - 1);
    QuickSort(arry, prev + 1, end);
}

3.2.2：快速排序的几个优化点

优化1：三数取中：

  根据二叉树的知识，在理想情况下，这个算法的时间复杂度是O(N * logN)，以2为底。但是如果出现下面这种极端情况时：

  

    此时就是有序序列，时间复杂度为O(N^2)，为了避免出现这种情况，即我们希望每次都可以分为左右子序列，为了到达这个目的，我们挑选出序列开头，中间，结尾三个元素中数值大小位于中间的元素，然后交换到序列开头作为基准值key。

优化2：小区间优化：

   还有就是：递归也是调用函数，那么就会有函数栈帧的消耗，如果递归的层次太深，时间和空间消耗较大，效率也会受到影响，比如：

  上图示例中才仅仅10个数据，即使在理想情况下，还是有那么多的递归调用消耗，而对于大量数据集合来说，这样的子序列占比超过所有划分序列的一半，如果都继续采用上图的方法，显然就不太合适了，此时对于这样的小数据集合就应该采用简单快捷的方法，比如：直接插入排序，直接选择排序，冒泡排序等，而上面已经通过一个简单的对比发现，直接插入排序较优，所以此时采用直接插入排序减少递归消耗更加合适，而10个元素划分的小区间刚刚好。

  加上三数取中和小区间优化后的代码示例如下：

void QuickSort(int* arry, int begin, int end)
{
	//当begin >= end时：序列只有一个或没有数据，此时就排序不再递归
	if (begin < end)
	{	//优化1：小区间优化，当序列区间较小时，不再进行递归分割排序，减少递归消耗，直接进行插入排序
		if ((end - begin + 1) > 10)
		{
			    //优化2：三数取中
 
				//找到中间值的下标
				int key = 0;
				int mid = begin + (end - begin) / 2;
				if (a6[begin] < a6[mid])
				{
					if (arry[mid] < arry[end])
					{
						key = mid;
					}
					else
					{
						if (arry[begin] > arry[end])
						{
							key = begin;
						}
						else
						{
							key = end;
						}
					}
				}
				else
				{
					if (arry[begin] < arry[end])
					{
						key = begin;
					}
					else
					{
						if (arry[mid] > arry[end])
						{
							key = mid;
						}
						else
						{
							key = end;
						}
					}
				}
				//将中间值和序列的第一个值交换
				if (key != begin)
				{
					Swap(&arry[begin], &arry[key]);
				}
			
            /*
                Hoare版，挖坑法，前后指针任选一种
            */
		}
		else
		{
			//插入排序
			InsertSort(arry + begin, end - begin + 1);
		}
	}
}

  这里对比一下加了优化和不加优化的区别：

  可以看出，加了优化后，效率确实提高了。

  但是在面对数据集合中有大量重复元素时，此算法还是会被拉低效率，如下：

  所以，面对大量重复数据时，又多了一个可以优化的点：三路划分

  之前的快速排序算法每次只能将一个基准值key调整到正确的位置，而三路划分的目的则是将所有==key的元素调整到一起。

  如下：

对应的代码实现：

void QuickSort1(int* arry, int begin, int end)
{
	//当begin >= end时：序列只有一个或没有数据，此时就排序不再递归
	if (begin < end)
	{	
		
			int left = begin, right = end, cur = begin + 1;
            int key = arry[begin];
			//三路划分
			while (cur <= right)
			{
				if (arry[cur] < arry[begin])
				{
					Swap(&arry[cur++], &arry[left++]);
				}
				else if (arry[cur] == arry[begin])
				{
					cur++;
				}
				else
				{
					Swap(&arry[cur], &arry[right--]);
				}
			}
 
			//接着拆分为左右子序列，递归
			QuickSort1(arry, begin, left - 1);
			QuickSort1(arry, left + 1, end);
			
	}
	return;
}

 注意：只有数据大量重复时三路划分才能充分体现它的优势，一般情况下，三数取中和小区间优化就足够了，强行在原算法基础上使用三路划分有时候反而会适得其反。

3.2.3：非递归实现快速排序

  前面就说过：快速排序是一种二叉树结构的交换排序方法，待排序序列并不是二叉树，而是通过序列区间的划分让不同的区间范围形成二叉树的逻辑关系。

  所以，快速排序的本质是分治，即划分区间排序。

  那么，每次排序时只要得到对应的区间范围就行了。

  方法就是：使用栈，入栈保存区间范围，出栈获得区间范围。

  如下代码示例：

void QuickSortNoR(int* arry, int size)
{
	assert(arry);
	//建栈
	Stack tmp;
	//初始化
	StackInit(&tmp);
	//先将整个序列区间范围入栈，注意栈后入先出的特点，不要在获取区间头尾时弄混了
	StackPush(&tmp, size - 1);
	StackPush(&tmp, 0);
	//分区循环进行排序
	while (!StackEmpty(&tmp))
	{
		//出栈：获取排序区间
		int begin = StackTop(&tmp);
		StackPop(&tmp);
		int end = StackTop(&tmp);
		StackPop(&tmp);
		//Hoare版，挖坑法，双指针任选一种
			//三数取中......
            //小区间优化…………
			//此处以前后指针法为例
		int prev = begin, cur = begin + 1;
		while (cur <= end)
		{
			if (arry[cur] <= arry[begin])
			{
				Swap(&arry[++prev], &arry[cur]);
			}
			cur++;
		}
		Swap(&arry[begin], &arry[prev]);
		//分区间入栈
		//右序列
		if (prev + 1 < end)
		{
			StackPush(&tmp, end);
			StackPush(&tmp, prev + 1);
		}
		//左序列
		if (begin < prev - 1)
		{
			StackPush(&tmp, prev - 1);
			StackPush(&tmp, begin);
		}
	}
	//销毁栈
	StackDestroy(&tmp);
 
	return;
}

3.2.4：快速排序的特性总结

1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序.

如下对比；

2. 时间复杂度：O(N*logN）

3. 空间复杂度：O(logN) 

4:归并排序

4.2：概念及递归实现

 基本思想：归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。

  将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

  如下动图：

  对应的代码示例如下：

//------------递归实现（类似后序）
void Part_MergeSort(int* a, int* tmp, int begin, int end)
{
	if (begin < end)
	{
		//拆分为左右序列
		int mid = begin + (end - begin) / 2;
		Part_MergeSort(a, tmp, begin, mid);
		Part_MergeSort(a, tmp, mid + 1, end);
		//左右序列归并到过渡内存tmp
		int cur1 = begin, cur2 = mid + 1, i = begin;
		while (cur1 <= mid && cur2 <= end)
		{
			if (a[cur1] <= a[cur2])
			{
				tmp[i++] = a[cur1++];
			}
			else
			{
				tmp[i++] = a[cur2++];
			}
		}
		while (cur1 <= mid)
		{
			tmp[i++] = a[cur1++];
		}
		while (cur2 <= end)
		{
			tmp[i++] = a[cur2++];
		}
		//将tmp中已经排好的数据拷贝到原空间中
		memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
	}
}
 
void MergeSort(int* arry, int size)
{
	assert(arry);
    //借助序列外的空间归并排序后再拷贝到原序列空间
	int* tmp = (int*)malloc(sizeof(int) * size);
	assert(tmp);
	Part_MergeSort(arry, tmp, 0, size - 1);
}

4.2：非递归实现

  就是递归实现的逆过程，如下所示：

对应的代码如下：

void MergeSortNoR(int* arry, int size)
{
	assert(arry);
	int* tmp = (int*)malloc(sizeof(int) * size);
	assert(tmp);
	int begin = 0, end = size - 1, gap = 1;
	while (gap < size)
	{
		for (int i = begin; i <= end; i += gap)
		{
			//每次归并都确保有两个区间的序列
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = end1 + 1, end2 = end1 + 1 + gap;
			//因为begin1 = i, i <= end,所以至少存在一个区间[begin1, end1], 如果只有一个区间序列，即[begin2, end2]越界不存在，跳出不排
			if (begin2 > end)
			{
				break;
			}
			//如果两个区间序列都存在
			else
			{
				//如果第二个区间的结束位置存在越界错误，就修改
				if (end2 > end)
				{
					end2 = end;
				}
			}
			//开始排序，归并到临时空间tmp中
			int j = begin1, cur1 = begin1, cur2 = begin2;
			while (cur1 <= end1 && cur2 <= end2)
			{
				if (arry[cur1] <= arry[cur2])
				{
					tmp[j++] = arry[cur1++];
				}
				else
				{
					tmp[j++] = arry[cur2++];
				}
			}
			while (cur1 <= end1)
			{
				tmp[j++] = arry[cur1++];
			}
			while (cur2 <= end2)
			{
				tmp[j++] = arry[cur2++];
			}
			//将tmp中排好的数据copy到源序列的本来起始位置
			memcpy(arry + begin1, tmp + begin1, sizeof(int) * (end2 - begin1 + 1));
		}
		gap *= 2;
	}
	return;
}

 4.3:  特性总结

1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。

  比如现在有10亿个待排序整型元素，其总大小约4G, 但是假设现在计算机的闲置可用内存只有2G，那么就不能直接一次性将所有数据都读入内存，此时就可以把数据放到容量较大的硬盘中，先把所有元素平均分割成4份后分别放入4个子文件中，然后分别将每个子文件数据读入内存进行排序，接着再写入原子文件中。那么之后的子文件之间的两两归并排序就不必再将全部数据读入内存，使用文件指针遍历比较，创建中间文件写入数据，最终就能合并到一个文件中，完成排序。

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

5：计数排序

  上述的排序算法都是比较排序，而计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用，属于非比较排序。

  其基本思路是：用一块额外的数组空间统计相同元素出现次数 ，然后根据统计的结果将序列回放到原来的序列中，如下示例：

  

  对应的代码实现如下：

void CountSort(int* arry, int size)
{
	assert(arry);
	//首先，遍历找到最小和最大值，确定范围
	int max = INT_MIN, min = INT_MAX;
	for (int i = 0; i < size; i++)
	{
		if (max < arry[i])
		{
			max = arry[i];
		}
		if (min > arry[i])
		{
			min = arry[i];
		}
	}
 
	//找到范围，定义为range,申请range范围的辅助空间
	int range = max - min + 1;
	int* tmp = NULL;
	tmp = (int*)calloc(range, sizeof(int));
	//开始排序，便利，记录源数据出现的位置此时和在tmp中的对应位置
	for (int j = 0; j < size; j++)
	{
        //注意：最小值min不一定就是数组的起始下标0
		tmp[arry[j] - min]++;
	}
	//再次遍历，将tmp中的数据还原（覆盖）到源空间，并释放辅助空间tmp
	int cur = 0;
	for (int k = 0; k < range; k++)
	{
		while (tmp[k]--)
		{
			arry[cur++] = k + min;
		}
	}
	free(tmp);
	return;
}

 时间复杂度：O(N + range)
 空间复杂度：O(range)
 局限性：只适用于数据范围（值）比较紧凑的整形

6：上述排序算法的复杂度和稳定性总结

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

  所以有：

  

 本篇分享到这就结束了，如果对你有所帮助就是对小编最大的鼓励和支持，如果可以的话，点赞，关注+收藏并分享给你的好友一起学习吧。

 关注小编，持续更新！