栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

口口相传的八大排序算法

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

口口相传的八大排序算法

文章目录
  • 排序算法面试现状
  • 交换类
    • 冒泡排序
    • 快速排序
    • 快速排序1.0-原生hoare版本
    • 快速排序2.0-挖坑法
    • 快速排序3.0-前后双指针法
    • 快速排序4.0-非递归版本
  • 插入类
    • 直接插入排序
    • 希尔排序
  • 选择类
    • 简单选择排序
    • 堆排序
  • 归并类
    • 归并排序1.0-递归版
    • 归并排序2.0-非递归版
  • 非比较类:计数排序
  • 排序算法稳定性的意义
  • 各算法的时空间复杂度
  • 各算法性能测试
  • 递归程序的问题
  • 编者寄语

排序算法面试现状

知乎:邓卓…对排序算法的考察内容

升序为例

交换类 冒泡排序

中心思想…:每一个数从左向右依次比较,一趟下来确定一个最值放到最后,两个for循环

void BubbleSort(int* a, int n)
{
	for (int i = 0; i < n-i; i++)/跑完i躺 ,已经把i个大的数放到了最后,从前往后比的,所以不需要再比较了。
	{
		int flag = 1;
		for (int j = 0; j < n - 1-i; j++)/不用再和i个已经比他大的数比较了
		{
			if (a[j] > a[j + 1])
			{
				int tmp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = tmp;
				flag = 0;
			}
		}
		/一趟下来没有发生 交换说明俨然有序了
		if (flag == 1)
		{
			return;
		}
	}
}
快速排序

中心思想…:选定左边/右边第一个作为K值,从右往左找比它小的,从左往右找比他大的,交换;
相等停下,交换相等处值和K值,返回相等出的下标;
递归【left----K值下标】区间,和【K值下标----right】区间,直到【left>=right】return空
三数取中是在快速排序面对有序数组的神级优化插件,三个版本都可以用


快速排序1.0-原生hoare版本

三数取中
int ChooseKeysi(int*a, int left, int right)
{
	/优化---针对接近高度有序的数组,接近于冒泡排序,因为高度有序,所以取头部,中间 尾部三个数比较
/选取一个合适 的作为基准值,便会大大加快快排面对有序数组的排序效率
	int mid = left + (right - left) / 2;/防止左右坐标各自超过int的一半儿
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] < a[right])
		{
			return right;
		}
		else
		{
			return left;
		}
	}
	else  //(a[left] > a[mid])
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[left] < a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}


一趟快排
int PartSort(int* a, int left, int right)
{
	int mid = ChooseKeysi(a, left, right);
	/把左边的值换成基准值
	swap(&a[mid], &a[left]);
	int keys = left;
	while (left
		/防止右边都是大的情况,一路减减,右边遇见了左,而左边还要一直加加
		/右边找比k值小的, 如果一路没有小的便会和左边相遇,
		while (left < right && a[right]>=a[keys])
		{
			--right;
		}
		/左边找比K值大的,和上面小的交换,脚底下就是小的了,
		/相遇了就不会加加且该位置上就是小的数,就可以和K值换位置。把小的换到前面。
		while (left < right && a[left]<=a[keys])
		{
			++left;
		}
		swap(&a[left], &a[right]);
	}
	/等于的地方便是K值最合适的地方,左右区间相对有序
	/然后返回K值坐标,递归排序左右区间
	/left停的地方必定是大的地方,然后和右边的小的互换。
	swap(&a[keys], &a[left]);
	return left;
}
多趟
void QuickS(int* a, int left, int right)
{
	if (left>=right)
	{
		return;
	}
	int keyi = PartSort(a, left, right);
	/对左右区间确定K值,当left == right 时,说明只有一个数了。
	QuickS(a, left, keyi - 1);
	QuickS(a, keyi + 1, right);
}
快速排序2.0-挖坑法

在这里找到的图片

子函数2.0

int HoleSort(int* a, int left, int right)
{
	int mid = ChooseKeysi(a, left, right);
	/把左边的值换成基准值
	swap(&a[mid], &a[left]);
	int hole = left;
	int k = a[hole];
	while (left
		/右边开始走,把比key小的往洞里填
		while (left < right && a[right]>= k)
		{
			--right;
		}
		/更新洞的坐标
		a[hole] = a[right];
		hole = right;
		while (left < right && a[left]<=k)
		{
			++left;
		}
		a[hole] = a[left];
		hole = left;
	}
	a[hole] = k;
	return hole;
}
快速排序3.0-前后双指针法


子函数3.0

int DoubleSort(int* a, int left, int right)
{
	/把左边的值换成基准值
	int mid = ChooseKeysi(a, left, right);
	swap(&a[mid], &a[left]);
	/Cur比prev多一,如果cur的值比k值小,则停下来,++prev,交换两个的值
	/直至cur走到结束
	int k = left;
	int prev = left;
	int cur = prev + 1;
	while (cur<=right)
	{
		/防止一路都是小,一路原地交换
		if (a[cur]<=a[k] && cur != ++prev)
		{
			swap(&a[prev], &a[cur]);
		}
		cur++;
	}
	swap(&a[prev], &a[k]);
	return prev;
}
快速排序4.0-非递归版本

