常见八大排序(纯C语言版)

目录

基本排序

一.冒泡排序

二.选择排序

三.插入排序

进阶排序(递归实现)

一.快排hoare排序

1.单趟排序

快排步凑

快排的优化

(1)三数取中

(2)小区间优化

二.前后指针法(递归实现)

三.快排的非递归实现(前后指针法的非递归)

快排的挖坑法的实现

二.堆排序

1.建堆的选择

2.堆排序的实现

二希尔排序

三.归并排序(递归实现与非递归的实现)

归并排序(非递归实现)

四.非比较排序(计数排序)

计数排序的缺陷

五.排序总结

稳定性的概念

六,排序的选择题练习与巩固


欢迎各位大佬的关顾,能给个赞就好了QWQ,由于篇幅很大,可以根据目录跳转你想看的排序哦!!

基本排序

一.冒泡排序

冒泡排序即,每次相邻比较排序,每次将最小或最大固定在数组最后

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

二.选择排序

很明显选择排序就是去找最小或者最大的下标然后赋值给原始位置,代码实现如下

void SelectSort(int* arr, int len)
{
	for (int i = 0; i < len-1; i++)
	{
		int min = i;
		for (int j = i + 1; j < len; j++)
		{
			if (arr[j] < arr[min])
				min = j;
		}
		Swap(&arr[min], &arr[i]);
	}
}

但是这种选择排序也太low了让我们来实现一个Plus版本,一次循环找到最大与最小

int SelectSortPlus(int* arr, int len)
{
	int begin = 0;
	int end = len - 1;
	for (int i = begin; i <=end-1; i++)
	{
		int min = begin;
		int max = begin;
		for (int j = i+1; j <= end; j++)
		{
			if (arr[j] < arr[min])
				min = j;
			if (arr[j] > arr[max])
				max = j;
		}
		Swap(&arr[begin], &arr[min]);
		if (begin == max)//注意这里当begin与max的下标一样的时候,会被先换导致bug
			max = min;
		Swap(&arr[end], &arr[max]);
		begin++;
		end--;
	}
}

三.插入排序

看动图可以很容易的理解插入排序就是将已排好的序的后一个与前面的进行比较,比它大或小的往后移动

void InsertSort(int* a, int len)
{
	for (int i = 0; i < len - 1; i++)
	{
		int end = i;
		int temp = a[end + 1];
		while (end >= 0)
		{
			if (temp < a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
			a[end + 1] = temp;
		}
	}
}

进阶排序(递归实现)

一.快排hoare排序

快排有着多种实现方式我们下面这个是hoare(创始人)的排序方式

快速排序是一种高效的排序现在来让我们来实现一下

1.单趟排序

想要写出一个排序首先我们要去理解这个排序的单趟 单趟如图所示

如图我们可以发现它的步骤如下

快排步凑

(1)选出基准值key 为 left

(2)右边r先走找到比key小的停止

(3)右边r找到的情况下,左边L再开始找比key大的值

(3)左边L找到的情况下停止,将这两个值进行交换

循环上面的操作

直到他们相遇,将相遇的位置的值与key值交换

这就是快排的单趟排序,接下来让我们来实现一下

void QuickSort2(int* arr, int left, int right)
{
		int key = left;
		int begin = left;
		int end = right;
		while (begin < end)
		{
			//先从右边开始找小 //注意结束条件 begin一定<end
			while (begin < end && arr[end] >= arr[key])
			{
				--end;
			}
			//再从左边找大
			while (begin < end && arr[begin] <= arr[key])
			{
				++begin;
			}
			//两边都找到了之后进行交换
			Swap(&arr[begin], &arr[end]);
		}
		//最后相遇再与key交换
		Swap(&arr[begin], &arr[key]);
	}
}

想必这里大家会有一些疑问,为什么

1.为什么要右边先走,左边先走可以吗

2.为什么最后交换key的位置就固定了

3.要怎么样才能实现排序的效果

循环的实现,既然单趟可以固定住key值在整个数里面的想要排序的位置,那我们可不可以将这个数组进行分割[left~key-1]key[key+1~right]

