快排&超详细,Leetcode排序数组题目带你升华掌握

这篇具有很好参考价值的文章主要介绍了快排&超详细,Leetcode排序数组题目带你升华掌握。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

快排&超详细,Leetcode排序数组题目带你升华掌握,数据结构,leetcode,算法,数据结构,排序算法,推荐算法

大家好,这里是Dark FalmeMater。
这篇文章我将超级仔细地讲解快速排序,快排之所以叫快排,到底有多快,为什么这么快,还有快速排序的优化和改进,通过这篇文章你一定会对快排有进一步的掌握。

快排的历史及介绍
快速排序由C. A. R. Hoare在1962年提出。

它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归 进行,以此达到整个数据变成有序序列。

 其中Hoare大佬写的版本由于没有那么容易理解且容易出现错误,在后人的智慧下,进行了小小的改变,分化出了挖坑法和双指针法。我们逐个进行讲解。

Hoare版

快排&超详细,Leetcode排序数组题目带你升华掌握,数据结构,leetcode,算法,数据结构,排序算法,推荐算法
递归函数分析思路如下
在数组中选定一个关键的点,最右边或者最右边都可以。

我们选择最左边进行讲解,找到关键位置后设置left和rght然后分别从数组左边和最右边开始遍历,右边先行,找到小于key位置的值就停下了,左边的找大于key位置的值,找到后就互换,直到左下标和右下标相遇,相遇的时候说明左边已经没有大于key位置的值了,右边没有小于key位置的值了,交换相遇位置的值和key位置的值,就可以将该组数分割成以key位置的值分割的两组数。

有了思路我们可以写出以下的代码:

//hoare版本
int PartSort1(int* a, int left, int right)
{
	int key = a[left];//设置关键点
	while (left < right)
	{
		while (a[right] > a[keyi])//从最右边开始找到大于关键点的坐标
		{
			--right;
		}
		//找大
		while (a[left] < a[keyi])//从左边开始找到小于key的坐标
		{
			++left;
		}
		Swap(&a[left], &a[right]);//交换
	}
	Swap(key, &a[left]);//当left相遇,就交换关键点和相遇点的值
	return left;返回相遇点的坐标
}

Hoare版解答疑惑及易错点指出:

  1. key的选择

 之所以选择最左边的位置设置key,是因为利用这个值在写代码和进行判断时更方便一些,利用right位置的值当做key当然也可以,如果用递归函数传参数组的第二个元素做key,在递归到每个小区间只有一个数时就会出现错误,因为没有key。

  1. 相遇节点为什么可以和key位置的互换呢?为什么相遇点的数值一定会比key位置的值小呢?

大家可以思考一下…

这就要看左右指针谁先行了,如动图所示
快排&超详细,Leetcode排序数组题目带你升华掌握,数据结构,leetcode,算法,数据结构,排序算法,推荐算法
如果是right先行,会发生什么呢?其实除了最后left和right相遇,其他的都是一样,如果是right先行的话。
快排&超详细,Leetcode排序数组题目带你升华掌握,数据结构,leetcode,算法,数据结构,排序算法,推荐算法
在循环判断中右边先行是一定要注意的。


还有吗?
还有呢。
判断条件怎么写呢?判断条件是大于交换还是大于等于(相对left而言)交换呢?如果是left位置的值大于key的话,就交换有可能会发生森么情况呢?
快排&超详细,Leetcode排序数组题目带你升华掌握,数据结构,leetcode,算法,数据结构,排序算法,推荐算法
 看这个图,在交换了组边的6和右边的2之后,right开始–,因为判断条件是a[right]>key,所以当right找到5时,5=key,right就跳出了循环。同理,因为不满足left下标的值小于key,left跳出循环,交换以left为下标和以right为下标的值,交换的还是5和5,再次循环,判断left<right成立,继续循环,left和right还在原来的位置,继续交换,就会陷入死循环,所以这里的判断条件要写为a[left]>=key,a[right]<=key,然后再进行交换。
看动图
快排&超详细,Leetcode排序数组题目带你升华掌握,数据结构,leetcode,算法,数据结构,排序算法,推荐算法
判断条件也要注意,这种情况很难想到,所以有时运行错误不知道问题出在哪里
更改上边问题,将判断条件改为a[right] >= key和a[left] <= a[keyi]


 思考了这么多,终于找到相遇的点后交换key和a[left](a[left]都可以),就可以将这个数组分为两个大小不同的的区间啦!
