数据结构-快速排序“人红是非多”？看我见招拆招

目录

1.快速排序

Hoare版本：

挖坑法：

前后指针版本:

快速排序的时间复杂度

2.快速排序的优化

三数取中法选key

随机数选key

三路划分法

3. 非递归实现快速排序

1.快速排序

快速排序一共有三种版本：Hoare版本、挖坑法、前后指针版本。

Hoare版本：

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

也就是说如果我们要排一个升序，我们可以在待排数据中选择一个值key，把大于该值的数据放在该值的右边，小于该值的数据放在该值的左边，然后在左边的数据中同样选择一个值，重复以上步骤，同时，在右边的数据中选择一个值，重复以上步骤，直到key的左边和右边都是有序的，此时所有数据都有序了。

过程如图所示，是一个递归的过程：

下面我们先来实现一趟的排序：

可以选左边第一个数据为key，然后从右边先开始遍历，当右边找到小于key的值时，停下来，当左边遍历找到大于key的值时，也停下来，然后交换左右两边的数据，最后当左右相遇的时候，把key交换到相遇位置，这就保证了小于key的数据落入key左边，大于key的数据落在key右边。

上代码：

int PartSort(int* a, int left, int right)
{
	int key = a[left];
	int keyi = left;
	while (left < right)
	{
		while (left < right && a[right] >= key)
		{
			right--;
		}
		while (left < right && a[left] <= key)
		{
			left++;
		}
		Swap(&a[left], &a[right]);
	}
	Swap(&a[keyi], &a[left]);
	return left;
}

我们单趟排完之后应该如下图所示：

下面来解释一下代码中的循环判断条件：

最外层循环：left<right，左右相遇时就停止。

内层循环：left < right && a[right] >= key，这段代码解决了两个可能存在的问题：

1.  死循环问题

当待排数据如下面所示就可能造成死循环：

所以a[right] >= key时继续遍历。

2. 越界问题

如果a[right] >= key时继续遍历，下面极端情况可能导致越界：

所以我们在内层循环中还要判断一下 left<right。

这就是单趟排序的代码了，我们要实现对所有数据的升序，递归调用就行了，当完成一趟排序时，返回相遇位置，然后对相遇位置的左边和右边数据继续重复进行以上操作。这有些类似于二叉树的递归问题。

代码如下：

//交换函数
Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
//快速排序
int PartSort(int* a, int left, int right)
{
	int key = a[left];
	int keyi = left;
	while (left < right)
	{
		while (left < right && a[right] >= key)
		{
			right--;
		}
		while (left < right && a[left] <= key)
		{
			left++;
		}
		Swap(&a[left], &a[right]);
	}
	Swap(&a[keyi], &a[left]);
	return left;
}

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	int keyi = PartSort(a, begin, end);
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1,end);
}

Print(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}
int main()
{
	int a[] = { 9,7,5,2,4,7,1,6,0,8 };
	QuickSort(a, 0, sizeof(a) / sizeof(int) - 1);
	Print(a, sizeof(a) / sizeof(int));

	return 0;
}

整个排序过程如下图：

注意下面这段代码的作用是：当区间只有一个值或者出现区间不存在的情况的时候就返回。

 if (begin >= end)
    {
        return;
    }

不知道大家有没有注意到一个情况，我们在选择key为左边的数据时，先让右边开始遍历，这是为什么呢？

首先，我们选左边的数据为key，那最终相遇位置的数就一定要比key的值小，这样交换后才能保证key的左边的值都比它小，右边的值都比它大，那我们如何保证相遇位置的值一定就比key小呢？

先给结论:

1. 左边做key，右边先走；保证了相遇位置的值比key小。

2. 右边做key，左边先走；保证了相遇位置的值比key大。

下面我们来论证一下：

结论2的论证同上。

这就是Hoare版本，但是通过上文的学习，这种版本存在的坑太多，下面我们来学一种方法避坑。