运用递归来实现呢

答案是肯定的

只需要每次递归进行分割,固定n的值的位置,如下图所示

如图所示很明显当我们进行递归的时候每次的位置都将被固定,从而实现了排序

代码如下

void QuickSort2(int* arr, int left, int right)
{
	//返回条件
	if (left >= right)
		return;
		int key = left;
		int begin = left;
		int end = right;
		while (begin < end)
		{
			//先从右边开始找小 //注意结束条件 begin一定<end
			while (begin < end && arr[end] >= arr[key])
			{
				--end;
			}
			//再从左边找大
			while (begin < end && arr[begin] <= arr[key])
			{
				++begin;
			}
			//两边都找到了之后进行交换
			Swap(&arr[begin], &arr[end]);
		}
		//最后相遇再与key交换
		Swap(&arr[begin], &arr[key]);
		//递归排序分割成两份
		//[left~key-1] key [key+1~right]最后相遇的指针也是一样的
		QuickSort2(arr, left, end - 1);
		QuickSort2(arr, end + 1, right);
}

到这里我们也就完成了阉割版的快排,但是距离真正的快排还是有些距离

现在的这个排序有着致命的缺陷如果说在数组已经是有些的情况下,快排的将会退化,就像是二叉树退化为单叉树一样,如果我们这时还去递归那就会有爆栈(栈溢出)的风险,原因很简单

如下图所示

如果是有序的情况下,那么递归的深度将会变成n如果数据量太大将会爆栈

所以接下来要去实现一下三数取中,小区间优化来对递归快排进行优化

快排的优化

(1)三数取中

选择key值进行,key值的选择就是为了避免这种有序情况的出现,因为选key固定key的位值,我们只需要找到中间的那个数进行固定区间递归的高度将会变为\log n解决了爆栈的风险

