程序员社区

初阶数据结构——经典排序算法

🎉🎉想快速入门数据结构,推荐订阅作者的初阶数据结构专栏!此专栏预计更新:顺序表,链表,栈,队列,二叉树,排序算法等等

🎉🎉初阶数据结构我们通过c语言实现,所以此专栏也可以帮助大家巩固大家的c语言知识

🎉🎉源代码已上传至我的码云

前言

非常感谢各位小伙伴的支持,我们的初阶数据结构系列在经过这篇文章后,也迎来了它的完结!

这个系列我们使用纯c语言实现了一些简单的数据结构,用它们解决了一些简单的问题

在这里插入图片描述
当年,可能有的小伙伴会问了:为啥作者没有收录图或者其它的数据结构啊?

别急,作者在下个月开始后,会开一个c++的新坑,不仅会介绍基础语法,还会介绍一些类啊,STL和一些只能使用c++实现的数据结构,感谢各位小伙伴的持续关注哦!

毕竟,c语言还是有局限性的,使用c语言来写会非常麻烦

好!接下来开始我们今天的内容!


目录

  • 排序算法简介
  • 插入排序
    • 直接插入排序
    • 希尔排序
  • 选择排序
    • 直接选择排序
    • 堆排序
  • 交换排序
    • 冒泡排序
    • 快速排序(划重点)
      • 概述
      • 最初版本
      • 挖坑法
      • 双指针法
      • 如何把单趟组合起来?
      • 快速排序算法的问题及其改进
      • 快速排序的非递归实现
  • 归并排序
    • 递归写法
    • 非递归写法
  • 非比较排序(计数排序)
  • 排序算法之间的比较
    • O(n^2^)算法之间的比较
    • 各种算法稳定性的比较

排序算法简介

我们在生活中,会遇到各种各样的排序

比如我们在淘宝进行网购的时候

我们网购手机,将价格啊,销量啊进行排序,方便我们对商品的筛选

在这里插入图片描述
在这里插入图片描述

大家应该好奇了,这种排序在背后是咋实现的啊?别担心,今天我帮你们揭开排序神秘的面纱

排序算法按数据交互方式分,可分为以下几种

  1. 插入排序:将数据插入到有序序列中的特定位置
  2. 选择排序:选择符合要求的数据放入相应位置
  3. 交换排序:通过交换数据将它们变得有序
  4. 归并排序:归并两个有序数组

插入排序

直接插入排序

一种简单的插入算法,基本思想:

把待排序数据关键字插入到一个有序序列中的特定位置

画图求解:

在这里插入图片描述

我们从后往前检查,3-6都比2大,当发现1比2小了的时候,将2插入到1的后面

在这里插入图片描述

具体操作方法:

我们学过顺序表的插入,知道如果要插入数据的话,最好挪动关键字位置后面的数据,防止数据的覆盖

单趟排序的演示:

将已经排好序的序列的末尾开始,往后面扫描,当发现比待排序关键字小的数据后,挪动后面的数据,将待排序插入到选定数据的后面

动图演示:

在这里插入图片描述
代码:

		int end = i;//有序序列的末尾
		int x = a[end + 1];//待排序
		while (end >= 0)
		{
			if (a[end] > x)
			{
				a[end + 1] = a[end];//挪动数据
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = x;//插入

将其组合为插入排序?

我们可以从前往后遍历待排序数组,将已经遍历的数组看做是有序数组,而后面的数据是我们待排序的数据

动图展示:

在这里插入图片描述
代码实现

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

	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int x = a[end + 1];
		while (end >= 0)
		{
			if (a[end] > x)
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = x;
	}
}

性能分析:

时间复杂度:O(n2),最坏情况为逆序,扫描数组需要n次,而挪动数据又需要n次

空间复杂度:O(1)

而在最好情况,复杂度为O(n),有序数组的情况

而我们可以利用在有序或者接近有序的情况下,插入排序效率较高这一特征,对插入排序进行优化,而这个优化方式就叫希尔排序

希尔排序

希尔排序是对插入排序的优化,此排序算法分为以下两个阶段:

  1. 预排序:将一个乱序数组经过预排序,使其尽量有序
  2. 直接插入排序:经过了预排序处理,直接插入排序的效率将会提高

这个算法的重点就是预排序过程,

以下是预排序的思路:

选定一个整数gap,把待排序数组按每gap一步分组进行排序,对每一组的数据进行排序

重复,当gap=1时,就变成了直接插入排序

例如,当gap=5时的分组

在这里插入图片描述
我们只需要对9,4;1,8。。。进行排序即可

gap=2时

在这里插入图片描述
这样的预处理,我们可以使序列尽量有序,可以将较大的数据尽快挪动在数组末尾

例如,将gap=2进行预排序(单趟)

其实与插入的思想相同,插入是一次挪动1个数据,这里1次挪动gap数据(也就是将gap=2组直接看做一个序列进行插入排序)

在这里插入图片描述
代码实现:

			int end = i;//将插排的1换成了gap,其它无差别
			int x = a[end + gap];

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

而我们要完成预排序的操作时,可以用插排的思想,遍历数组,对齐进行组间交叉的预排序

在这里插入图片描述
我们的操作组是以下的关系

在这里插入图片描述
而gap我们可以逐渐减小,作者这里是每次将gap/3,直到gap为1时,进行插入排序

代码实现

void ShellSort(int* a, int n)
{
	assert(a);
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int x = a[end + gap];

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

}

性能分析:

时间复杂度:O(n1.5)大约,因为希尔排序的时间复杂度不太好算
空间复杂度:O(1)

选择排序

直接选择排序

一个非常好理解的排序

我们可以定义两个指针,寻找最大值和最小值,再与左端和右端进行交换

动图展示:

在这里插入图片描述
代码实现:

void SelectSort(int* a, int n)
{
	assert(a);

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

		Swap(&a[begin], &a[imin]);
		if (imax == begin)
			imax = imin;//这里是防止imax被换走,对imax进行修正
		Swap(&a[end], &a[imax]);
		begin++;
		end--;
	}
}

时间复杂度:O(n2),无论什么情况都是O(n2)

空间复杂度:O(1)

堆排序

我们在这篇文章中讲到了堆的实现,而堆的重要应用就是排序,点我直达文章

堆排序的步骤:

  1. 先对数组进行建堆:这篇文章是升序,升序建大堆,降序建小堆
  2. 将堆顶与数组末尾交换后,将数组大小-1,进行调整成新的大堆,再重复第二步
    首先,为什么要建大堆?

建大堆,我们可以方便选出每次待排序序列中的最大元素,方便与最后一个元素交换

过程演示:

在这里插入图片描述
建好堆后的操作:

在这里插入图片描述
代码实现:

void HeapSortDown(int* a, int n)
{
	assert(a);
	int i = 0;
	for (i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n , i);
	}//建堆操作

	for (i = n - 1; i > 0; i--)
	{
		Swap(&a[0], &a[i]);
		AdjustDown(a, i, 0);
	}//调整最大元素
}

时间复杂度:O(n*logn),建堆消耗O(n),调整执行树的高度次,也就是(logn)次

空间复杂度:O(1)

交换排序

冒泡排序

冒泡排序是我们在初学c语言时就接触到的一种简单的排序算法

基本思想是:

每次通过两两相邻的元素交换,将最大的元素交换到数组的末尾,就想冒泡一样把最大元素冒在上面

动图演示:

在这里插入图片描述
一些优化:

我们可以定义一个标记变量,当我们遍历时没有发生交换操作,(即数组已经有序)则直接跳出循环

void BubbleSort(int* a, int n)
{
	assert(a);

	int end = n;
	while (end >= 0)
	{
		int flag = 0;
		for (int i = 0; i < end - 1; i++)
		{
			if (a[i] > a[i + 1])
			{
				flag = 1;
				Swap(&a[i], &a[i + 1]);
			}
				
		}
		end--;
		if (!flag)
			break;
	}
}

时间复杂度:O(n2),但有序情况下复杂度为O(n)

空间复杂度:O(1)

快速排序(划重点)

**注意,划重点!**本文最重要的知识点,没有之一

概述

快速排序是一种二叉树结构交换算法,基本思想是:任取一个待排序中的基准值(key)(本文取数组的最左边),通过交换操作,使序列左边的值比基准值小,而右边的值比基准值大然后左右子列重复过程,直到整个序列有序