改造递归,用循环,或栈+循环

void QueickNoRecursion(int* a, int left, int right)
{
	/需要初始化栈 入栈 出栈 栈顶元素,是否为空 ,栈的销毁
	SK quc;
	SKIinit(&quc);
	/左右指针入栈,右边的先入
	SKPush(&quc, right);
	SKPush(&quc, left);
	/记住每次要处理区间的左右下标,后进先出,栈不为空就处理
	while (!SKEmy(&quc))
	{
		int lef = SKTop(&quc);
		SKPop(&quc);
		int rig = SKTop(&quc);
		SKPop(&quc);
		/基准值坐标
		int k = DoubleSort(a, lef, rig);
		/当k=左边右边时,说明待排序数组区间只剩一个了
		/则下面不会执行,空栈了,循环结束。
		if ( k
			SKPush(&quc, rig);
			SKPush(&quc, k+1);
		}
		if (lef
			SKPush(&quc, k - 1);
			SKPush(&quc, lef);
		}
	}
	SKDty(&quc);
}
插入类 直接插入排序

中心思想…:第一个坐标和后一个比,比他大则交换;第三个和前两个比较,放到合适的位置,以此类推形成相对有序,最后使整个数组有序,场景:打扑克牌

void InsertS(int* a, int n)
{
	int i = 0;
	for ( i = 0; i < n-1; i++) /i+1<=n-1
	{
		/假设前end个有序
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}
希尔排序

中心思想…:一个叫希尔的人对直接插入排序的优化,将待排序数组分为gap组,每组间隔gap,对gap个间隔为gap的分组进行直接插入排序;等比缩小gap…当gap== 1时,数组接近有序

//希尔排序 O(N^1.3)...
void ShellS(int* a, int n)
{

	int gap = n;
	while (gap>1)
	{
		/分组
		/ 2/3=0 +1 
		gap = gap / 3 + 1;
		/对多个分组同时进行直接插入排序
		for (int i = 0; i < n - gap; i++)//i+gap
			int end = i;
			int tmp = a[i + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					/确保前end个有序
					end -= gap;
				}
				else
				{
					break;
				}
			}
			/0-gap = -gap
			a[end + gap] = tmp;
		}
	}

}
选择类 简单选择排序

中心思想…:每一趟选出一个最值,放到起始位置…

void SelectS(int* a, int n)
{
	int begin = 0;
	int end = n - 1;
	int min = begin;
	int max = begin;
	while (begin
		/选出遍历一遍,选出整个数组最大最小的
		for (int i = begin; i <=end ; i++)
		{
			if (a[begin] < a[min])
			{
				min = begin;
			}
			if (a[begin] > a[max])
			{
				max = begin;
			}
		}
		/最大的放尾部,最小的放头部,同时缩减数组比较范围
		swap(&a[begin], &a[min]);
		if (begin == max)
		{
			/假设最大的是头部,换完之后,最大的跑到了min那里
			max = min;
		}
		swap(&a[end], &a[max]);
		begin++;
		end--;
	}
}
堆排序

中心思想…:找到最后一个非叶子节点,进行向下调整算法,减减到0为止。

堆排序

归并类

中心思想…:似与二叉树的前序遍历,需要将左右区间相对有序,再将整体有序;
分区间取值排序(left—mid;mid—right),放进临时数组,再将临时数组拷贝给原数组;
非递归版分成2的次方倍的gap组进行归并…

归并排序1.0-递归版

void MergerSort(int* a, int left, int right, int* tmp)
{
	/相等证明递归进来只有一个元素
	if (left >= right)
	{
		return;
	}
	/递归 左边 到 中间  中间  到 右边,分区排序
	int mid = left + (right - left) / 2;
	MergerSort(a, left, mid, tmp);
	MergerSort(a, mid+1,right, tmp);
	/归并
	int tmpi = left; /临时数组坐标起始位置

	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	/依次比较分开的数组值,进新数组
	while (begin1<=end1 && begin2<=end2)/起始坐标小于等于数组尾部坐标结束
	{
		if (a[begin1] < a[begin2])
		{
			/插入到新数组
			tmp[tmpi++] = a[begin1++];
		}
		else
		{
			tmp[tmpi++] = a[begin2++];
		}
	}
	/把没有走到头的数组继续插入新数组
	while (begin1<=end1)
	{
		tmp[tmpi++] = a[begin1++];
	}
	while (begin2<=end2)
	{
		tmp[tmpi++] = a[begin2++];
	}

	/临时数组拷贝到原数组,传过来的是闭区间
	for (int i = left; i <=right; i++)
	{
		a[i] = tmp[i];
	}
}
归并排序2.0-非递归版