真的吗?
 前边初始化key=a[left],交换key和遍历后的a[left],然而a[0]并没有和找到的值进行交换,而是key这个数和找到的相遇点交换,这个时候a[left]就没有改变为相遇点找到的小于key的值,如果一直递归下去,会变成什么样呢?(上边动图部分,key改成a[left]

再来看排序该组数据
快排&超详细,Leetcode排序数组题目带你升华掌握,数据结构,leetcode,算法,数据结构,排序算法,推荐算法
如果是创建的key和找到的点进行交换,就会出现数据污染,好多数据都被更改了,这样的排序一定是错误的,所以初始化条件可以这样。

int keyi=left;
int key=a[keyi]

在判断时利用key,在交换时交换a[keyi]和a[left]即可。


终于结束啦,然而并没有。
要注意的是在right和left找的过程中left也不能小于right,比如该数组是有序的,在排序的过程中,right先行,但是一直没有找到小于a[keyi]的值,直到到达left的位置再次减一,就会越界访问。
完整代码如下

//hoare版本
int PartSort1(int* a, int left, int right)
{
	//int midi=GetMidi(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;
}

是不是细节满满,一不小心就会出来好多bug。


挖坑法

同样先看图
快排&超详细,Leetcode排序数组题目带你升华掌握,数据结构,leetcode,算法,数据结构,排序算法,推荐算法
挖坑法相较于Hoare大佬的方法,步骤更加清晰明了一点,一步一步实现

上边的动图表现得十分清晰,设置一个坑位,保存left位置的值,设置hole变量等于left,然后从右边找小于a[keyi]即上图key的值,填入坑中,这时将找到的值的位置right设置为坑,然后从左往右找大于a[keyi]的值填入hole,将left所在位置设置为hole,不断循环,直到left等于right,将之前保存的key,即a[keyi]填进坑里,就完成了前边相同的操作。

代码如下,很容易理解

//挖坑法
int PartSort2(int* a, int left, int right)
{
	int key = a[left];
	//保存key值以后。左边形成一个坑
	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;
}

最后返回right,left,hole都可以,反正最后他们在同一个位置上。


双指针法

快排&超详细,Leetcode排序数组题目带你升华掌握,数据结构,leetcode,算法,数据结构,排序算法,推荐算法
看几遍动图,不管他们用什么方法进行实现,最终实现的效果都是相同的。双指针法只要懂得了原理,还是很容易实现的。
双指针法和前边两种方法略有不同,来体验一下。先看代码后进行讲解

//前后指针法
int PartSort3(int* a, int left, int right)
{
	int midi = GetMidi(a, left, right);
	Swap(&a[left], &a[midi]);

	int prev = left;
	int cur = prev + 1;

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

还是一样选择left位置的值作为key,设置两个指针,一个指向数组最前边的位置,一个在他的后边,前后指针法因此得名。
具体思路:

 设置前后指针,后边的指针只要不越界访问,cur就一直往后走,如果prev的下一个位置不是cur,且cur找到小于key的值时,就交换prev位置和cur位置的值。直到最后cur大于right结束循环。此时prev位置的值一定小于或等于key,因为cur在后边查找的过程中最不济的情况也就是一个也没找到,prev和他自己换,照样也不变,在找到第一个之前cur和prev一直一起移动并一直在cur的后一位,当cur找到大于key位置的坐标后,prev不动,cur继续移动,所以当cur找到小于key的位置时,prev的下一个位置一定是大于key的,可以放心交换。
直到最后cur走到数组尽头,就如前边所说,prev的下一位一定大于key,而prev位置的值一定小于等于key,交换a[prev]和a[keyi]的值,就可以将数组分成以prev位置为中心的两组,左边的值都小于等于key,右边的值都大于key。

循环有一种更简单的方法表示,效果相同

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

&&操作符,当前一条件为假,后一条件就不走,如果前一条件为真后,才会走后一条件,然后prev才会++,与上边实现的效果相同。


递归函数

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

begin和end是传进来的数组段的第一个位置和最后一个位置的下标。要注意接下来的递归数组的区间还有结束判断条件。
举一个例子说明递归流程。
快排&超详细,Leetcode排序数组题目带你升华掌握,数据结构,leetcode,算法,数据结构,排序算法,推荐算法

递归结束后,数组就变为有序的了。至于先往右递归还是先往左都可以,没有区别。
上边递归时用的Hoare大佬的版本,用挖坑法和双指针法也都可以。

时间复杂度与空间复杂度

快排的时间复杂度为O(nlogN),空间复杂度为O(N),如果情况比较好的话为O(log2n),空间是可以复用的,一边用完另一边还可以用。
时间复杂度最坏的情况是若该数组为有序数组。最好情况就是一直取到中间位置。
最坏情况:
快排&超详细,Leetcode排序数组题目带你升华掌握,数据结构,leetcode,算法,数据结构,排序算法,推荐算法
若数组数量为n,一次只排好了一个数据,right第一次跑n次,第二次跑n-1次,则时间复杂度明显为O(n^2)。
假使每次都能找到中间值,此时时间复杂度最低。2^h=n,所以n=log2 ^n。
快排&超详细,Leetcode排序数组题目带你升华掌握,数据结构,leetcode,算法,数据结构,排序算法,推荐算法
最好情况时间复杂度为O(n
logn)。
至于空间复杂度从上边的图就可以看出,因为递归开辟的空间是在栈上的,每次开辟的空间都可知小于n,故每次递归开辟空间为O(1),所以快排的时间复杂度为递归深度乘于O(1),最坏情况为O(N),最好的情况为O(logN)。

优化

借助题目:排序数组
快排&超详细,Leetcode排序数组题目带你升华掌握,数据结构,leetcode,算法,数据结构,排序算法,推荐算法
给一个数组,要求给他排序,要求很简单,却只有50%的通过率,力扣标记简单不一定简单,标记中等那一定是有点难。
这题很显然,普通的排序比如冒泡排序,插入排序,选择排序是过不了的,我们刚刚学习了快排,何不尝试一波。

void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}

 void QuickSort1(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	int keyi = PartSort1(a, begin, end);
	QuickSort1(a, begin, keyi - 1);
	QuickSort1(a, keyi + 1, end);
}
//hoare版本
int PartSort1(int* a, int left, int right)
{
	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;
}
int* sortArray(int* nums, int numsSize, int* returnSize){
    QuickSort1(nums, 0, numsSize-1);
    *returnSize=numsSize;
    
    return nums;
}

快排解题的代码如下
然而却发现
快排&超详细,Leetcode排序数组题目带你升华掌握,数据结构,leetcode,算法,数据结构,排序算法,推荐算法
 用hoare大佬的方法走一遍,发现时间复杂度在这组用例上为O(N^2),right一直向右移,不会分成左右两组,一直递归n次,right向前的次数从n到1,这样的话花费的时间太多了,针对这种情况进行优化,就要介绍三数取中。

三数取中

如何防止上面最坏的情况发生?
只需要防止最左边的数为该组数里最小的数即可。

 可以找出left位置的值和right位置的值及(left+right)/2数组中间下标的值,找出他们三个中间大小的一个,与a[left]进行交换,这样就可以防止left是数组中最小的元素这种情况的发生。

将三数取中抽离成函数

//三数取中
int GetMidi(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	//left mid right
	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[left] > a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}

在每次partsort前搞来中间值的坐标,与left进行交换

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

加上三数取中再次运行
然而。。。。
快排&超详细,Leetcode排序数组题目带你升华掌握,数据结构,leetcode,算法,数据结构,排序算法,推荐算法
 再次出乎意料,如果是全部数字都一样或者有大量重复数据,right还是像刚才有序数组的情况一样,right一直向左,时间复杂度为O(N^2),此时三数取中也没用了,无论怎么取,取到的都是2。针对这种情况怎么办?

三路分化

将hoare大佬的方法和双指针法结合起来,将数组分为三个部分,左边小于key,中间的区段是等于key的,右边的部分是大于key的。
设置三个指针,两个指针用于位置的交换是数组划分为三个区间,一个指针用于遍历。
看思路
快排&超详细,Leetcode排序数组题目带你升华掌握,数据结构,leetcode,算法,数据结构,排序算法,推荐算法
最后在left和right之间的部分就是等于5的部分,left之前皆小于key,right之后皆大于key。
总结下来只有以下三种情况

  1. cur的值小于key,交换cur的值和left的值,cur++,left++。
  2. cur的值等于key,直接++cur
  3. cur的值大于key,交换cur和right的值,cur不能动。

代码实现

void QuickSort1(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int begin = left;//记录左右边界
	int end = right;
	int midi = GetMidi(a, left, right);
	Swap(&a[left], &a[midi]);

	int key = a[left];
	int cur = left + 1;
	while (cur <= right)
	{
		if (a[cur] < key)//重点理解
		{
			Swap(&a[cur], &a[left]);
			++left;
			++cur;
		}
		else if (a[cur] > key)
		{
			Swap(&a[cur], &a[right]);
		}
		else
		{
			++cur;
		}
	}
	QuickSort1(a, begin, left-1);
	QuickSort1(a, right+1, end);
}

这次我们信心满满,如果数组的元素全部为2的话,遍历一遍,right和left直接相遇,甚至只需要O(N)的时间就可以完成。
更改代码后运行。
快排&超详细,Leetcode排序数组题目带你升华掌握,数据结构,leetcode,算法,数据结构,排序算法,推荐算法
 还是超出时间限制,这又是为什么呢?这道题对快速排序做了针对性的处理,普通的快排很难过这道题,他会检测我们的三数取中,然后搞出对应的一串数字,让每次取出的数都是数组中倒数第二大,这样的话时间复杂度还是很大。
解决方法:

 选取数组中任意位置的数和left位置和right作比较选出keyi,而不是一直取中间坐标与他们相比较,用rand函数进行操作,使我们选数位置没有规律可循,这样编译器就不能根据我们所写的代码搞出针对性用例。

代码如下:

int GetMidi(int* a, int left, int right)
{
	//int mid = (left + right) / 2;
	int mid =left+(rand()%(right-left));
	//left mid right
	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[left] > a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}

void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}