int GetMid2(int* arr, int left, int right)
{
	//三个数进行比较 分类讨论
	int mid = (left + right) / 2;
	if (arr[left] < arr[mid])
	{
		if (arr[mid] < arr[right])
		{
			return mid;
		}//arr[mid]>arr[right]
		else if (arr[right] < arr[left])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else//arr[left]> arr[mid]
	{
		if (arr[mid] > arr[right])
		{
			return mid;
		}//arr[righ]>arr[mid]
		else if (arr[right]>arr[left])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}
(2)小区间优化

什么是小区间优化?在我们进行快排的时候,如果每次的区间都能二分的化,这个递归的过程是可以看出一颗二叉树,而在满二叉树的叶子节点个数为整棵树的一半,对于快排来说它的最后一层和倒数第二层,是不用去排和只排一个数的,但是却还要开辟栈帧,所以我们这里使用小区间优化带代码如下直接使用当区间小于10时进行插入排序

//小区间优化 提升效率节省空间
if ((right - left + 1) < 10)//减少递归次数
{
	//加上偏移量left
	InsertSort(arr+left, right - left + 1);
}
else
{
    //进行递归
}

注意事项

二.前后指针法(递归实现)

由于hoare版本的有些复杂要去考虑什么右边先走之类的,所以又有人想出了更加简单跟容易理解的办法,前后指针法,过程如图所示

可以发现与hoare版本大体一致都是去选择key与key比较,不同点在于,只有是cur去找比key小的值,当找到比key小的值的时候++prev然后与cur位置的值进行交换,最后当cur走到最后,prev的值再与key位置的值进行交换,比起hoare版本简单了许多,接下来我们来尝试实现一下

void QuickSortByPointer(int* arr, int left, int right)
{
	if (left >= right)
		return;
	//三数取中
	int mid = GitMid(arr,left,right);
	Swap(&arr[mid], &arr[left]);
	int key = left;
	int prev = left;
	int cur = prev+1;
	//三数取中
	if ((right - left + 1) < 10)
	{
		InsertSort(arr+left, right - left + 1);//加上left
	}
	else
	{
		while (cur <= right)
		{
			if (arr[key] > arr[cur]&&++prev != cur)//为什么要写成这样?
				Swap(&arr[prev], &arr[cur]);
			cur++;
		}
		Swap(&arr[prev], &arr[key]);
		//区间变为[0,prev-1]prev[prev+1,right]
		QuickSortByPointer(arr, left, prev - 1);//值给错了应该是left
		QuickSortByPointer(arr, prev + 1, right);
	}
}

你以为到这里快排就结束了嘛其实还是马达马达得是(远远没有结束),虽然我们加上三数取中,与小区间的优化但是如果数据量过大还是会有爆栈的风险(栈的空间比较小),所以我们可以使用数据结构的栈来模拟实现程序中的压栈与出栈,(由于是在堆中建立,内存巨大,8G的内存不可能溢出把!)

三.快排的非递归实现(前后指针法的非递归)

可以看见我们先是将每次的单次排序进行封装的

我们可以想象一下在程序中栈帧的建立与销毁的过程,然后我们也可以自己使用数据结构的栈来实现

快排其实是可以看作二叉树的前序遍历的,但是栈又是后进先出,想要先得到左边界的值就需要先进右边,想要得到右边界的值就需要先进左边

void QuickSortNoR(int* arr, int begin, int end)
{
	Stack st;
	CreatStack(&st);
	StackPush(&st, end);
	StackPush(&st, begin);
	while (StackGetSize(&st)!=0)
	{
		int left = StackPop(&st);//我的Pop是即出又返回栈顶元素的因为后进先出想要先得到left进右
		int right = StackPop(&st);
		//小区间优化
		if ((right - left + 1) / 2 < 10)
			InsertSort(arr + left, right - left + 1);
		else
		{
			//开始模拟递归
			int key = PartPointer(arr, left, right);//这个函数是每一次的单趟排序
			if (key + 1 < right)//进行递归由于后进先出 先进右区间
			{
				StackPush(&st, right);//后进先出由于我们的右区间是后出 所以先进
				StackPush(&st, key + 1);
			}
			if (left < key - 1)//注意错误之处区间不要写错了
			{
				StackPush(&st, key - 1);
				StackPush(&st, left);
			}
		}
	}
}
int PartPointer(int* arr, int left, int right)
{

	//三数取中
	int mid = GitMid(arr, left, right);
	Swap(&arr[mid], &arr[left]);
	int key = left;
	int prev = left;
	int cur = prev + 1;
	while (cur <= right)
	{
		if (arr[key] > arr[cur])
		Swap(&arr[++prev], &arr[cur]);
		cur++;
	}
	Swap(&arr[prev], &arr[key]);
	return prev;//返回key的位置 prev就是key中间值 然后进行区间的分割同上
}

快排的挖坑法的实现

(由于篇幅有限这里不在过多讲解)

int PartSort2(int* a, int begin, int end)
{
	//begin是坑
	int key = a[begin];
	while (begin < end)
	{
		while (begin < end && a[end] >= key)
			--end;

		// end给begin这个坑,end就变成了新的坑。
		a[begin] = a[end];

		while (begin < end && a[begin] <= key)
			++begin;

		// end给begin这个坑,begin就变成了新的坑。
		a[end] = a[begin];
	}

	a[begin] = key;

	return begin;
}

二.堆排序

学习完了快排,接下来学习堆,首先我们要知道堆的概念,

堆在逻辑结构上是一个完全二叉树,在物理结构上是一个数组,

想要找到儿子节点就是(parent-1)/2

想要找到父亲节点就是child*2+1

如果想要深入理解堆可以看我的这一篇博客堆的实现与堆排序(纯C语言版)-CSDN博客

1.建堆的选择


当我们想要进行排序的时候首先要模拟堆的插入过程进行建堆,这里有个问题如果想要降序排列那么应该建小堆还是大堆呢,在我刚开学学习的时候想的是肯定是建大堆啊因为这样根节点就是最大的然后再出堆,其实这样想就错了,这样只是出堆降序,不是数组本身进行了降序排列,所以降序是其实是建小堆,升序其实是建大堆.那又是怎么实现的呢

2.堆排序的实现

在进行建堆之后(小堆降序来举例),我们就只需要模拟出堆,这时每次最小的数就被放在了最后的位置,最后完成排序后,整个数据就有序,如图当我们想要升序排列的时候建大堆

下面是完整的代码

void HeapSort(int* a, int max)//max为最大个数
{
	//建队
	for (int i = 0; i <max; i++)
	{
		AdjustUp(a, i);//模拟插入建小堆
	}
	//排序
	int end = max - 1;//找到最后一个元素的下标进行交换
	while (end>0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, 0, end);
		--end;//最后的有序不在排序
	}
}

其实第一步建堆算法还没有做到极致,还可以倒着向下调整,这样的时间复杂度更低

//建堆法2
for (int i = (max - 1 - 1) / 2; i >= 0; i--)//找到第一个非叶子结点 倒着进行想下调整
{
	AdjustDown(a, i, max-1);
}

二希尔排序

希尔排序是一个时间复杂度大约为O(N^{1.3})的排序算法,

它其实就是运用的插入排序

它的排序可以分为2步

1.预排序分为gap组进行

2.当gap=1时即为选择排序

希尔排序的实质就是如果在排一个升序的数组,如果大的在很前面,每次就是一步一步的移动,而当有了gap之后,移动的步长将会变大,大的数将会以更快的速度移到后面

我们将插入排序来进行一下比较

void InsertSort(int* a, int len)
{
	for (int i = 0; i < len - 1; i++)
	{
		int end = i;
		int temp = a[end + 1];
		while (end >= 0)
		{
			if (temp < a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
			a[end + 1] = temp;
		}
	}
}

可以看见在进行插入排序的时候,此时的步长gap为1,每次只会往后面进行一步,所以我们这里只需去改变想要排序的步长即可

下面是代码的实现

void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		// +1保证最后一个gap一定是1
		// gap > 1时是预排序
		// gap == 1时是插入排序
		gap = gap / 3 + 1;

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

我们可以发现,我们上面是一组一组来排序

也可以多组并走都是一样的

三.归并排序(递归实现与非递归的实现)

归并排序的思想就是分治法(分而治之),如图所示

首先我们要创建一个临时的数组

运用了二叉树的后序遍历的思维,先将数组拆分,拆分后的数组又来进行合并,在进行合并的两个数组分别有序,只需要比较一次将小的放入到临时的数组当中,放完成后再拷贝回去完成排序

重点就是在进行合并的时候两个数组是有序的!

让我们来实现一下

l

999000lkklkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkklkkkkkkkkkkkkkkkkkkkkkkkk                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          222

代码如下

void MergeSort(int* arr, int len)
{
	int* temp = (int*)malloc(sizeof(int) * len);
	_MergeSort(arr,temp,0,len-1);
	free(temp);
	temp = NULL;
}
void _MergeSort(int* arr, int* temp, int left, int right)
{
	//返回条件
	if (left >= right)
		return;
	//进行递归
	
	//分成[left mid][mid+1,right]不能写成[left mid-1][mid,right]分区间的时候将会出现问题
	//单趟排序 将左右区间看作有序数组 进行比较放入temp数组中
	int mid = (left + right) / 2;
	//[left mid][mid+1,right]
	int begin1 = left;
	int begin2 = mid + 1;
	int end1 = mid;
	int end2 = right;
	_MergeSort(arr, temp, begin1, end1);//左区间
	_MergeSort(arr, temp, begin2, end2);//右区间
	int i = 0;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] < arr[begin2])
		{
			temp[i++] = arr[begin1++];
		}
		else//直接else
		{
			temp[i++] = arr[begin2++];
		}
	}
	//循环结束后还有元素全部放后面
		while (begin1 <= end1)
		{
			temp[i++] = arr[begin1++];
		}
	//循环结束后还有元素全部放后面
		while (begin2 <= end2)
		{
			temp[i++] = arr[begin2++];
		}
	//进行拷贝回去
	memcpy(arr+left, temp, i*sizeof(int));
}

