【八大排序(十)】八大排序效率与稳定性分析

💓博主CSDN主页:杭电码农-NEO💓
 
⏩专栏分类:八大排序专栏⏪
 
🚚代码仓库:NEO的学习日记🚚
 
🌹关注我🫵带你学习排序知识
  🔝🔝

八大排序总结

• 1. 前言
• 2. 什么是排序算法的稳定性?
• 3. 各大排序稳定性分析
• • 3.1 插入和希尔排序的分析
  • 3.2 选择,堆排序的分析
  • 3.3 冒泡,快速排序的分析
  • 3.4 归并排序分析
• 4. 各大算法效率比较
• 5. 总结与代码分享

1. 前言

比较八大排序不能直接将
这八个排序放在一起讨论
我们根据大致效率将它们分为两组:
(每个排序的详情链接在后面)

1. 第一组

• 插入排序 详情
• 选择排序 详情
• 冒泡排序 (略)

2. 第二组

• 堆排序 详情
• 希尔排序 详情
• 快速排序 详情
• 归并排序 详情

各大排序的进阶版本被放在了专栏:
    八大排序专栏

本篇文章将从稳定性和效率两个方面
来分析这两组排序

2. 什么是排序算法的稳定性?

官方话语是这样的:

排序序列中,有多个具有相同关键字的记录经过排序,记录对应的相对次序保持不变,这就是排序的稳定性。

举个例子,定义一个无序数组:

int a[]={5(i),3,6,4,5(j),2,8};

数组中有两个5
把第一个5记为 i
第二个5记为 j
当我们用任意算法排好序后

int a[]={2,3,4,5,5,6,8};//排好序后的数组

若 i 还在 j 前面,则这个算法是稳定的

int a[]={2,3,4,i,j,6,8};

若 i 在 j 后面,则算法不稳定

int a[]={2,3,4,j,i,6,8};

3. 各大排序稳定性分析

想要搞清楚排序是否稳定
就要明白内部的实现思路!

3.1 插入和希尔排序的分析

1. 插入排序:

插入排序是从数组中第一个元素开始
一一和它后面的元素做比较
并且一个元素向前挪动停下来的条件是:
当前元素的值大于等于正在挪动的元素

结论: 是稳定的

2. 希尔排序:

虽然希尔排序是对插入排序的优化
但是希尔排序多了一个分组预排序
当相同的数组被分到同一组时
它们的顺序不会变化
但是当相同的数据分到不同组时
排好序后的顺序就有可能改变!

结论: 不是稳定的

3.2 选择,堆排序的分析

1. 选择排序:

选择排序明显是不稳定的
当前循环选出的最大值是
这个值第一次出现的位置
将它放在数组最后,第二层循环
寻找次大值时若和刚刚的值相同
这个次打值就到倒数第二个位置了

结论: 不稳定的

2. 堆排序:

堆排序和选择排序类似
我们直接举个向下调整的例子:

蓝色的5从第一个位置跑到最后一个了

结论: 不稳定的

3.3 冒泡,快速排序的分析

1. 冒泡排序:

冒泡排序是挨个儿比较
挨个儿交换.所以不会将相同的值
交换到不同的位置

结论: 稳定的

2. 快速排序

快速排序比较特殊.
当基准值key和L,R指针相遇的点
对应的值相同时,会改变位置!
画图说明:

5的前后顺序发生了变化

结论: 不稳定的

3.4 归并排序分析

归并排序可以稳定也可以不稳定
当左右子数组中出现相同值时
如果先将左子数组的数据入数组
那么归并排序就是稳定的
如果先将右子数组的数据入数组
那么归并排序就是不稳定的

所以我们写归并排序时
数据相同时尽量先下左边

结论: 稳定的!

4. 各大算法效率比较

现实生活中处理的信息量往往非常大
这里我们随机生成五百万个数排序
试一试每一个排序算法要花多少毫秒?

注:clock是记录程序
走到当前这一行运行的时长
两个clock相减就是中间程序运行的时间

//测试性能
void TestOP()
{
	srand(time(0));
	const int N = 5000000;
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);
	int* a3 = (int*)malloc(sizeof(int) * N);
	int* a4 = (int*)malloc(sizeof(int) * N);
	int* a5 = (int*)malloc(sizeof(int) * N);
	int* a6 = (int*)malloc(sizeof(int) * N);
	int* a7 = (int*)malloc(sizeof(int) * N);

	for (int i = 0; i < N; ++i)
	{
		a1[i] = rand();
		a2[i] = a1[i];
		a3[i] = a1[i];
		a4[i] = a1[i];
		a5[i] = a1[i];
		a6[i] = a1[i];
	}

	int begin1 = clock();
	InsertSort(a2, N);
	int end1 = clock();

	int begin2 = clock();
	ShellSort(a2, N);
	int end2 = clock();

	int begin3 = clock();
	SelectSort(a3, N);
	int end3 = clock();

	int begin4 = clock();
	HeapSort(a2, N);
	int end4 = clock();

	int begin5 = clock();
	QuickSort(a2, 0, N - 1);
	QuickSort(a2, 0, N - 1);
	int end5 = clock();

	int begin6 = clock();
	MergeSort(a2, N);
	int end6 = clock();

	printf("InsertSort:%d ms\n", end1 - begin1);
	printf("ShellSort:%d ms\n", end2 - begin2);
	printf("SelectSort:%d ms\n", end3 - begin3);
	printf("HeapSort:%d ms\n", end4 - begin4);
	printf("QuickSort:%d ms\n", end5 - begin5);
	printf("MergeSort:%d ms\n", end6 - begin6);

	free(a1);
	free(a2);
	free(a3);
	free(a4);
	free(a5);
	free(a6);
}

对于五百万个数据来说
插入,选择,冒泡排序运行的时间会很长
所以我们这里直接比较第二组排序:

五百万个数据:

一百万个数据:

每个排序效率都不错
快排与归并格外的好!

5. 总结与代码分享

八大排序整体完结!
下面分享一个知识表格大全:

我将C语言实现八大排序
所有代码汇总分享给大家:

gitee代码仓库

八大排序所有内容结束!