void QuickSort1(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int begin = left;//记录左右边界
	int end = right;
	int midi = GetMidi(a, left, right);
	Swap(&a[left], &a[midi]);

	int key = a[left];
	int cur = left + 1;
	while (cur <= right)
	{
		if (a[cur] < key)
		{
			Swap(&a[cur], &a[left]);
			++left;
			++cur;
		}
		else if (a[cur] > key)
		{
			Swap(&a[cur], &a[right]);
			--right;
		}
		else
		{
			++cur;
		}
	}
	QuickSort1(a, begin, left-1);
	QuickSort1(a, right+1, end);
}
int* sortArray(int* nums, int numsSize, int* returnSize){
	srand(time(NULL));
    QuickSort1(nums, 0, numsSize-1);
    *returnSize=numsSize;
    
    return nums;
}

运行后如图
快排&超详细,Leetcode排序数组题目带你升华掌握,数据结构,leetcode,算法,数据结构,排序算法,推荐算法
可以发现所用时间还是很长,这道题如果用堆排序和shell排序都是很好过的,放在这里是为了提升我们对快排的理解和掌握。

小区间优化

 在上边显示递归流程的图中,我们可以看到递归的过程,类比树的结构,树的每一个节点都是一次递归,树的最后一排的节点个数占全部节点的50%,倒数第二行占总个数的25%,如果分成的数组的量的变小到一定的个数的时候可以不再使用递归,而是选择其他的方法进行排序,可以减少大量的递归次数。
