【数据结构与算法】万字剖析八大排序(直接插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序、计数排序)

这篇具有很好参考价值的文章主要介绍了【数据结构与算法】万字剖析八大排序(直接插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序、计数排序)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【数据结构与算法】万字剖析八大排序(直接插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序、计数排序)
【数据结构与算法】万字剖析八大排序(直接插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序、计数排序)

一.直接插入排序

初窥直接插入排序我们先来看一张动图:
【数据结构与算法】万字剖析八大排序(直接插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序、计数排序)
由动图我们可以分析出直接插入排序是从第二个数据开始遍历,与前面的数据进行比较如果小于 则让前面的数据向前移动 自己接着向前面的数据比较 直到比较到大于等于自己的数据或者没有数据能进行比较时停止 插入当前的位置。

直接插入排序性能分析:
时间复杂度:O(N^2),最好情况当数据本来就有序时可以做到O(N)
空间复杂度:直接插入排序并没再开过一段连续的空间所以为O(1)

完整代码如下,我们看到while循环中的判断即是让tmp小于的数据 不断向前覆盖 直到找到小于tmp的数据 或者 end小于0(前面没有可比较的数据)时 跳出循环将数据插入。

void InsertSort(int* a, int size)
{
	assert(a);

	for (int i = 0; i < size - 1; i++)
	{
		int tmp = a[i + 1];
		int end = i;

		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}

		a[end + 1] = tmp;
	}
}

二.希尔排序

希尔排序又称缩小增量排序,它选定了一个整数gap将待排数据分组,然后对组内的数据进行直接插入排序,接着减小gap 改变分组的区间 再进行排序。此过程称为预排序最后gap减小到1时,数据已经接近有序,再对数据进行直接插入的排序效率则较高。动图演示如下:
【数据结构与算法】万字剖析八大排序(直接插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序、计数排序)

希尔排序性能分析:
时间复杂度:最坏O(N^ 2) ,平均在<数据结构>严蔚敏中给出O(N^1.3);
空间复杂度:O(1);

完整代码如下,如有疑问随时私信或者在评论区提出。

void ShellSort(int* a, int size)
{
	assert(a);
	int gap = size;

	while (gap > 1)
	{
		gap /= 2;//使得gap最后能减到1 成为直接插入排序
		//gap /= 3 + 1;
		for (int i = 0; i < size - gap; i += gap)
		{
			int end = i;
			int tmp = a[i + gap];

			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}

	}
}

三.选择排序

