探索数据结构：快速排序与归并排序的实现与优化

码农世界 2024-06-20 后端 110 次浏览 0个评论

✨✨ 欢迎大家来到贝蒂大讲堂✨✨

🎈🎈养成好习惯，先赞后看哦~🎈🎈

所属专栏：数据结构与算法
贝蒂的主页：Betty’s blog

1. 快速排序

1.1. 算法思想

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

1.2. 算法实现

快速排序的实现方式有很多，下面我们主要介绍三种方法。

1.2.1. Hoare法

利用两个变量left，right分别指向数组的起始位置与末尾位置。并且以数组第一个元素作为key值。
right先从右往左依次遍历找到比key小的数，left从左往右依次遍历找到比key大的数。然后交换left与right下标对应的值。重复步骤2直至right>=left。
之后交换key与left或者right对应的值，并且把该位置记为mid。
最后划分区间[left，mid-1]与[mid+1,right]继续重复1,2步骤。直至不能划分。

思考：为什么最后相遇位置一定小于或等于**key**值？

我们知道right与left相遇无非两种情况：

情况一：right停住，left移动与right相遇·。因为right一直再找比key小的值，所以right停下位置一定比key小，相遇位置也一定比key小。
情况二：left停住，right移动与left相遇·。此时又分为两种情况：

left从未移动，右侧数据都比可以大，相遇位置就是key，交换不变。
left移动过至少一次，也就是至少交换过一次，此时left停留位置的值是上一轮right所对应的值，又因为right一直再找比key小的值，所以相遇位置也一定比key小。

代码实现：

void swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
int PartSort1(int* arr, int begin, int end)
{
	int left = begin, right = end;
	int keyi = begin;
	while (left < right)
	{
		//left=而不是>防止数据出现死循环
		while (left=arr[keyi])
			//寻找比key小的值
		{
			right--;
		}
		while (left < right && arr[left] <= arr[keyi])
			//寻找比key大的值
		{
			left++;
		}
		swap(&arr[left], &arr[right]);
	}
	int mid = left;
	swap(&arr[keyi], &arr[mid]);
	return mid;
}
void QuickSort(int* arr, int left, int right)
{
	if (left >= right)//不能划分
	{
		return;
	}
	int mid = PartSort1(arr, left, right);//单趟排序
	QuickSort(arr, left, mid - 1);//左区间
	QuickSort(arr, mid+1, right);//右区间
}

1.2.2. 挖坑法

先将起始位置key值设为坑，之后right从右往左找比key值小的值，找到之后放入坑位，此时right就形成新的坑。然后left从左往右找比key大的值，找到之后放入坑位，此时left就又形成新的坑。
最后left与right相遇，将key放入最后一个坑，并将该位置记为mid，。·
最后划分区间[left，mid-1]与[mid+1,right]继续重复1,2步骤。直至不能划分。

代码实现：

int PartSort2(int* arr, int begin, int end)
{
	int left = begin, right = end;
	int hole = begin;//记录坑位
	int key = arr[left];
	while (left < right)
	{
		//left=而不是>防止数据出现死循环
		while (left < right && arr[right] >= key)
			//寻找比key小的值
		{
			right--;
		}
		arr[hole] = arr[right];
		hole = right;
		while (left < right && arr[left] <= key)
			//寻找比key大的值
		{
			left++;
		}
		arr[hole] = arr[left];
		hole = left;
	}
	arr[hole] = key;
	return hole;
}
void QuickSort(int* arr, int left, int right)
{
	if (left >= right)//不能划分
	{
		return;
	}
	int mid = PartSort2(arr, left, right);//单趟排序
	QuickSort(arr, left, mid - 1);//左区间
	QuickSort(arr, mid+1, right);//右区间
}

1.2.3. 前后指针法

先定义一个prev指向数组首元素，然后定义一个cur指向第二个位置。
cur从左往右依次遍历找key小的值，找到之后++prev，然后交换prev与cur指向的值。之后cur++继续遍历。(key为起始位置的值)
当cur遍历完之后，此时交换prev指向的值与key。将此时位置记为mid。
最后划分区间[left，mid-1]与[mid+1,right]继续重复1,2,3步骤。直至不能划分。