这种方法叫做小区间优化,使用什么排序比较好呢?冒泡排序和选择排序的时间复杂度为O(N²),选择排序的时间复杂度最高为O(N²),可以使用选择排序进行小区间优化,从而减少大量的递归次数
插入排序及小区间优化后的代码如下


//插入排序
void InsertSort(int* a, int n)
{
	//[0,end]有序,把end+1的位置插入到前序序列
	//控制[0,end+1]有序
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
			}
			else
			{
				break;
			}-+
			--end;
		}
		a[end + 1] = tmp;
	}
}
//加上小区间优化
void QuickSort2(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	if ((end - begin + 1) > 10)//如果一个数组的元素小于10,就进行插入排序
	{
		int keyi = PartSort2(a, begin, end);
		QuickSort2(a, begin, keyi - 1);
		QuickSort2(a, keyi + 1, end);
	}
	else
	{
		InsertSort(a + begin, end - begin + 1);
	}
}

//加上小区间优化
void QuickSort2(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	if ((end - begin + 1) > 10)
	{
		int keyi = PartSort2(a, begin, end);
		QuickSort2(a, begin, keyi - 1);
		QuickSort2(a, keyi + 1, end);
	}
	else
	{
		InsertSort(a + begin, end - begin + 1);
	}
}

快排非递归版
复习一下:它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归 进行,以此达到整个数据变成有序序列。
将一整个数组不断细分,在不断划分的过程中进行有序化,最终完成排序的功能。在前边partsort函数中,我们只要通过某种方法得到分成一组一组的小数组段的left和right即可。
上边的说明递归的流程图是直接全部展开的,实际上是一直向左划分,直到分出的数组left和right相等,然后回到上步。
如图所示
快排&超详细,Leetcode排序数组题目带你升华掌握,数据结构,leetcode,算法,数据结构,排序算法,推荐算法
结合代码就很容易明白。
在非递归版本我们想和递归的步骤相同,如何得到上述递归过程中的left和right?这是问题之所在,而且在递归过程中向partsort1传入不同的left和right。
可以借助栈先进先出的功能来实现,push起始的left和right,进行第一次partsort,知道了left和right后,将他们再pop掉。

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 = PartSort1(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);
}