归并排序(非递归实现)

想要实现归并的非递归,我们是否还需要像快排一样去模拟栈呢,当我们取模拟栈的时候由于归并的递归是一个后序遍历,而栈无法去记录值,所以使用栈就要用两个,较为麻烦,使用我们直接用下面这种思想

由上面递归实现的归并排序很容易想,其中的gap为每个小组的个数

但是好像还有一个问题,数组越界的问题

当我们使用了上面的数据进行分组的时候,所以我们要进行区间的判断

加入

if (begin2 > len - 1)//begin2已经越界,说明只有一组了没必要再排
{
	break;
}
if (end2 > len - 1)//end2越界了进行修正即可
{
	end2 = len - 1;
}

完整的代码如下

void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}

	// gap每组归并数据的数据个数
	int gap = 1;
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2 * gap)
		{
			// [begin1, end1][begin2, end2]
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;

			//printf("[%d,%d][%d,%d] ", begin1, end1, begin2, end2);

			// 第二组都越界不存在,这一组就不需要归并
			if (begin2 >= n)
				break;

			// 第二的组begin2没越界,end2越界了,需要修正一下,继续归并
			if (end2 >= n)
				end2 = n - 1;

			int j = i;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] <= a[begin2])//注意等号这样才会稳定
				{
					tmp[j++] = a[begin1++];
				}
				else
				{
					tmp[j++] = a[begin2++];
				}	
			}

			while (begin1 <= end1)
			{
				tmp[j++] = a[begin1++];
			}

			while (begin2 <= end2)
			{
				tmp[j++] = a[begin2++];
			}
			memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
		}
		//memcpy(a , tmp , sizeof(int) *n );

		//printf("\n");

		gap *= 2;
	}

	free(tmp);
	tmp = NULL;
}