代码实现：

int PartSort3(int* arr, int begin, int end)
{
	int prev = begin;
	int cur = begin + 1;
	int keyi = begin;
	while (cur <= end)
	{
		if (arr[cur] < arr[keyi])//小于则交换
		{
			swap(&arr[++prev], &arr[cur]);
		}
		cur++;	
	}
	swap(&arr[prev], &arr[keyi]);
	return prev;
}
void QuickSort(int* arr, int left, int right)
{
	if (left >= right)//不能划分
	{
		return;
	}
	int mid = PartSort3(arr, left, right);//单趟排序
	QuickSort(arr, left, mid - 1);//左区间
	QuickSort(arr, mid+1, right);//右区间
}

1.3. 复杂度分析

时间复杂度：通常情况下，需要递归logN层，每层都需要遍历，所以时间复杂度为O(NlogN)。

空间复杂度：通常情况下，需要递归logN层，所以空间复杂度为O(logN)。

1.4. 算法优化

1.4.1. 改变基准元素

当数组有序时，我们再对其进行快速排序，其时间复杂度讲话劣化为O(N2)。

这时候我们为了防止这种现象，可以选择提前改变基准元素key。

三数取中：即取出数组首尾以及中间元素，选取数值位于中间的元素作为准元素key。

int GetMidNum(int*arr, int left, int right)
{
	int mid = (left + right) >> 1;
	if (arr[mid] > arr[left])
	{
		if (arr[mid] < arr[right])
		{	//left  mid  right
			return mid;
		}
		else if (arr[left] > arr[right])
		{	//right  left  mid
			return left;
		}
		else
		{	//left  right  mid
			return right;
		}
	}
}
int PartSort3(int* arr, int begin, int end)
{
	int prev = begin;
	int cur = begin + 1;
	int keyi = begin;
	int mid=GetMidNum(arr, begin, end);
	swap(&arr[begin], &arr[mid]);
	while (cur <= end)
	{
		if (arr[cur] < arr[keyi])//小于则交换
		{
			swap(&arr[++prev], &arr[cur]);
		}
		cur++;	
	}
	swap(&arr[prev], &arr[keyi]);
	return prev;
}

随机数取中：三数取中有时候也并不能保证基准元素的准确性，这时候我们最好使用随机数获取基准值。

int GetRanNum(int*arr, int left, int right)
{
	srand(time(0));//生成随机种子
	int mid = rand() % (right - left) + left;//随机数
	return mid;
}

1.4.2. 聚集元素

除了数组有序的情况外，还有一种情况也会导致快速排序的时间复杂度劣化为O(N2 )，那就是当数组元素全部相同时。

为了解决这个问题，我们采用一种三指针分化区间的方式。其步骤如下：

分别定义三个指针left,cur,right分别指向数组首元素，第二个元素，最后一个元素。
从左往右用cur依次遍历数组：(key为数组第一个元素)

如果arr[cur]
如果arr[cur]>key，交换arr[cur]与arr[right]，再让right--。
如果arr[cur]==key，直接让cur++。
重复步骤2直至cur>right,成功划分区间。小于key：[begin,left-1]，等于key：[left, right] 大于key：[right + 1, end]。

问题：为什么当arr[cur]>key，交换arr[cur]与arr[right]时不让cur++？

因为交换过来的值可能比key大，也可能比key小。如果直接cur++，并不能对这个元素进行正确的划分。

void ThreeDivision(int*arr, int*left, int*right)
{
	int cur = *left + 1;
	int key = arr[*left];
	while (cur <= *right)
	{
		if (arr[cur] < key)//大于key
		{
			swap(&arr[(*left)++], &arr[cur++]);
		}
		else if (arr[cur] > key)//小于key
		{
			swap(&arr[cur], &arr[(*right)--]);
		}
		else//等于key
		{
			cur++;
		}
	}
}
void QuickSort(int* arr, int begin, int end)
{
	if (begin >= end)//不能划分
	{
		return;
	}
	if ((end - begin + 1) < 10)//小区间优化
	{
		InsertSort(arr, end - begin + 1);
		return;
	}
	int mid = GetRanNum(arr, begin, end);
	swap(&arr[begin], &arr[mid]);
	int left = begin;
	int right = end;
	ThreeDivision(arr, &left, &right);//三指针划分区间
	//[begin, left - 1][left, right][right + 1, end]
	QuickSort(arr, begin, left - 1);//左区间
	QuickSort(arr, left+1, end);//右区间
}