挖坑法：

挖坑法的单趟排序过程如图所示：

先选左边的一个数据，把它作为坑，并保存它的值，然后继续右边遍历找到比key小的值就停下，挖走这个值填坑，挖走后形成新的坑，左边遍历找比key大的值就停下，挖走这个值填坑......最后左右相遇，把保存的key值填坑。

代码实现如下:

//挖坑法
int PartSort2(int* a, int left, int right)
{
	int key = a[left];
	int hole = left;
	while (left < right)
	{
		while (left < right && a[right] >= key)
		{
			right--;
		}
		a[hole] = a[right];
		hole = right;
		while (left < right && a[left] <= key)
		{
			left++;
		}
		a[hole] = a[left];
		hole = left;
	}
	a[hole] = key;
	return hole;
}

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	int keyi = PartSort2(a, begin, end);
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}
Print(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}
int main()
{
	int a[] = { 9,7,5,2,4,7,1,6,0,8 };
	QuickSort(a, 0, sizeof(a) / sizeof(int) - 1);
	Print(a, sizeof(a) / sizeof(int));

	return 0;
}

前后指针版本:

前后指针版本单趟排序过程如下图所示：

我们可以看到，cur在找小，如果a[cur]<key，prev++，然后交换a[prev]和a[cur]，如果a[cur]>key，prev不动，整个过程中cur一直不停的往后走，直到cur越界就结束了，此时再交换key和a[prev]。

代码如下：

//前后指针版本
int PartSort3(int* a, int left, int right)
{
	int prev = left;
	int cur = left + 1;
	int keyi = left;
	while (cur <= right)
	{
		if (a[cur] <= a[keyi])
		{
			prev++;
			Swap(&a[prev], &a[cur]);
		}
		cur++;
	}
	Swap(&a[prev], &a[keyi]);
	keyi = prev;
	return keyi;
}
void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	int keyi = PartSort3(a, begin, end);
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}
Print(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}
int main()
{
	int a[] = {6,1,2,7,9,3,4,5,10,8};
	QuickSort(a, 0, sizeof(a) / sizeof(int) - 1);
	Print(a, sizeof(a) / sizeof(int));

	return 0;
}

快速排序的时间复杂度

时间复杂度（最好）：O(N*logN)。

时间复杂度（最坏）：O(N^2)。

什么时候最好呢？

当每次选的key恰好是中位数时，每次都把数据分成两份，每次减少一半的运算量，相当于二分法：

什么时候最坏呢？

当待排数据本来就是有序的时候，每次选key，选的都是最小的值，此时就相当于等差数列：

那我们选key有两种方案：

1. 随机数取key。

2. 三数取中法选key。

这样可以保证不会是最坏的情况。

2.快速排序的优化

三数取中法选key

三数取中法就是，把左边、右边和中间的三个数相比较，取出其中的中位数，把它作为key，这样就可以提高快速排序的效率。

代码如下：

//三数取中法选key
int GetMidIndex(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[mid] < a[left])
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[right] > a[left])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[right] > a[left])
		{
			return right;
		}
		else
		{
			return left;
		}
	}
}
//快速排序
//Hoare版本
int PartSort(int* a, int left, int right)
{

	int midi = GetMidIndex(a, left, right);
	Swap(&a[left], &a[midi]);

	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]);
	}
	Swap(&a[keyi], &a[left]);
	return left;
}

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	int keyi = PartSort(a, begin, end);
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

以上就是三数取中法对快速排序的优化了，下面我们来看一道题，看看我们的快速排序能不能通过？

题目链接：力扣（LeetCode）

结果呢？

超出时间限制了，这其实是力扣针对快速排序三数取中专门设计的一个测试用例，他故意把左边、右边和中间的值都设的很小，这样即使你三数取中，选出的key依旧很小，接近我们上文说的最坏情况，所以会超出时间限制，那我们不玩三数取中能不能过呢？