四.非比较排序(计数排序)

接下来让我们来学习最后一个排序,这个排序的特点是非比较的排序,通过建立一个数组来存放数组中每个数出现的次数,来实现排序

首先来思考我们想要开辟的数组的大小,那是否就是原数组的长度大小呢,因为要存储每个元素出现的次数,那么我们开辟数组必须是连续的,在开辟数组长度大小的时候有个细节,如果每次都从0开始建立计数数组,那如果遇到一个最小值为99,最大值为110的数组,那我们还是需要从0开始建立数组,前面明明一个数都没有出现但是我们却还是去开辟的数组,浪费了很多的空间,所以我们只需要去找到最大与最小的那个值,计算出rang=最大值-最小值+1(注意要加一),所以计数数数组的大小为rang,那我们在进行计数的时候就只需要进行-min就可以了

然后是进行排序,当计数数组里不为0说明当前位置有映射值进行自减1.加上min赋值给原数组实现排序效果

代码如下

void CountSort2(int* arr, int len)
{
	//找到原数组的最大与最小值
	int min = arr[0];
	int max = arr[len - 1];
	for (int i = 0; i < len; i++)
	{
		if (arr[i] < min)
		{
			min = arr[i];
		}
		if (arr[i] > max)
		{
			max = arr[i];
		}
	}
	int rang = max - min + 1;
	//开辟计数数组 注意这里要初始化开辟的计数数组 这样奇计数数组才全是0
	int* count = (int*)calloc(rang,sizeof(int) * rang);
	//进行计数
	for (int i = 0; i < len; i++)
	{
		count[arr[i] - min]++;
	}
	//进行排序
	int j = 0;
	for (int i = 0; i < rang; i++)
	{
		while (count[i]--)//当count[i]的元素不为0的时候说明当前映射有值
		{
			arr[j++] = i + min;
		}
	}


}

计数排序的缺陷

既然计数排序是一种映射的方法,所以是只能对整数进行排列的

五.排序总结

学习完了上面的排序现在我们来进行一下总结,

排序         平局时间复杂度    最坏时间复杂度 最好时间复杂度 稳定性

冒泡排序                O(N^{2})                  O(N^{2})       O(N^{})                稳定 

选择排序                O(N^{2})                 O(N^{2})        O(N^{2})               不稳定

插入排序                O(N^{2})                 O(N^{2})        O(N^{})                稳定

希尔排序                O(N^{1.3})              O(N^{2})        O(N^{1.3})             不稳定

堆排序                    O(N*\log N)  O(N*\log N)O(N*\log N) 不稳定