选择排序在八大排序中属于是最“老实的”一个排序,其基本思想 首先选出一个关键值 一般是数据的第一位 接着遍历剩下的数据 记录剩下数据中最小值和最大值的下标。接着将最小值放到左边 最大值放到右边 接着减小需要排序的区间(因为已经排一个最大值和一个最小值了
【数据结构与算法】万字剖析八大排序(直接插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序、计数排序)
当前代码逻辑实现如下:

void SelectSort(int* a, int n)
{
	int left = 0;
	int right = n - 1;

	while (left < right)
	{
		int mini = left, maxi = left;
		for (int i = left + 1; i <= right; i++)
		{
			if (a[mini] > a[i])
			{
				mini = i;
			}

			if (a[maxi] < a[i])
			{
				maxi = i;
			}
		}
		Swap(&a[left], &a[mini]);
		Swap(&a[right], &a[maxi]);
		--right;
		++left;
	}
}

将我测试代码时发现,有些情况,上面的代码无法处理。
【数据结构与算法】万字剖析八大排序(直接插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序、计数排序)
这是为什么了,我们调试观察到:
【数据结构与算法】万字剖析八大排序(直接插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序、计数排序)
此时关键值为a[3] 6 ,在下标区间4到6遍历后max仍然是6min是3。接着min与a[left]交换即:
【数据结构与算法】万字剖析八大排序(直接插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序、计数排序)
后续最大值与a[right]交换时,原本应该放着最大值的a[left]已经被换成了最小值,所以交换会发生错误。也就是left与maxi重叠时,需要将maxi赋为mini才不会发生错误。

选择排序性能:
时间复杂度:O(N^2);
空间复杂度:O(1);

正确代码如下:

void SelectSort(int* a, int n)
{
	int left = 0;
	int right = n - 1;

	while (left < right)
	{
		int mini = left, maxi = left;
		for (int i = left + 1; i <= right; i++)
		{
			if (a[mini] > a[i])
			{
				mini = i;
			}

			if (a[maxi] < a[i])
			{
				maxi = i;
			}
		}
		Swap(&a[left], &a[mini]);
		if (left == maxi)//防止left与maxi重叠
		{
			maxi = mini;
		}
		Swap(&a[right], &a[maxi]);

		--right;
		++left;
	}
}

四.堆排序

堆排序在之前我就写过文章讲解,这里就不赘述了。需要注意的是:排升序、建大堆,排降序、建小堆文章堆和堆排序的链接

五.冒泡排序

【数据结构与算法】万字剖析八大排序(直接插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序、计数排序)
冒泡排序在学习C语言时就已经学过,所以实现它轻而易举,代码如下:

选择排序性能:
时间复杂度:O(N^2);
空间复杂度:O(1);

void BubbleSort(int* a, int size)
{
	for (int i = 0; i < size - 1; i++)
	{
		for (int j = 1; j < size  - i; j++)
		{
			if (a[j - 1] > a[j])
			{
				Swap(&a[j - 1], &a[j]);
			}
		}
	}
}

六.快速排序

1.hoare版

快速排序顾名思义它的效率较高,是由Hoare于1962年提出的一种二叉树结构的交换排序方法。它的思想是选定一个基准值,将小于基准值的数据放到左边大于的放到右边。接着在分别递归左右区间。
【数据结构与算法】万字剖析八大排序(直接插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序、计数排序)

快速排序性能:
时间复杂度:O(N*logN)最坏O(N^2)
空间复杂度:O(1);

此版本需要注意的是如果将左边第一个作为基准值就需要让右边先走,需要小于基准值的数据,相反就让左边先走

void QuickSort11(int* a, int left, int right)
{
	if (left >= right)
		return;

	int begin = left;
	int end = right;

	int keyi = left;
	while (left < right)
	{
		while (left < right && a[keyi] <= a[right])
			--right;

		while (left < right && a[keyi] >= a[left])
			++left;

		Swap(&a[left], &a[right]);
	}

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


	QuickSort11(a, begin, keyi - 1);
	QuickSort11(a, keyi + 1, end);
}

2.挖坑法

挖坑法的优化不明显,排序思想也与原先的差不多。
【数据结构与算法】万字剖析八大排序(直接插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序、计数排序)
代码如下,供大家理解:

void QuickSort22(int* a, int left, int right)
{
	if (left >= right)
		return;

	int begin = left;
	int end = right;

	int hole = left;
	int key = a[left];
	while (left < right)
	{
		while (left < right && key <= a[right])
			--right;

		a[hole] = a[right];
		hole = right;

		while (left < right && key >= a[left])
			++left;

		a[hole] = a[left];
		hole = left;
	}

	a[hole] = key;
	QuickSort22(a, begin, hole - 1);
	QuickSort22(a, hole + 1, end);
}

3.前后指针

前后指针是快速排序的第三个版本,它的做法就非常的妙:
【数据结构与算法】万字剖析八大排序(直接插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序、计数排序)
完整代码如下:

void QuickSort33(int* a, int left, int right)
{
	if (left >= right)
		return;

	int begin = left;
	int end = right;
	
	int keyi = left;
	
	int prev = left;
	int cur = prev + 1;

	while (cur <= right)
	{
		if (a[cur] <= a[keyi] && ++prev != cur)
			Swap(&a[prev], &a[cur]);

		++cur;
	}
	Swap(&a[keyi], &a[prev]);
	QuickSort33(a, begin, prev - 1);
	QuickSort33(a, prev + 1, end);
}

4.选取基准值的优化

我们知道快速排序的效率是很高的,特别是处理无序的数据时,但是当数组为有序时,时间复杂度就会下降到O(N^2),这是因为我们总是将第一个数据作为基准值导致的。这里就有个优化的方法———三数取中———它将比较mid left right的数据,取中值作为基准值,使得即使数据有序,效率也不会太差。

int GetMidNumi(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 left;
		else
			return right;
	}
	else
	{
		if (a[mid] < a[right])
			return mid;
		else if (a[right] < a[left])
			return left;
		else
			return right;
	}
}