void MergerSortNoRe(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	/将递归改为循坏, 依次分成1 2 4 8... 组 归并排序
	int gap = 1;
	while (gap
		for (int i = 0; i < n; i += 2*gap)
		{
			int  begin1 = i; int end1 = i + gap - 1;
			int begin2 = i + gap; int end2 = i + 2 * gap - 1;
			int ti = i ;
			/ 1、[begin2,end2] 不存在, 修正为一个不存在的区间
			/下面while 的  b2 <=end2  就不会生效,,end 1越界 begin2就会越界  
			if (begin2 >= n)
			{
				begin2 = n + 1;
				end2 = n;
			}
			/ 2、end1越界,修正一下,  gap 4  i = 8   e1  =11  数组9 
			if (end1 >= n)
			{
				end1 = n - 1;//8 
			}
			/ 3、end2越界,需要修正后归并  gap 2   i=6   b2 = 8   e2= 11
			if (end2 >= n)  
			{
				end2 = n - 1;// b2  8  end2  8   19  
			}
			while (begin1 <= end1 && begin2 <= end2)     //b1 0  end1  7   8  8  19   
			{
			/取小值放入临时数组
				if (a[begin1]
					tmp[ti++] = a[begin1++];
				}
				else
				{
					tmp[ti++] = a[begin2++];
				}
			}
			/有一个越界,一个还没比较完,则将还没比较完的给临时数组
			while (begin1 <= end1)
			{
				tmp[ti++] = a[begin1++];/b1   8    end1 7 ti 8   ti++=  9  上面结束
			}
			while (begin2 <= end2)
			{
				tmp[ti++] = a[begin2++];
			}
		}/将分成多组的每两组都进行比较,导入临时数组
		/进行下一次调整分组前将临时数组导入给原数组
		for (int i = 0; i < n; i++)
		{
			a[i] = tmp[i];
		}
		gap *= 2;
		//SortPrint(a,9);
	}

}

非比较类:计数排序

中心思想…:相对映射,原数组的值减去最小值作为临时数组的下标;临时数组下标位置统计原数组值出现的次数;最后根据临时数组的次数,将临时下标加上最小值返给原数组
1.计数排序在数据范围集中时,效率很高,但是适用范围及场景有限。
2. 时间复杂度:O(MAX(N,范围))
3. 空间复杂度:O(范围)

void ConutSort(int* a, int n)
{
	int i = 0;
	int max = a[0], min = a[0];
	for ( i = 1; i < n; i++)
	{
		if (a[i]>max)
		{
			max = a[i];
		}
		 if (a[i] < min)
		{
			min = a[i];
		}
	}	/相对映射,绝对映射,决定开辟的临时数组的大小
	/相对映射 ,数组的最大值 -- 最小值
	int tmpn = max - min+1;//40-20 21个数
	int* tmp = (int*)calloc(tmpn, sizeof(int));

	/原数组元素减去一个最小值  是tmp数组的坐标,相同的值会有相同的坐标
	/tmp元素记录 该值 出现的次数
	for ( i = 0; i < n; i++)
	{
		tmp[a[i] - min]++;
	}
	//tmp坐标
	int j = 0;
	i = 0;
	for ( j = 0; j < tmpn; j++)
	{
		while (tmp[j]--)/值出现的次数
		{
			a[i++] = j + min;  /下标加上最小值 还原元素
		}
	}

	free(tmp);
}
排序算法稳定性的意义

中心思想…:本来想等的两个值,他在前,她在后,排完序后相对位置不变;场景之一:发奖金
原始稳定的有 : 冒泡,直接插入.归并;但都可以写成不稳定

各算法的时空间复杂度

中心思想…:第一梯队:快速排序,堆排序,归并排序,平均都是(N*logN)…

各算法性能测试
/排序函数性能测试
void SortFunctionPerformanceTest()
{
	srand((unsigned)time(NULL));
	int N = 100000000;
	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];
		//a7[i] = a1[i];
	}

	//int start1 = clock();
	//InsertS(a1, N);
	//int end1 = clock();

	int start2 = clock();
	ShellS(a2, N);
	int end2 = clock();

	//int start3 = clock();
	//SelectS(a3, N);
	//int end3 = clock();

	int start4 = clock();
	QuickS(a4, 0, N - 1);
	int end4 = clock();

	int* tmp = (int*)malloc(N * sizeof(int));
	int start5 = clock();
	MergerSort(a5, 0, N - 1, tmp);
	int end5 = clock();

	//int start6 = clock();
	//ConutSort(a6,N);
	//int end6 = clock();

	//int start7 = clock();
	//BubbleSort(a7, N);
	//int end7 = clock();

	//printf("InsertSort:  %dn", end1 - start1);
	printf("ShellSort:  %dn", end2 - start2);
	//printf("SelectSort:  %dn", end3 - start3);
	printf("QuickSort:  %dn", end4 - start4);
	printf("MergerSort:  %dn", end5 - start5);
	/printf("CountSort:  %dn", end6 - start6);
	


	free(a1);
	free(tmp);
	free(a2);
	/free(a3);
	free(a4);
	free(a5);
	/free(a6);
	/free(a7);

}

我的快排可能有问题…

递归程序的问题

编者寄语

秉持着自己写的代码,只有自己看的懂的原则…hhh,单链表专训练,二叉树专题训练,大复习作业…

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/957410.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号