快速排序                O(N*\log N)   O(N^{2})         O(N*\log N)       不稳定

归并排序                 O(N*\log N)    O(N*\log N)   O(N*\log N) 稳定

 

稳定性的概念

上表的稳定性是什么意思?其实就是相同数据的前后位置是否发生改变,如下面红色5与蓝色5当排序完成后红色5还在蓝色5前面就是稳定的

六,排序的选择题练习与巩固

学完上面的知识,不来两道题检测一下是不知道自己真正掌握了没有的下面让我们来做几道题加深一下印象。

1.用某种排序方法对关键字序列 25 84 21 47 15 27 68 35 20 进行排序,序列的变化情况采样如下:

20 15 21 25 47 27 68 35 84

15 20 21 25 35 27 47 68 84

15 20 21 25 27 35 47 68 84

请问采用的是以下哪种排序算法( )

A.选择排序

B.希尔排序

C.归并排序

D.快速排序

答案:D

解析:

此题中的排序是快排二分排序的思想,第一趟的基准值是25,第二趟的基准值分别是20,47,第三趟的基准值分别是15,21,35,68

 

2.下面的排序算法中,初始数据集的排列顺序对算法的性能无影响的有( )

① 快速排序

② 希尔排序

③ 插入排序

④ 堆排序

⑤ 归并排序

⑥ 选择排序

A.①④⑤

B.④⑤⑥

C.②③⑥

D.②③⑤⑥

答案:B

解析:

快排: 初始顺序影响较大,有序是,性能最差

插入: 接近有序,性能最好

希尔:希尔是对插入排序的优化,这种优化是在无序的序列中才有明显的效果,如果序列接近有序,反而是插入最优。

堆排,归并,选择对初始顺序不敏感

3.下列排序方法中,每一趟排序结束时都至少能够确定一个元素最终位置的方法是( )

① 选择排序

② 归并排序

③ 快速排序

④ 堆排序

A.①④

B.①②④

C.①③④

D.①②③④

 

答案:C

解析:

选择排序每次选一个最值,放在最终的位置

快速排序每次基准值的位置也可以确定

堆排序每次堆顶元素的位置也可以确定

所以这三种方法都可以每次至少确定一个元素的位置

而归并排序每次都需要对n个元素重新确定位置,所以不能保证每次都能确定一个元素位置,有可能每次排序所有元素的位置都为发生变化。

 

4.现有数字序列 5 11 7 2 3 17,目前要通过堆排序进行降序排序,那么由该序列建立的初始堆应为( )

A.2 3 7 11 5 17

B.17 11 7 2 3 5

C.17 11 7 5 3 2

D.2 3 5 7 11 17

答案:A

解析:

要降序排列,所以要建小堆,每次把堆顶元素放在当前堆的最后一个位置

建堆要进行向下调整算法(从最后一个非叶子节点开始进行向下调整算法,直到根元素)

5

11 7

2 3 17

5

2 7

11 3 17

2

3 7

11 5 17

所以初始堆序列为: 2 3 7 11 5 17

5.下列选项中,不可能是快速排序第2趟排序后的结果的是( )

A.2 3 5 4 6 7 9

B.2 7 5 6 4 3 9

C.3 2 5 4 7 6 9

D.4 2 3 5 7 6 9

 

答案:C

解析:

这里说的是快排的第二趟,即在第一趟快排的结果的基础上进行的,如果已经经过了一趟排序,则会通过第一趟选择的基准值划分两个子区间,每个子区间也会以区间内选择的基准值划分成两部分。

A: 第一趟的基准值可以为2, 第二趟的基准值可以为3

B: 第一趟的基准值可以为2, 第二趟的基准值可以为9

C: 第一趟的基准值只能是9,但是第二趟的基准值就找不出来,没有符合要求的值作为基准值,所以不可能是一个中间结果。

D: 第一趟的基准值可以为9, 第二趟的基准值可以为5

由于个人精力有限,如有错误欢迎指出!!!

小bit!!!

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

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

相关文章

计算机网络 ——网络层(IPv4地址)