(1)快速排序非递归

上文快速排序的三个版本都使用了递归,当数据量过大,建立的栈帧空间过多时,容易产生栈溢出,导致错误。所以我们要学习 将代码从递归改为非递归避免错误 是以后我们工作的必备技能。
快速排序的非递归需要使用到栈 使用栈辅助改为循环。
如何利用栈将快排改为循环呢?我们将数组左右下标压入栈,为了出栈顺序为先左后右,我们则要先压右下标,再压左下标。然后当栈非空时就 继续弹出区间给快排函数排序,当左右区间数据少于1时停止压栈。

void QuickSortNon(int* a, int left, int right)
{
	ST QS;
	InitST(&QS);
	Push(&QS, right);
	Push(&QS, left);

	while (!STEmpty(&QS))
	{
		int begin = STTop(&QS);
		Pop(&QS);

		int end = STTop(&QS);
		Pop(&QS);

		int key = QuickSort3(a, begin, end);
		if (begin < key - 1)
		{
			Push(&QS, key - 1);
			Push(&QS, begin);
		}
		if (key + 1 < end)
		{
			Push(&QS, end);
			Push(&QS, key + 1);
		}

	}
	DestroyST(&QS);
}

七.归并排序

归并排序采用了分治的算法思想,将数据分成两个区间不断递归到两个区间有序后,将两个区间内的数据排到新malloc的辅助空间中
演示动图如下:
【数据结构与算法】万字剖析八大排序(直接插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序、计数排序)

归并排序性能:
时间复杂度:O(N*logN)
空间复杂度:O(N);归并排序需要的辅助空间较多,所以常用于解决磁盘的外排序问题

完整代码如下:

void _MergeSort(int* a, int left, int right, int* tmp)
{
	if (left >= right)
		return;
	int mid = (left + right) / 2;

	_MergeSort(a, left, mid, tmp);
	_MergeSort(a, mid+1, right, tmp);

	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int i = begin1;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] > a[begin2])
		{
			tmp[i++] = a[begin2++];
		}
		else
		{
			tmp[i++] = a[begin1++];
		}
	}

	while(begin1 <= end1)//前面两个区间中还有多余没有拿下来的数据,一并排进去
		tmp[i++] = a[begin1++];
	while (begin2 <= end1)
		tmp[i++] = a[begin2++];

	memcpy(a + left, tmp+left, sizeof(int)*(right-left+1));
}

(2)归并排序非递归

由上面的归并排序代码我们可知,排序开始先找到mid 将数据分为两个区间,接着不断递归到区间内只有一个数据也就是有序了然后与右区间的数据进行比较排进辅助空间中。
那我们可不可以不通过递归 控制数据区间有序呢?可以直接定义gap控制一区间内的数据个数,gap初值为1,也就达到了区间有序
【数据结构与算法】万字剖析八大排序(直接插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序、计数排序)
控制如下:

	int gap=1;
	while (gap < size)
	{	
		gap *= 2;
	}

而且非递归版本不想递归有mid,便于控制区间,其区间的控制需要理解:

	int gap = 1;
	while (gap < size)
	{
		for (int i = 0; i < size; i += 2 * gap)
		{
			int begin1 = i, end1 = i + gap - 1;//区间控制
			int begin2 = i + gap, end2 = i + 2 * gap - 1;//好好体会
			int j = i;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] > a[begin2])
				{
					tmp[j++] = a[begin2++];
				}
				else
				{
					tmp[j++] = a[begin1++];
				}
			}

			while (begin1 <= end1)
				tmp[j++] = a[begin1++];
			while (begin2 <= end2)
				tmp[j++] = a[begin2++];

			memcpy(a, tmp, sizeof(int) * (end2-1+1));

		}

到这里我们就不免有个疑问,不同于上图所示,如果数据为奇数,不能正好的分区间,那该怎么办呢?
我们则需要在区间控制,再判断一下区间是否越界以及相关的处理。

	int begin1 = i, end1 = i + gap - 1;//区间控制
	int begin2 = i + gap, end2 = i + 2 * gap - 1;