快排讲到这里就结束啦,如果你有耐心看完的话你一定会对快排的掌握有所提升哒。
加油!文章来源地址https://www.toymoban.com/news/detail-715933.html

到了这里,关于快排&超详细,Leetcode排序数组题目带你升华掌握的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 数组(一篇带你掌握数组)

        在之前,我们想要存储一个数据的时候可以创建变量,例如存储一个整形的变量,我们使用int类型的变量来存储,那么如果存储一组相同类型的数据呢?这时我们就引入了 数组 的概念。 目录 一、一维数组的创建和初始化 1.1数组的创建 1.2 数组的初始化 1.3 一维数组的使

    2023年04月08日
    浏览(47)
  • 【排序算法】 快速排序(快排)!超详细看这一篇就够了”保姆级教学“

    🎥 屿小夏 : 个人主页 🔥个人专栏 : 算法—排序篇 🌄 莫道桑榆晚,为霞尚满天! 什么是快排?快排的速度到底有多快呢?它们的思想和实现是什么样的? 本文会对这快速排序进行详解,绝对细致入微!让你彻底搞懂快排! 英国计算机科学家Tony Hoare在1960年为了解决计算

    2024年02月05日
    浏览(51)
  • 带你刷算法——数组/字符串的完全掌握(一)

    「作者主页」 :雪碧有白泡泡 「个人网站」 :雪碧的个人网站 「推荐专栏」 : ★ java一站式服务 ★ ★ 前端炫酷代码分享 ★ ★ uniapp-从构建到提升 ★ ★ 从0到英雄,vue成神之路 ★ ★ 解决算法,一个专栏就够了 ★ ★ 架构咱们从0说 ★ ★ 数据流通的精妙之道★ 给你两个

    2024年02月13日
    浏览(54)
  • 代码随想录额外题目| 数组03 ●34排序数组查首尾位置 ●922按奇偶排序数组II●35搜索插入位置

    #34排序数组查首尾位置 medium,我写的:1 暴力 我写的,做了个类似二分搜索的方法: 随想录:从两头都做类似二分搜索 #922 按奇偶排序数组II 我的解法,有点蠢: inplace解法: 把odd idx放的偶数,给换到even idx放的奇数 注意j是从1开始,而且每轮i,j都是继续增加不回去 空间表

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

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

    2024年02月02日
    浏览(60)
  • C语言题目 - 调用qsort函数对数组进行排序

    如题 其实没什么难的,只要严格按照 qsort 函数的参数来填充即可,这里要用到 函数指针 。 qsort 函数的原型如下: void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void *)); 参数说明: base :指向需要排序的数组的指针,数组中每个元素的大小应为 size 字节。

    2024年02月11日
    浏览(41)
  • 【C语言初阶】带你轻松掌握指针基础知识完结篇——野指针,指针运算,指针和数组,二级指针

    君兮_的个人主页 勤时当勉励 岁月不待人 C/C++ 游戏开发 Hello,这里是君兮_,今天继续给大家更新0基础入门C语言的内容,我们这次主要更新的依然是初阶指针的基础知识 废话不多说咱们直接开始吧!! 概念: 野指针就是指针指向的位置是不可知的(随机的、不正确的、没有

    2024年02月16日
    浏览(45)
  • 【LeetCode题目详解】 977.有序数组的平方 209.长度最小的子数组59.螺旋矩阵II day2

    看完这个题目第一想法就是直接暴力解决,直接将全部平方然后进行排序。比如快排。 代码如下: 时间复杂度是 O(nlogn)或者说【O(n + nlogn)】,括号里面这个是为了比较接下来的方法。 然后看了代码随想录的视频学习了用双指针来写这道题的方法(说实话不看视频真没想到可

    2024年02月13日
    浏览(42)
  • leetcode 912.排序数组

    🌟 leetcode链接:排序数组 思路: 此题如果使用冒泡插入选择这些时间复杂度 O ( N 2 ) O(N^2) O ( N 2 ) 的算法会超时,使用快排 + 优化也过不去,因为里面有一个测试用例全是 2 即使加了三数取中也会是 O ( N 2 ) O(N^2) O ( N 2 ) ,以下实现主要使用归并排序。 如果需要其他排序的可

    2024年02月14日
    浏览(47)
  • leetcode 33.搜索旋转排序数组

    🌟 leetcode链接:搜索旋转排序数组 ps: 本题是二分查找的变形,旋转排序数组之后其实会 形成两个有序的区间 。算出平均下标先判断是否与 target 相等,因为这样可以减少代码的冗余。如果前者不成立则使用平均下标元素 midIndex 与 数组最后一个元素判断大小(因为我们可

    2024年02月13日
    浏览(45)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包