计算机网络 ——网络层&#xff08;IPv4地址&#xff09; 什么是IPv4地址IP地址的分类特殊的IP地址 查看自己的IPv4地址 我们今天来看IPv4地址&#xff1a; 什么是IPv4地址 IPv4&#xff08;Internet Protocol version 4&#xff09;是第四版互联网协议&#xff0c;是第一个被…

欢乐钓鱼大师辅助:哪家云手机自动钓鱼更好操作!

在探索《欢乐钓鱼大师》的世界时&#xff0c;我们不得不提到一个强大的游戏辅助工具——VMOS云手机。通过VMOS云手机&#xff0c;你可以轻松实现自动钓鱼&#xff0c;让游戏体验更加便捷高效。 什么是VMOS云手机&#xff1f; VMOS云手机是一款基于虚拟机技术的云端工具&#…

AMPL下载安装于基本使用(二)

1 带有下标的优化模型 优化问题大部分情况下&#xff0c;参数有很多&#xff0c;约束也有很多&#xff0c;但大部分参数和约束都是同类型的&#xff0c;在数学表达式中往往都以下标来区分&#xff0c;例如《运筹学》&#xff08;罗纳德 L. 拉丁&#xff09;中的Pi Hybrids问题…

【postgresql初级使用】视图上的触发器instead of,替代计划的rewrite,实现不一样的审计日志

instead of 触发器 ​专栏内容&#xff1a; postgresql使用入门基础手写数据库toadb并发编程 个人主页&#xff1a;我的主页 管理社区&#xff1a;开源数据库 座右铭&#xff1a;天行健&#xff0c;君子以自强不息&#xff1b;地势坤&#xff0c;君子以厚德载物. 文章目录 inst…

Linux宝塔部署数据库连接问题

博主在部署项目时发现网页可以成功部署&#xff0c;但是登录界面一直登录不进去推测是数据库连接问题。 博主当时在IDEA中写的是用户名为root 密码123456 但是在宝塔中因为自己是跟着教程学的所以就顺手把用户名和密码都改了&#xff0c;于是java中的配置和数据库配置连接不上…

C++第二十五弹---从零开始模拟STL中的list(下)

✨个人主页&#xff1a; 熬夜学编程的小林 &#x1f497;系列专栏&#xff1a; 【C语言详解】 【数据结构详解】【C详解】 目录 1、函数补充 2、迭代器完善 3、const迭代器 总结 1、函数补充 拷贝构造 思路&#xff1a; 先构造一个头结点&#xff0c;然后将 lt 类中的元…

深入探索:十种流行的深度神经网络及其运作原理

算法 深入探索&#xff1a;十种流行的深度神经网络及其运作原理一、卷积神经网络&#xff08;CNN&#xff09;基本原理工作方式 二、循环神经网络&#xff08;RNN&#xff09;基本原理工作方式 三、长短期记忆网络&#xff08;LSTM&#xff09;基本原理工作方式 四、门控循环单…

.net core 使用js,.net core 使用javascript,在.net core项目中怎么使用javascript

.net core 使用js&#xff0c;.net core 使用javascript&#xff0c;在.net core项目中怎么使用javascript 我项目里需要用到“文字编码”&#xff0c;为了保证前端和后端的编码解码不处bug, 所以&#xff0c;我在项目中用了这个 下面推荐之前在.net F4.0时的方法 文章一&#…

js--hasOwnProperty()讲解与使用

@TOC 前言 hasOwnProperty(propertyName)方法 是用来检测属性是否为对象的自有属性 object.hasOwnProperty(propertyName) // true/false 讲解 hasOwnProperty() 方法是 Object 的原型方法(也称实例方法),它定义在 Object.prototype 对象之上,所有 Object 的实例对象都会继…

下载中心表设计

文件表 有哪些文件需要异步生成 文件夹表 添加文件夹功能时使用 权限表 文件权限绑定 对用户来说&#xff0c;下载文件和配置下载管理是两个可直接交互的功能。下载文件包括&#xff1a; 1&#xff09;添加下载任务&#xff08;手动开始&#xff09;。 2&#xff09;开始…