区间如上所示,又因为i是0到size-1的所以end1 begin2 end2都有越界的可能,我们分类讨论解决一下。
【数据结构与算法】万字剖析八大排序(直接插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序、计数排序)
共有三种情况:

  1. end1就越界了,begin2和end2肯定也就越界了,这时只有左区间的部分数据有效所以无法进行比较+排入,所以这时的gap是错误了,此次循环不进行直接break
  2. begin2和end2越界时,这时只有左区间有效,无法进行比较+排入与第一种情况相同直接break
  3. 最后一种情况只有end2越界了,我们只需将end2赋为正常区间之内即可
    调整代码如下:
		int begin1 = i, end1 = i + gap - 1;//区间控制
		int begin2 = i + gap, end2 = i + 2 * gap - 1;
		if (end1 >= size || begin2 >= size)
		{
			break;
		}
		else if (end2 >= size)
		{
			end2 = size - 1;
		}

完整代码如下:

void _MergeSortNon6(int* a, int size)
{
	int* tmp = (int*)malloc(sizeof(int) * size);

	if (tmp == NULL)
	{
		perror("malloc fail");
	}
	int gap = 1;
	while (gap < size)
	{
		for (int i = 0; i < size; i += 2 * gap)
		{
			int begin1 = i, end1 = i + gap - 1;//区间控制
			int begin2 = i + gap, end2 = i + 2 * gap - 1;//好好体会
			if (end1 >= size || begin2 >= size)
			{
				break;
			}
			else if (end2 >= size)
			{
				end2 = size - 1;
			}

			int j = i;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] > a[begin2])
				{
					tmp[j++] = a[begin2++];
				}
				else
				{
					tmp[j++] = a[begin1++];
				}
			}

			while (begin1 <= end1)
				tmp[j++] = a[begin1++];
			while (begin2 <= end2)
				tmp[j++] = a[begin2++];

			memcpy(a, tmp, sizeof(int) * (end2-1+1));

		}

		gap *= 2;
	}
	free(tmp);
}

上面的代码是归并一部分就拷贝一部分,也可以在for循环外一次性拷贝进去,一次性拷贝对区间的控制更为麻烦,这里就不过多赘述。感兴趣的可以在我的gitee中找到代码匿名者Unit码云

八.计数排序

计数排序属于非比较排序,适合范围集中,并且范围不大的整形数组排序。

计数排序性能:
时间复杂度:O(N+range)
空间复杂度:O(range);

完整代码如下:

void CountSort(int* a, int n)
{
	int max = a[0], min = 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* countA = (int*)malloc(sizeof(int) * range);
	assert(countA);

	memset(countA, 0, sizeof(int) * range);

	for (int i = 0; i < n; i++)
	{
		countA[a[i] - min]++;
	}
	int j = 0;
	for (int i = 0; i < range; i++)
	{
		while (countA[i]--)
		{
			a[j++] = i + min;
		}
	}
}

九.八大排序稳定性分析

在排序中稳定性的含义如下:
【数据结构与算法】万字剖析八大排序(直接插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序、计数排序)
冒泡排序每一趟将一个数排到最终位置,可以控制相等条件使得冒泡稳定。
选择排序不稳定的情况就难以想到了:
【数据结构与算法】万字剖析八大排序(直接插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序、计数排序)
1小于基准值2,则将1与2交换,导致了两个2的相对顺序发生改变
直接插入排序同样可以控制相等交换条件,做到稳定排序。
希尔排序有可能会出现相同的值分到不同组中,导致不稳定的情况。
堆排序在堆调整时可能会更改相同值的相对次序,所以不稳定。
归并排序在插入辅助空间时,是按照原来的顺序 不会改变次序,所以是稳定排序。
快速排序与选择排序的情况相同,也是交换了基准值导致了不稳定的情况。
【数据结构与算法】万字剖析八大排序(直接插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序、计数排序)

文章到此结束,有疑问的随时私信或者评论区留言!文章来源地址https://www.toymoban.com/news/detail-412590.html