结果很明显，还是过不了，这次他直接给了个有序的测试用例，这就直接是我们上文中所说的最坏情况了，那怎么办呢？别急，我们还有一招：

随机数选key

随机数取key的意思是，我们保证左右的数据位置不变，中间数据的位置取一个随机数，这样我们三数取中得到的key也是随机的数据，这样力扣就针对不到我们了。

代码如下：

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

//三数取中法选key
int GetMidIndex(int* a, int left, int right)
{
    //随机数取key
	int mid=left+(rand()%(right-left));

	if (a[mid] < a[left])
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[right] > a[left])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[right] > a[left])
		{
			return right;
		}
		else
		{
			return left;
		}
	}
}
//前后指针版本
int PartSort3(int* a, int left, int right)
{
	int midi = GetMidIndex(a, left, right);
	Swap(&a[left], &a[midi]);

	int prev = left;
	int cur = left + 1;
	int keyi = left;
	while (cur <= right)
	{
		if (a[cur] <= a[keyi])
		{
			prev++;
			Swap(&a[prev], &a[cur]);
		}
		cur++;
	}
	Swap(&a[prev], &a[keyi]);
	keyi = prev;
	return keyi;
}
void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	int keyi = PartSort3(a, begin, end);
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

int* sortArray(int* nums, int numsSize, int* returnSize) {
	  srand(time(0));
    QuickSort(nums,0,numsSize-1);
    *returnSize=numsSize;
    return nums;
}

int mid=left+(rand()%(right-left));

表示中间位置取随机位置，为了防止随机数越界，我们用它取余（right-left）。

但是这就结束了吗？还是太天真了，力扣预判了你的预判，不信再运行一下：

这次它给的数据全部相同，那不管我们怎么取key值都是取的最小的，这就又相当于最坏的情况，可见这道题为了针对快速排序是费尽了心思，那我们就没办法了吗？

当然不是，我们还有终极一招，

三路划分法

何谓三路划分呢？我们之前的快速排序是把大于等于key的放在右边，小于等于key的放在左边，相当于待排数据分为两份，而三路划分的意思是把小于key的放在左边，大于key的放在右边，等于key的放在中间，如图所示：

这种方法就是把等于key的收拢在中间位置，当我们递归子区间的时候，只递归小于和大于的区间，这样当待排数据中有重复数据时，可以大大提高效率，尤其是上述测试用例，收拢之后，左右子区间直接就没有值了，都不用再递归。

下图就是三路划分的思想：

我们可以演示一下三路划分的过程：

可以看到，三路划分的本质就是：

1. 和key相等的值都被收拢到中间

2. 小的被甩到左边，大的被甩到右边。

代码如下：

//三数取中法选key
int GetMidIndex(int* a, int left, int right)
{
	//随机数取key
	int mid=left+(rand()%(right-left));
	if (a[mid] < a[left])
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[right] > a[left])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[right] > a[left])
		{
			return right;
		}
		else
		{
			return left;
		}
	}
}

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	//三数取中
	int midi = GetMidIndex(a, begin, end);
	Swap(&a[begin], &a[midi]);

  int left=begin;
  int right=end;
  int cur=left+1;
  int key=a[left];
	//三路划分
  while (cur  <= right)
	{
		if (a[cur] < key)
		{
			Swap(&a[left], &a[cur]);
			left++;
			cur++;
		}
		else if (a[cur] > key)
		{
			Swap(&a[right], &a[cur]);
			right--;
		}
		else
		{
			cur++;
		}
	}
	//递归
	QuickSort(a, begin, left - 1);
	QuickSort(a, right + 1, end);
}

int* sortArray(int* nums, int numsSize, int* returnSize) {
	  srand(time(0));
    QuickSort(nums,0,numsSize-1);
    *returnSize=numsSize;
    return nums;
}