基本思想图解

在这里插入图片描述
所以,类似于二叉树,快速排序也使用递归实现
其中,交换方式有三种

最初版本

这个方式是最开始发明快速排序的人提出的

步骤是:

先标记序列的最左边和最右边,从选定key位置相反一端开始遍历,本文也就是右端向左走右端找到比key小的元素后停止,左边找到比key大的元素后停止,同时停止后交换,直到它们相遇在相遇位置赋予关键字的值

这样,就能实现我们单趟排序的目的:左比key小右比key大

动图演示

在这里插入图片描述
单趟交换的代码:

int Partion1(int* a, int left, int right)
{
	int key = left;

	while (left < right)
	{
		while (left < right && a[right] >= a[key])
		{
			right--;
		}

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

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

	return left;

}

其中while里面的while中的left<right是防止right越界,(12345)或者其它有序序列
其中a[right]>=a[key]中的>=是防止重复序列(55555)而出现死循环

挖坑法

基本思想是:

遍历方式同上,将key保存下来,并将key的位置设置为一个坑右边找到符合要求的数后,将它放在坑里面,并将符合要求的数设为一个新坑,然后左右重复操作,直到它们相遇,把key放入它们的相遇位置

动图:

在这里插入图片描述
代码实现:

int Partion2(int* a, int left, int right)
{
	int key = a[left];
	int pivot = left;
	while (left < right)
	{
		if (left < right && a[right] >= key)
		{
			right--;
		}
		a[pivot] = a[right];
		pivot = right;

		if (left < right && a[left] <= key)
		{
			left++;
		}
		a[pivot] = a[left];
		pivot = left;

	}

	a[pivot] = key;
	return pivot;
}

双指针法

基本思想:定义prev和cur。将prev放在key位置,cur初始在prev前一格
cur找比key小的数,找到后先++prev,再交换它们,如果遍历到不满足要求的数组,直接走cur

要达到的目的就是利用cur把较小数往左翻,prev把大序列往右推

动图演示:

在这里插入图片描述
代码实现:

int Partion3(int* a, int left, int right)
{
	int key = left;
	int prev = left;
	int cur = prev + 1;
	while (cur <= right)
	{
		if (a[cur] < a[key] && ++prev != cur)//prev和cur相等不用交换
		{
			Swap(&a[cur], &a[prev]);
		}
		
		cur++;

	}
	Swap(&a[prev], &a[key]);

	return prev;
}

如何把单趟组合起来?

如何把它们变的有序?

使用递归

每次将相遇位置保保存,然后对[left,key-1]和[key+1,right]继续此操作

void QuickSort(int* a, int left, int right)
{
	assert(a);

	if (left >= right)
		return;
	
	int key = Partion1(a, left, right);

	QuickSort(a, left, key - 1);//递归左序列
	QuickSort(a, key + 1, right);//递归右序列
}

快速排序算法的问题及其改进

首先,如果我们要排的是有序序列,我们的算法效率会非常低

直接到O(n2)

因为如果是12345,拿左边做key,每次就相当于要遍历一个数组但又没有任何操作,然后递归拿2接着遍历,又没有任何操作

为了解决这个问题,我们引入了三数取中法

从左,右,中间选出一个不是最大又不是最小的数字交换到左边做新的key

int GetMidIndex(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[left] < a[right])
	{
		if (a[mid] < a[left])
		{
			return left;
		}
		else if (a[mid] > a[right])
		{
			return right;
		}
		else
		{
			return mid;
		}
	}

	else
	{
		if (a[mid] < a[right])
		{
			return right;
		}
		else if (a[mid] > a[left])
		{
			return left;
		}
		else
		{
			return mid;
		}
	}
}

下一个问题是,小区间的递归层数可能会非常多,这会影响算法效率

可以设想一颗二叉树,最多的结点是叶子结点,类比于小区间

我们可以在小区间使用插入排序,而不是快速排序,小区间通常是n<10的时候

这叫做小区间优化

void QuickSort(int* a, int left, int right)
{
	assert(a);

	if (left >= right)
		return;
	
	int key = Partion3(a, left, right);
	if (right - left + 1 < 10)
	{
		InsertSort(a + left, right - left + 1);
	}//小区间优化

	QuickSort(a, left, key - 1);
	QuickSort(a, key + 1, right);
}