安卓约束性布局学习

据说这个布局是为了解决各种布局过度前套导致代码复杂的问题的。 我想按照自己想实现的各种效果来逐步学习&#xff0c;那么直接拿微信主页来练手&#xff0c;用约束性布局实现微信首页吧。 先上图 先实现顶部搜索框加号按钮 先实现 在布局中添加一个组件&#xff0c;然后摆放…

Java学习54-关键字this的使用

this是什么 this的作用&#xff1a; 它在方法(准确的说是实例方法或非static的方法)内部使用&#xff0c;表示调用该方法的对象 它在构造器内部使用&#xff0c;表示该构造器正在初始化的对象 this可以调用的结构&#xff1a;成员变量、方法和构造器 什么时候使用this 实…

安徽代理记账公司的专业服务和创新理念

在当今竞争激烈的市场环境中&#xff0c;为了提升企业的运营效率&#xff0c;许多企业开始寻找专业的代理记账公司进行财务管理和记账&#xff0c;本文将介绍一家名为安徽代理记账公司的专业服务和创新理念。 安徽代理记账公司是一家专注于为企业提供全方位会计服务的公司&…

[ 网络通信基础 ]——网络的传输介质(双绞线,光纤,标准,线序)

&#x1f3e1;作者主页&#xff1a;点击&#xff01; &#x1f916;网络通信基础TCP/IP专栏&#xff1a;点击&#xff01; ⏰️创作时间&#xff1a;2024年6月8日14点23分 &#x1f004;️文章质量&#xff1a;94分 前言—— 在现代通信网络中&#xff0c;传输介质是数据传…

江西代理记账公司的专业服务和优质品质

作为一家专业的代理记账公司&#xff0c;我们始终以“专业、公正、公平”为宗旨&#xff0c;为客户提供全方位的会计咨询服务&#xff0c;我们的服务内容包括但不限于以下几点&#xff1a; 1、代理记账服务&#xff1a;我们拥有丰富的经验和专业知识&#xff0c;能够为企业提供…

【ARM Cache 系列文章 1.2 -- Data Cache 和 Unified Cache 的详细介绍】

请阅读【ARM Cache 及 MMU/MPU 系列文章专栏导读】 及【嵌入式开发学习必备专栏】 文章目录 Data Cache and Unified Cache数据缓存 (Data Cache)统一缓存 (Unified Cache)数据缓存与统一缓存的比较小结 Data Cache and Unified Cache 在 ARM架构中&#xff0c;缓存&#xff08…

一次改SQLMAP的操作

前言 sqlmap这个工具&#xff0c;相信各位大佬们都不陌生&#xff0c;但sqlmap虽好&#xff0c;也时常会有些实际存在但无法注入的地方&#xff0c;这时候就需要我们改它的配置了&#xff0c;今天就以本人遇到的事件进行阐述。 正文 确认注入点 通过一系列测试最终确定这里…

论文高级图表绘制(Python语言,局部放大图)

本文将通过一个具体的示例,展示如何使用Python语言和Matplotlib库来绘制高级图表,包括局部放大图的制作。适用于多条曲线绘制在同一个图表中,但由于数据量过大,导致曲线的细节看不清,需要对细节进行局部放大。如下图: 环境准备 首先,确保你的Python环境中已经安装了以…

PHP超详细安装及应用

目录 所需安装包如下 一、PHP安装 依赖包安装 安装扩展工具&#xff08;先将PHP所需的软件包全部拖进centos根目录下&#xff09; 安装libmcrypt 安装mhash 安装mcrypt 安装PHP 二、设置LAMP组件环境&#xff08;要保证mysql、http都安装完成了&#xff09; Php.ini的建…

附录二-nmap基本用法

参考 黑客工具—Nmap的使用_哔哩哔哩_bilibili nmap是扫描IP和端口的&#xff0c;相当于攻击前的索敌步骤。不止网络安全方面会用到&#xff0c;平时运维的时候也会用到nmap 1 下载nmap nmap官网 https://nmap.org/ 点击下载&#xff0c;然后点你用的平台就行了 往下滚可以…