到这，这道题就用了三种优化方式了，而且三种方式缺一不可，那能不能解决问题呢？

当然可以啦，如果没有上述优化方式，用快排做这道题会很坑，不是快排不快，而是“人红是非多”啊，快排在这道题上被针对的体无完肤，反而堆排、希尔排序等还能通过。

3. 非递归实现快速排序

 我们前文讲的递归方式，实际上递归过程处理的是左右子区间，现在我们不能用递归，那要如何处理左右子区间呢？

其实可以用栈实现，每次从栈中拿出一段区间，单趟分割处理，然后让左右子区间入栈。

代码如下（栈部分的代码可以拷贝前面章节的，这里只给核心代码）：

//前后指针版本
int PartSort3(int* a, int left, int right)
{
	int prev = left;
	int cur = left + 1;
	int keyi = left;
	while (cur <= right)
	{
		if (a[cur] <= a[keyi])
		{
			prev++;
			Swap(&a[prev], &a[cur]);
		}
		cur++;
	}
	Swap(&a[prev], &a[keyi]);
	keyi = prev;
	return keyi;
}
//非递归方式实现快排
void QuickSortNonR(int* a, int begin, int end)
{
	ST st;
	STInit(&st);
	STPush(&st, end);
	STPush(&st, begin);

	while (!STEmpty(&st))
	{
		int left = STTop(&st);
		STPop(&st);

		int right = STTop(&st);
		STPop(&st);

		int keyi = PartSort3(a, left, right);

		if (keyi + 1 < right)
		{
			STPush(&st, right);
			STPush(&st, keyi + 1);
		}

		if (left < keyi-1)
		{
			STPush(&st, keyi-1);
			STPush(&st, left);
		}
	}

	STDestroy(&st);
}

好了，以上就是快速排序，下节继续学习归并排序，

未完待续。。。 

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/175798.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

跑步耳机哪种好？运动耳机什么牌子好？无线运动耳机品牌排行

跑步耳机哪种好？运动耳机什么牌子好？无线运动耳机品牌排行

​运动健身已经成为当下最热门的运动健康项目&#xff0c;越来越多的人开始加入到这个行列中来。而在运动的过程中&#xff0c;佩戴一款适合自己的运动耳机听歌&#xff0c;不仅可以增加运动的乐趣&#xff0c;还能帮助我们更好地集中注意力&#xff0c;提高运动效果。然而&…
阅读更多...
matplotlib设置y轴刻度范围【已解决】

matplotlib设置y轴刻度范围【已解决】

用matplotlib绘制个一个图&#xff0c;但是y轴刻度过大&#xff0c;因为AUC本身最大值是1&#xff0c;所以现在需要修改y轴刻度 上图的代码如下 import matplotlib.pyplot as plt import numpy as np# 假设你的数据范围是0.5到1 y_ticks_range np.arange(0.5, 1.1, 0.1)# 示…
阅读更多...
redis的一些操作

redis的一些操作

文章目录 清空当前缓存和所有缓存配置内存大小&#xff0c;防止内存饱满设置内存淘汰策略键过期机制 清空当前缓存和所有缓存 Windows环境下使用命令行进行redis缓存清理 redis安装目录下输入cmdredis-cli -p 端口号flushdb 清除当前数据库缓存flushall 清除整个redis所有缓存…
阅读更多...
Oracle 的 Java SE、OpenJDK、Database 链接

Oracle 的 Java SE、OpenJDK、Database 链接