快速排序的非递归实现

递归总是有一个问题:如果递归深度很大,会导致栈溢出

为了解决这个问题,我们可以使用非递归实现

其中,我们如果想把递归改为非递归,有两种方法可以实现,改为循环和模拟栈实现

这里我们使用模拟栈来实现

利用栈,来保存我们要操作的区间

我们可以将区间入在栈当中,然后拿到区间后开始操作,再把[left,key-1]和[ket+1,right]分别入在栈中,重复,直到栈为空

void QuickSortNonR(int* a, int left, int right)
{
	assert(a);

	ST st;
	StackInit(&st);

	StackPush(&st, left);
	StackPush(&st, right);

	while (!StackEmpty(&st))
	{
		int end = StackTop(&st);//区间右端
		StackPop(&st);
		int begin = StackTop(&st);//区间左端
		StackPop(&st);

		int key = Partion3(a, begin, end);//对区间进行单趟排序

		if (end > key + 1)
		{
			StackPush(&st, key + 1);
			StackPush(&st, end);
		}//如果区间存在,则入栈
		if (begin < key - 1)
		{
			StackPush(&st,begin);
			StackPush(&st, key - 1);
		}//如果区间存在,则入栈
	}

	StackDestory(&st);
}

时间复杂度:O(n*logn)

空间复杂度:O(logn)(此为函数递归开辟的额外空间)

归并排序

递归写法

基本思想是:

我们可以把两个有序数组进行合并,合并成一个新的有序大数组

所以我们使用分治思想,将待排序数组分成两个数组,不断往下分,即将每个子序列有序,再使子序列段间有序

在这里插入图片描述
代码:

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;
	int end1 = mid;
	int begin2 = mid + 1;
	int end2 = right;
	int i = left;//不是0
	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 (int j = left; j <= right; j++)
	{
		a[j] = tmp[j];
	}
}



void MergeSort(int* a, int n)
{
	assert(a);

	int* tmp = malloc(sizeof(int) * n);

	if (!tmp)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	_MergeSort(a, 0, n - 1, tmp);

	free(tmp);
	tmp = NULL;
}

时间复杂度:O(n*logn)

空间复杂度:O(n)(开辟了临时数组用于归并)

非递归写法

因为归并排序使用了递归,同样有栈溢出的风险,所以我们需要掌握非递归的写法

我们还是拿上面的数组举例【10,6,7,1,3,9,4,2】

同样,递归改递归要么用栈和队列,要么用循环

这个排序递归改成非递归用循环比较合适

它的基本思路是这样的:

同样还是跟递归一样的分法,要把它们不断细分为小组逐步进行归并,这里我们可以使用gap进行归并,控制循环变量i走的步数长度不一样来控制我们小组的长度

初始将gap设置为1,每次遍历将i走2*gap步(代表两组之间的合并)

于是我们需要归并的区间为[i,i+gap-1]和[i+gap,i+2*gap-1]这两个区间

具体归并步骤与上面一样,不再阐述

动图演示:

在这里插入图片描述
至于把临时数组拷贝回原数组的问题,我们每归并一组,就拷贝一组,防止临时数组越界

代码如下:

void MergeSortNonR(int* a, int n)
{
	assert(a);
	int* tmp = malloc(sizeof(int) * n);

	if (!tmp)
	{
		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;
			int index = i;
			while (begin1 <= end1 && begin2 <= end2)//归并操作
			{

				if (a[begin1] < a[begin2])
				{
					tmp[index++] = a[begin1++];

				}
				else
				{
					tmp[index++] = a[begin2++];

				}
			}

			while (begin1 <= end1)
			{
				tmp[index++] = a[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[index++] = a[begin2++];
			}

			for (int j = i; j <= end2; j++)//拷贝
			{
				a[j] = tmp[j];
			}
		}
		gap *= 2;
	}
}

你以为这么就完了?你太天真了!

大家想想,我们要排这样的数据怎么办?

【10,6,7,1,3,9,4,2,3】
【10,6,7,1,3,9,4,2,11,3】
【10,6,7,1,3,9,4,2,3,11,14】

大家应该发现了,这样的数据,它的有些区间可能不存在!