到了这里,关于【数据结构与算法】万字剖析八大排序(直接插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序、计数排序)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】八大排序之简单选择排序算法

    🦄 个人主页 :修修修也 🎏 所属专栏 :数据结构 ⚙️ 操作环境 : Visual Studio 2022 目录 一.简单选择排序简介及思路 二.简单选择排序的代码实现 三.简单选择排序的优化 四.简单选择排序的时间复杂度分析 结语 简单选择排序算法(Simple Selection Sort) 是一种简单直观的 选择排序算

    2024年02月01日
    浏览(78)
  • 【数据结构】--八大排序算法【完整版】

    本文主要讲解代码及代码思路,涵盖八大排序的全面知识点 ———————————————— 目录 一、直接插入排序 二、希尔排序(直接插入排序的改良版) 三、选择排序(直接选择排序) 四、堆排序 五、冒泡排序 六、快速排序 1、 左右指针法 2、挖坑法: 3、前后指针

    2024年02月16日
    浏览(46)
  • 【数据结构】 常见的八大排序算法

    排序有 内部排序和外部排序 ,内部排序是数据记录在内存中进行排序,这里八大排序就是内部排序,指直接插入,希尔,选择,堆排,冒泡,快排,归并,计数。 下面让我们来共同学习这八大排序吧!🤗🤗🤗 什么是外部排序: 外排序是数据量较大,内存放不下,数据放到外

    2024年02月12日
    浏览(111)
  • 第五章 数据结构与算法——八大排序

    目录 一、排序的概念及其运用 二、八大排序的原理及其实现(升序为例) (一)、直接插入排序 (二)、希尔排序(也叫缩小增量排序)(重要) 1.原理: 2.该排序一般分为两个步骤: 3.预排序过程: 4.预排序的意义(升序为例): 5.希尔排序的特点: 6.希尔排序代码实现

    2024年02月19日
    浏览(52)
  • 【数据结构初阶】八大排序算法+时空复杂度

    学会控制自己是人生的必修课 1.直接插入排序思想: 假设现在已经有一个有序序列,如果有一个数字插入到这段序列的末尾,我们会选择拿这个数和它前面的每个数字都比较一遍,如果前面的数字比他大,那我们就让前面的数字赋值到这个被插入的数字位置,依次与前面的数

    2024年02月01日
    浏览(116)
  • 【数据结构】八大排序算法(内含思维导图和画图分析)

    作者主页: paper jie_博客 本文作者:大家好,我是paper jie,感谢你阅读本文,欢迎一建三连哦。 本文录入于《JAVA数据结构》专栏,本专栏是针对于大学生,编程小白精心打造的。笔者用重金(时间和精力)打造,将javaSE基础知识一网打尽,希望可以帮到读者们哦。 其他专栏:

    2024年02月08日
    浏览(62)
  • 手把手教你 ,带你彻底掌握八大排序算法【数据结构】

    直接插入排序是一种简单的插入排序法,其基本思想:是把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列 可以理解为一遍摸扑克牌,一边进行排序 在待排序的元素中,假设前面n-1(其中n=2)个数

    2024年02月02日
    浏览(66)
  • C/C++数据结构——剖析排序算法

     1. 排序的概念及其运用 1.1 排序的概念 https://en.wikipedia.org/wiki/Insertion_sort https://en.wikipedia.org/wiki/Insertion_sort 排序: 所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 稳定性: 假定在待排序的记录序列中,存在多个具有相同

    2024年02月19日
    浏览(42)
  • 【数据结构---排序】庖丁解牛式剖析常见的排序算法

    排序在我们生活中处处可见,所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 常见的排序算法可以分为四大类:插入排序,选择排序,交换排序,归并排序;其中,插入排序分为直接插入排序和希尔排序;选择排序分为直接

    2024年02月16日
    浏览(61)
  • 【数据结构与算法篇】手撕八大排序算法之快排的非递归实现及递归版本优化(三路划分)

    ​👻内容专栏: 《数据结构与算法篇》 🐨本文概括: 利用数据结构栈(Stack)来模拟递归,实现快排的非递归版本;递归版本测试OJ题时,有大量重复元素样例不能通过,导致性能下降,优化快速排序通过将数组划分为三个区域,可以更有效地处理重复元素。 🐼本文作者:

    2024年02月11日
    浏览(83)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包