1 访问主站 Oracle | Cloud Applications and Cloud Platform 2 开发者 2.1 OpenJDK (这里的不用登录&#xff0c;就可以下载) JDK Builds from Oracle 2.2 JavaSE (需要登录&#xff0c;才可以下载) Java Downloads | Oracle 2.3 DataBase (MySQL为例) MySQL :: MySQL Dow…
阅读更多...
RFID读写器在物联网中的应用与优势

RFID读写器在物联网中的应用与优势

随着物联网技术的不断发展&#xff0c;RFID读写器作为物联网感知层的重要组成部分&#xff0c;在各个领域得到了广泛应用。本文将介绍RFID读写器在物联网中的应用及优势。 一、RFID读写器概述 RFID&#xff08;Radio Frequency Identification&#xff09;技术是一种利用无线…
阅读更多...
HT560 30W 过温限幅 D类音频功率放大器

HT560 30W 过温限幅 D类音频功率放大器

HT560具有过温限幅功能&#xff0c;当芯片内部温度达到过温限幅点&#xff0c;HT560自动降低增益&#xff0c;使其IC能够连续播放而不间断。另外&#xff0c;HT560具有功率限制功能&#xff0c;一种是限幅功能&#xff0c;在输出端限制一定的输出幅度&#xff0c;使其不损坏喇叭…
阅读更多...
力扣OJ题讲解——循环队列

力扣OJ题讲解——循环队列

今天我们一起来做一道关于队列的OJ题目&#xff0c;这是力扣题目622题&#xff0c;点击题目链接可以直接跳转&#xff0c;https://leetcode.cn/problems/design-circular-queue/ 首先&#xff0c;我们看到要求&#xff0c;需要我们实现哪些功能&#xff1f; 我们需要设置队列长…
阅读更多...
【科技素养】蓝桥杯STEMA 科技素养组模拟练习试卷2

【科技素养】蓝桥杯STEMA 科技素养组模拟练习试卷2

单选题 1、两袋中分别有同样多的硬糖和酥糖&#xff0c;现将第一袋中的20块酥糖放到第二袋中&#xff0c;第二袋中的硬糖和酥糖相同&#xff0c;接着又将第二袋中的20块硬糖放到第一袋中&#xff0c;则第一袋中的硬糖是酥糖的4倍&#xff0c;问原来一袋中有&#xff08;&#…
阅读更多...
模电知识点总结（一）运算放大器

模电知识点总结（一）运算放大器

系列文章目录 文章目录 系列文章目录前言集成运算放大器基本线性运放电路虚短和虚断同向放大电路电压跟随器反向放大电路差分放大电路仪用放大器求和电路积分电路微分电路 前言 由于模电知识一直没用到&#xff0c;之前一直觉得没有什么用处&#xff0c;但是我越来越发现基础知…
阅读更多...
基于Springboot的美容院管理系统（有报告）。Javaee项目，springboot项目。

基于Springboot的美容院管理系统（有报告）。Javaee项目，springboot项目。

演示视频&#xff1a; 基于Springboot的美容院管理系统&#xff08;有报告&#xff09;。Javaee项目&#xff0c;springboot项目。 项目介绍&#xff1a; 采用M&#xff08;model&#xff09;V&#xff08;view&#xff09;C&#xff08;controller&#xff09;三层体系结构&a…
阅读更多...
振南技术干货集：制冷设备大型IoT监测项目研发纪实（3）

振南技术干货集：制冷设备大型IoT监测项目研发纪实（3）

注解目录 1.制冷设备的监测迫在眉睫 1.1 冷食的利润贡献 1.2 冷设监测系统的困难 &#xff08;制冷设备对于便利店为何如何重要&#xff1f;了解一下你所不知道的便利店和新零售行业。关 于电力线载波通信的论战。&#xff09; 2、电路设计 2.1 防护电路 2.1.1 强电防护…
阅读更多...
差分放大器工作原理（差分放大器和功率放大器区别）

差分放大器工作原理（差分放大器和功率放大器区别）

差分放大器是一种特殊的放大器&#xff0c;它可以将两个输入信号的差异放大输出。其工作原理基于差分放大器的电路结构和差分输入特性。 一、差分放大器电路结构 差分放大器一般由四个基本电路组成&#xff1a;正反馈网络、反相输入端、共模抑制电路和差分输入端。其中&#xf…
阅读更多...
云存储解决方案-阿里云OSS

云存储解决方案-阿里云OSS

云存储解决方案-阿里云OSS 1. 阿里云OSS简介 ​ 阿里云对象存储服务&#xff08;Object Storage Service&#xff0c;简称OSS&#xff09;为您提供基于网络的数据存取服务。使用OSS&#xff0c;您可以通过网络随时存储和调用包括文本、图片、音频和视频等在内的各种非结构化数…
阅读更多...
纯干货丨电脑监控软件有哪些（三款电脑监控软件大盘点）

纯干货丨电脑监控软件有哪些（三款电脑监控软件大盘点）

电脑监控软件在日常生活和工作中的应用越来越广泛。这些软件可以帮助我们监控电脑的使用情况&#xff0c;保护电脑的安全&#xff0c;提高工作效率。本文将介绍一些高人气的电脑监控软件&#xff0c;并分享一些纯干货。 1、 域之盾软件----电脑监控系统 是一款功能强大的电脑监…
阅读更多...
渗透测试过程中的JS调试（一）

渗透测试过程中的JS调试（一）

前言 前端调试是安全测试的重要组成部分。它能够帮助我们掌握网页的运行原理&#xff0c;包括js脚本的逻辑、加解密的方法、网络请求的参数等。利用这些信息&#xff0c;我们就可以更准确地发现网站的漏洞&#xff0c;制定出有效的攻击策略。前端知识对于安全来说&#xff0c;…
阅读更多...
2023年中国雷达设备市场规模及市场份额分析[图]

2023年中国雷达设备市场规模及市场份额分析[图]

雷达设备行业是一种利用无线电波对目标进行探测和定位的技术&#xff0c;也被称为无线电探测和定位。雷达通过发射电磁波对目标进行照射并接收其回波&#xff0c;经波形处理后获取目标的位置和速度等信息。雷达具有探测距离远&#xff0c;测定精度高&#xff0c;不受天气和地形…
阅读更多...
如何正确复制CSDN文章到自己的博客

如何正确复制CSDN文章到自己的博客

1.csdn 文章页面&#xff0c;按f12打开浏览器开发者工具 2.按ctrl f 找 "article_content" 3.在该元素源代码上右键 “Copy”->“Copy element” 4.新建一个txt文件,把你粘贴的东西复制进去,然后再把文件名的后缀改为html,然后打开html文件,把里面的内容ctrlA全部…
阅读更多...
Java生成一个区域内的经纬度随机点的方式

Java生成一个区域内的经纬度随机点的方式

准备&#xff1a; 1、四个角点&#xff08;四个点确定一个框&#xff09; 2、想要细分程度 &#xff08;这里说的是经纬度&#xff0c;这里没有对经纬度做更细的区分&#xff09; 如&#xff1a;0.000001约等于0.1m&#xff0c;0.00001约等于1m&#xff0c;0.0001约等于10m 。。…
阅读更多...
【老文新发】Otsu大津法详解及python实现

【老文新发】Otsu大津法详解及python实现

原文&#xff1a;A Threshold Selection Method from Gray-Level Histograms A Fast Algorithm for Multilevel Thresholding 前言 大津法包含两个重要的概念&#xff1a;类间方差&#xff08;between-class variance&#xff09;和类内方差&#xff08;within-class varianc…
阅读更多...
opencv-图像轮廓

opencv-图像轮廓

轮廓可以简单认为成将连续的点&#xff08;连着边界&#xff09;连在一起的曲线&#xff0c;具有相同的颜色或者灰度。轮廓在形状分析和物体的检测和识别中很有用。 • 为了更加准确&#xff0c;要使用二值化图像。在寻找轮廓之前&#xff0c;要进行阈值化处理或者 Canny 边界检…
阅读更多...
最新文章

Copyright @ 2022~2023