画图展示:
在这里插入图片描述
这样就会导致一个严重的错误,数组越界

处理方式也很简单,不是要越界吗,我把越界的区间修正一下就行了

但是,不同的情况需要不同讨论,这里有以下三种情况

  1. end1,begin2,end2不存在
  2. begin2,end2不存在
  3. end2不存在

前两种情况,就代表是有一个落单的数据和落单的一组在那里找不到归并的对象,处理方式比较简单,直接跳出循环,不要它们进行归并就行

最后一种情况,一般是代表前面的数据已经排好了,只剩最后一个数或者一个组无法进入整体排序没有排,这时候我们需要调整区间的范围,把end2调整到范围内就行,不会影响归并

完整代码:

void MergeSortNonR(int* a, int n)
{
	assert(a);
	int* tmp = malloc(sizeof(int) * n);

	if (!tmp)
	{
		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;
			int index = i;
			if (end1 >= n || begin2 >= n)
			{
				break;
			}

			if (end2 >= n)
			{
				end2 = n - 1;
			}
			while (begin1 <= end1 && begin2 <= end2)
			{

				if (a[begin1] < a[begin2])
				{
					tmp[index++] = a[begin1++];

				}
				else
				{
					tmp[index++] = a[begin2++];

				}
			}

			while (begin1 <= end1)
			{
				tmp[index++] = a[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[index++] = a[begin2++];
			}

			for (int j = i; j <= end2; j++)
			{
				a[j] = tmp[j];
			}
		}
		gap *= 2;
	}
}

非比较排序(计数排序)

计数排序其实是哈希定址法的应用

思路:

  1. 遍历数组,找到最大值最小值,开辟range范围的空间(range=max-min+1)

  2. 统计数字出现次数,每出现一次在新开辟的空间的对应位置+1(对应位置:min+a[i](a[i]为此次数据))

  3. 回收数据

动图

在这里插入图片描述
代码

void CountSort(int* a, int n)
{
	assert(a);
	int max = INT_MIN;
	int min = INT_MAX;
	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);
	if (!count)
	{
		printf("malloc fail\n");
		exit(-1);
	}

	memset(count, 0, sizeof(int) * range);
	for (int i = 0; i < n; i++)
	{
		count[a[i] - min]++;
	}
	int index = 0;
	for (int i = 0; i < range; i++)
	{
		while (count[i])
		{
			a[index++] = i + min;
			count[i]--;
		}
	}
	free(count);
	count = NULL;
}

排序算法之间的比较

O(n2)算法之间的比较

我们在本篇文章中介绍的O(n^2)排序算法有三种:直接插入,直接选择,冒泡

我们通过对它们算法思想的比较,可以得出一些结论

  • 直接选择在什么情况下都是O(n2),因为不管什么情况,计算机一定会选完所有的元素后才能得出最终结论

  • 而插入排序在有序或者接近有序的情况下的效率可达O(n),比如像[1,3,2,4,5]这样的数组,插入排序只需要操作1(挪动数据)+2(检查后面的数据)次

  • 冒泡排序虽然经过了改进,但需要遍历一次数组才能判断它是否真的有序,比如还是[1,3,2,4,5],冒泡在第一次排序后成了[1,2,3,4,5],但最后还要遍历一次才能判断它有序,所以冒泡效率不如直接插入

综上,在O(n2)排序中,直接插入排序的适应性更强

各种算法稳定性的比较

关于排序稳定性的概念:

在排序中,保持排序前关键字相同的数据在排序后的相对位置不变的,我们说这个排序是稳定的,否则是不稳定

比如1,2,3,5,6,5,1我们就要保证在排序先后,前面的5始终在后面的5的前面,而不能改变它们的相对位置

稳定的排序有:冒泡排序,插入排序,归并排序

选择排序为什么不稳定?

5,4,1,5,0,9这个数组

把0与5交换位置后,5和5的相对位置发生了改变

希尔排序?

相同的值可能会在不同组中进行排序

堆排序?

全是相同的值的情况?

快速排序?

最左边与某一位置数据相等?

赞(0) 打赏
未经允许不得转载:IDEA激活码 » 初阶数据结构——经典排序算法

一个分享Java & Python知识的社区