1.4.3. 区间优化

在我们进行递归调用时，递归越深递归调用的次数就会越多，为了优化这个问题，我们可以当区间较小时采用其他排序。

其中我们将递归调用抽象成树的形式：

其中根据我们在树那节学习的知识，我们知道第i层的节点数为2i-1 个，节点总数为2h -1个，**最后三次调用次数就约占据总次数的87.5%。**所以我们可以在倒数三层之后采用其他排序，如插入排序。

void QuickSort(int* arr, int left, int right)
{
	if (left >= right)//不能划分
	{
		return;
	}
	if ((right - left + 1) < 10)//小区间优化
	{
		InsertSort(arr+left, right - left + 1);
		return ;
	}
	int mid = PartSort3(arr, left, right);//单趟排序
	QuickSort(arr, left, mid - 1);//左区间
	QuickSort(arr, mid+1, right);//右区间
}

1.4.4. 尾递归优化

我们知道快速排序的空间复杂度最坏情况下会劣化为O(N)，为了防止栈帧空间的积累，我们可以采用尾递归形式进行递归，并且仅对较短的子数组进行递归。由于较短子数组的长度不会超过n/2，因此这种方法能确保递归深度不超过logN ，从而将最差空间复杂度优化至O(logN) 。

void QuickSort(int* arr, int begin, int end)
{
	while (begin < end)
	{
		int mid = PartSort3(arr, begin, end);
		if (mid - begin
			QuickSort(arr, begin, mid-1);
			begin = mid + 1;//更新区间
		}
		else
		{
			QuickSort(arr, mid + 1, end);//右区间
			end = mid - 1;//更新区间
		}
	}
}

1.5. 非递归实现

我们知道当递归太深时会存在栈溢出的风险，为了避免这种风险我们除了采用尾递归优化空间外，我们还可以采用非递归的形式实现。

非递归实现的方法需要借助栈这个数据结构，利用其后进先出的形式模拟实现递归，具体步骤如下：

首先将左右端点begin，end入栈。
如果栈不为空，则先出栈右端点right，在出栈左端点left，然后将[left,right]进行单趟排序得到基准点keyi。
然后判断[left,keyi-1],[keyi+1,right]区间是否合法，合法就继续入栈。
最后重复步骤2,3，直至栈为空。

void QuickSortNonR(int* a, int begin, int end)
{
	Stack st;
	InitStack(&st);
	PushStack(&st, begin);
	PushStack(&st, end);//入栈
	while (!StackEmpty(&st))
	{
		//先出为右端点
		int right = StackTop(&st);
		PopStack(&st);
        //后出为左端点
		int left = StackTop(&st);
		PopStack(&st);
		//单趟排序
		int keyi = PartSort3(a, left, right);
		//先入右
		if (keyi + 1 < right)//判断区间是否存在
		{
			PushStack(&st, keyi + 1);
			PushStack(&st, right);
		}
		//后入左
		if (left< keyi-1)
		{	
			PushStack(&st, left);
			PushStack(&st, keyi - 1);
		}
	}
	DestroyStack(&st);
}

2. 归并排序

2.1. 算法思想

**归并排序（Merge Sort）**是建立在归并操作上的一种有效的排序算法, 该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

2.2. 算法步骤

创建一个与待排序数组同等大小的tmp数组。
然后将待排序数组分为两个子数组，让两个子数组有序。为了让这两个子数组有序，我们又要将每个子数组分为两个子数组，让其有序。
当子数组没有元素或者只有一个元素时，我们可以认为其有序，然后将两个子数组开始归并。
归并时因为两个子数组有序，我们可以定义两个指针begin1，begin2分别指向两个数组起始位置。然后遍历比较arr[begin1]与arr[begin2]，取较小的元素尾插进tmp数组。
最后tmp数组数据拷贝回原数组。

2.3. 动图演示

2.4. 代码实现

void _MergeSort(int* arr, int begin, int end, int* tmp)
{
	if (begin >= end)
	{
		return;
	}
	int mid = (begin + end) >> 1;//以中间为分割点
	_MergeSort(arr, begin, mid, tmp);//归并左区间
	_MergeSort(arr, mid+1, end, tmp);//归并右区间
	int i = begin;		
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	while (begin1 <= end1 && begin2 <= end2)
	{
	if (arr[begin1] < arr[begin2])
	{
		tmp[i++] = arr[begin1++];
	}
	else
	{
		tmp[i++] = arr[begin2++];
	}
	}
	//若是还有区间存在数据
	while (begin1 <= end1)
	{
		tmp[i++] = arr[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[i++] = arr[begin2++];
	}
	//最后将归并完后后的数据拷贝回原数组
	memcpy(arr + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}
void MergeSort(int* arr, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail:");
		return;
	}
	_MergeSort(arr, 0, n - 1, tmp);
	free(tmp);
	tmp = NULL;
}

2.5. 复杂度分析

时间复杂度：通常情况下，需要递归logN层，每层都需要遍历，所以时间复杂度为O(NlogN)。

空间复杂度：通常情况下，需要创建tmp临时数组，所以空间复杂度为O(N)。

2.6. 算法优化

2.6.1. 区间优化

与快速排序类似，当递归调用层数越多时，最后三层的递归调用会浪费大量时间。为了避免这种情况，这时我们就可以采用小区间使用插入排序的方法。

void _MergeSort(int* arr, int begin, int end, int* tmp)
{
	if (begin >= end)
	{
		return;
	}
	if (end-begin+1<10)//小区间优化
	{
		InsertSort(arr+begin, end-begin+1);
		return;
	}
	int mid = (begin + end) >> 1;//以中间为分割点
	_MergeSort(arr, begin, mid, tmp);//归并左区间
	_MergeSort(arr, mid+1, end, tmp);//归并右区间
	int i = begin;		
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	while (begin1 <= end1 && begin2 <= end2)
	{
	if (arr[begin1] < arr[begin2])
	{
		tmp[i++] = arr[begin1++];
	}
	else
	{
		tmp[i++] = arr[begin2++];
	}
	}
	//若是还有区间存在数据
	while (begin1 <= end1)
	{
		tmp[i++] = arr[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[i++] = arr[begin2++];
	}
	//最后将归并完后后的数据拷贝回原数组
	memcpy(arr + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}

2.6.2. 判断区间有序

在归并排序合并时，如果两个区间是有序,即arr[end1]<=arr[begin2]时就不需要对其进行归并。

void _MergeSort(int* arr, int begin, int end, int* tmp)
{
	if (begin >= end)
	{
		return;
	}
	int mid = (begin + end) >> 1;//以中间为分割点
	_MergeSort(arr, begin, mid, tmp);//归并左区间
	_MergeSort(arr, mid+1, end, tmp);//归并右区间
	int i = begin;		
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	if (arr[begin2] < arr[end1])//区间有序则不合并
	{
		while (begin1 <= end1 && begin2 <= end2)
		{
			if (arr[begin1] < arr[begin2])
			{
				tmp[i++] = arr[begin1++];
			}
			else
			{
				tmp[i++] = arr[begin2++];
			}
		}
		//若是还有区间存在数据
		while (begin1 <= end1)
		{
			tmp[i++] = arr[begin1++];
		}
		while (begin2 <= end2)
		{
			tmp[i++] = arr[begin2++];
		}
		//最后将归并完后后的数据拷贝回原数组
		memcpy(arr + begin, tmp + begin, sizeof(int) * (end - begin + 1));
	}
}

2.7. 非递归实现

非递归实现归并排序，就需要通过迭代来模拟归并排序归并的过程。这时我们可以通过一个变量gap来代表归并区间的大小，初始化gap=1并且每次归并完成之后gap*=2。

void MergeSortNonR(int* arr, int n)//非递归实现
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail:");
		return;
	}
	int gap = 1;//归并区间大小
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2 * gap)
		{
			int j = i;//记录起始位置
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (arr[begin1] < arr[begin2])
				{
					tmp[j++] = arr[begin1++];
				}
				else
				{
					tmp[j++] = arr[begin2++];
				}
			}
			//若是还有区间存在数据
			while (begin1 <= end1)
			{
				tmp[j++] = arr[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[j++] = arr[begin2++];
			}
            //归并一组拷贝一组
			memcpy(arr + i, tmp + i, sizeof(int) * (end2 - i + 1));
		}
		gap *= 2;
	}
}

但是这段代码有一个明显的问题，那就是可能出现越界访问的情况，分别可能是end1越界，begin2越界， end2`越界。

情况一：end1越界，begin2越界，只有一个区间在原数组内，不需要归并拷贝，直接break跳出循环。

情况二：end2越界，有两个区间在原数组内，需要归并拷贝，修正end2=n-1。

void MergeSortNonR(int* arr, int n)//非递归实现
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail:");
		return;
	}
	int gap = 1;//归并区间大小
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2 * gap)
		{
			int j = i;//记录起始位置
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
			if (end1 >= n || begin2 >= n)
			{
				break;
			}
			if (end2 >= n)
			{
				end2 = n - 1;
			}
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (arr[begin1] < arr[begin2])
				{
					tmp[j++] = arr[begin1++];
				}
				else
				{
					tmp[j++] = arr[begin2++];
				}
			}
			//若是还有区间存在数据
			while (begin1 <= end1)
			{
				tmp[j++] = arr[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[j++] = arr[begin2++];
			}
			memcpy(arr + i, tmp + i, sizeof(int) * (end2 - i + 1));
		}
		gap *= 2;
	}
}

3. 文件外排序

当数据量很少时，数据都存在内存中，我们可以用的排序多种多样。但是当数据量足够大时，数据就将会放在磁盘文件中，这时文件指针很难完成随机偏移。即使有着fseek的库函数，效率也是极低的，所以这时最好选择归并排序对其进行排序。

步骤如下：

首先将一个待排序文件分成若干份，每一份文件存储数据都不大于内存最大的容纳范围。
然后将这若干个小文件放入内存中对其进行排序，使每一个文件有序。
然后利用归并排序的思想，以每一个小文件为基准进行归并。
最后归并完毕，就能使原数据量较大的文件有序。

void _MergeSortFile(const char* file1, const char* file2, const char* mfile)
{
	FILE* fout1 = fopen(file1, "r");
	if (fout1==NULL)
	{
		perror("fopen fail");
		return;
	}
	FILE* fout2 = fopen(file2, "r");
	if (fout2==NULL)
	{
		perror("fopen fail");
		return;
	}
	FILE* fin = fopen(mfile, "w");
	if (fin==NULL)
	{
		perror("fopen fail");
		return;
	}
	int num1, num2;
	int ret1 = fscanf(fout1, "%d\n", &num1);//利用返回值判断是否结束
	int ret2 = fscanf(fout2, "%d\n", &num2);
	while (ret1 != EOF && ret2 != EOF)
	{
		//文件指针在读取时会自动往后移动
		if (num1 < num2)
		{
			fprintf(fin, "%d\n", num1);
			ret1 = fscanf(fout1, "%d\n", &num1);
		}
		else
		{
			fprintf(fin, "%d\n", num2);
			ret2 = fscanf(fout2, "%d\n", &num2);
		}
	}
	while (ret1 != EOF)
	{
		fprintf(fin, "%d\n", num1);
		ret1 = fscanf(fout1, "%d\n", &num1);
	}
	while (ret2 != EOF)
	{
		fprintf(fin, "%d\n", num2);
		ret2 = fscanf(fout2, "%d\n", &num2);
	}
	fclose(fout1);
	fclose(fout2);
	fclose(fin);
}
/*文件外排序*/
void MergeSortFile(const char* file)
{
	FILE* fout1 = fopen(file, "w");
	if (fout1 == NULL)
	{
		perror("fopen fail");
		return;
	}
	for (int i = 0; i < 100; ++i)
    {
		int num = rand() % 100;
		fprintf(fout1, "%d\n", num);
    }
	fclose(fout1);
	FILE* fout = fopen(file, "r");
	if (fout==NULL)
	{
		perror("fopen fail");
		return;
	}
	int num = 0;
	const int n = 10;//每个小文件数据个数
	int i = 0;
	int arr[10];
	char subfile[20];
	int filei = 1;
	memset(arr, 0, sizeof(int) * n);//初始化
	//将大文件分为小文件
	while (fscanf(fout, "%d\n", &num) != EOF)
	{
		//首先读9个数据到数组中。
		//如果是一次读取10个数据，第11次进入else时的num会被忽略
		if (i < n - 1)
		{
			arr[i++] = num;	
		}
		else
		{
			arr[i] = num;//放入第10个数据
			QuickSort(arr, 0, n - 1);		//进行排序
			sprintf(subfile, "%d", filei++);//文件名
			FILE* fin = fopen(subfile, "w");
			if (fin==NULL)
			{
				perror("fopen fail:");
				return;
			}
			//将排序好数据写入每个小文件
			for (int j = 0; j < n; ++j)
			{
				fprintf(fin, "%d\n", arr[j]);
			}
			fclose(fin);
			i = 0;		//i重新置0，方便下一次的读取
			memset(arr, 0, sizeof(int) * n);//重置
		}
	}
	//两两归并文件
	char file1[100] = "1";
	char file2[100] = "2";
	char mfile[100] = "12";
	for (int i = 2; i <= 10; i++)
	{
		_MergeSortFile(file1, file2, mfile);
		strcpy(file1, mfile);
		sprintf(file2, "%d", i + 1);//更新文件名
		sprintf(mfile, "%s%d", mfile, i + 1);//更新文件名
	}
}

转载请注明来自码农世界，本文标题：《探索数据结构：快速排序与归并排序的实现与优化》

码农世界 37815篇文章站点微博

每一天，每一秒，你所做的决定都会改变你的人生！

发表评论取消回复

评论列表（暂无评论，110人围观）参与讨论

码农世界管理员

探索数据结构：快速排序与归并排序的实现与优化

1. 快速排序

1.1. 算法思想

1.2. 算法实现

1.2.1. Hoare法

1.2.2. 挖坑法

1.2.3. 前后指针法

1.3. 复杂度分析

1.4. 算法优化

1.4.1. 改变基准元素

1.4.2. 聚集元素

1.4.3. 区间优化

1.4.4. 尾递归优化

1.5. 非递归实现

2. 归并排序

2.1. 算法思想

2.2. 算法步骤

2.3. 动图演示

2.4. 代码实现

2.5. 复杂度分析

2.6. 算法优化

2.6.1. 区间优化

2.6.2. 判断区间有序

2.7. 非递归实现

3. 文件外排序

发表评论取消回复

还没有评论，来说两句吧...

文章目录

码农世界管理员

探索数据结构：快速排序与归并排序的实现与优化

1. 快速排序

1.1. 算法思想

1.2. 算法实现

1.2.1. Hoare法

1.2.2. 挖坑法

1.2.3. 前后指针法

1.3. 复杂度分析

1.4. 算法优化

1.4.1. 改变基准元素

1.4.2. 聚集元素

1.4.3. 区间优化

1.4.4. 尾递归优化

1.5. 非递归实现

2. 归并排序

2.1. 算法思想

2.2. 算法步骤

2.3. 动图演示

2.4. 代码实现

2.5. 复杂度分析

2.6. 算法优化

2.6.1. 区间优化

2.6.2. 判断区间有序

2.7. 非递归实现

3. 文件外排序

Visual Studio 连接 MySQL 数据库 实现数据库的读写（C++）

[工业自动化-1]：PLC架构与工作原理

网络编程（六）TCP并发服务器

Vue3、Element Plus使用v-for循环el-form表单进行校验

Ceph: vdbench 测试ceph存储rbd块设备

linux如何部署前端项目和安装nginx

Windows OpenVPN的安装之服务器自动启动连接

服务器数据恢复—KVM虚拟机被误删除如何恢复虚拟磁盘文件？

发表评论取消回复

还没有评论，来说两句吧...

文章目录

Visual Studio 连接 MySQL 数据库实现数据库的读写（C++）