1. Toy模板网首页
  2. > Toy博客

第11章：C语言数据结构与算法初阶之排序

7月前 作者：好好锅 分类：Toy博客 阅读(32) 违法举报

这篇具有很好参考价值的文章主要介绍了第11章：C语言数据结构与算法初阶之排序。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

系列文章目录

前言

排序是一种非常重要的算法。

排序的概念及其运用

排序的概念

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

内部排序：数据元素全部放在内存中的排序。

外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

常见的排序算法

第11章：C语言数据结构与算法初阶之排序,# C语言之数据结构初阶,c语言,排序算法,算法

常见排序算法的实现

1.直接插入排序

基本思想：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。 =>打扑克牌
第11章：C语言数据结构与算法初阶之排序,# C语言之数据结构初阶,c语言,排序算法,算法

void InsertSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{//i = n - 1 时已经排完了
		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;
		//放在结束位置的后一个位置，即要插入的位置
	}
	
}

插入排序在部分或已经有序的数列效率最高。
时间复杂度：
最坏：逆序——O(N2)
最好：顺序有序——O(N)

2. 希尔排序（缩小增量排序）

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。=>优化的插入排序

步骤
1. 多次预排序（分组排序）：对原数组进行间隔分组，再对分组进行插入排序，使得原数组变得相对更有序
2. 最有一次插入排序：当分组排序的间隔为1时

第11章：C语言数据结构与算法初阶之排序,# C语言之数据结构初阶,c语言,排序算法,算法

void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{	// gap > 1预排序
		// gap == 1 就是插入排序

		gap = gap / 3 + 1;
		//gap = gap / 2;
		
		for (int i = 0; i < n - gap; i++)
		{//i++gap组并排
		 //i = n - gap 时已经排完了
			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;
			//放在结束位置的后一个位置，即要插入的位置
		}
	}
}

1. gap越大，大的数可以更快到后面，小的可以更快到前面；越不接近有序。
2. gap越小，数据跳动越慢，越接近有序

时间复杂度：
分成gap组，每组N/gap个数据
每组最坏情况下挪动次数：1+2+3+…+N/gap-1 等差数列
最坏情况：（1+2+3+…+N/gap) * gap

最开始时gap很大 => 一趟排序：N
快结束时gap很小 => 一趟排序：N
排序次数：log2N

时间复杂度：O(N1.3)

3. 直接选择排序

基本思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。

  • 在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素
  • 若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换
  • 在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素
void SelectSort(int* a, int n)
{
	int begin = 0;
	int end = n - 1;

	
	while (begin < end)
	{
		//每次遍历选出最小和最大的数
		int mini = begin;
		int max = begin;
		for (int i = begin + 1; i <= end; i++)
		{
			if (a[i] < a[mini])
				mini = i;
			if (a[i] > a[max])
				max = i;
		}
		swap(&a[mini], &a[begin]);
		//如果max位置和mini位置重叠，需要修正一下max的位置
		if (max == begin)
			max = mini;
		swap(&a[max], &a[end]);
		//将最小和最大的数放到左右两边的位置
		begin++;
		end--;
	}
}

时间复杂度：O(N2)
空间复杂度：O(1)

与直接插入排序比较，插入排序适应性更强，对于有序、局部有序，都能效率提升。
而选择排序在任何情况都是O(N2)。

4. 堆排序

基本思想：堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
第11章：C语言数据结构与算法初阶之排序,# C语言之数据结构初阶,c语言,排序算法,算法

void AdjustDown(int* a, int parent, int size)
{//升序建大堆，降序建小堆
	int child = parent * 2 + 1;
	while (child < size)
	{
		//确认child指向大的哪个孩子
		if (child + 1 < size && a[child + 1] < a[child])
		{
			++child;
		}

		if (a[child] > a[parent])
		{//孩子大于父亲，交换，继续向下调整，建大堆
			swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{//孩子小于父亲
			break;
		}
	}
}

// O(N * logN)
void HeapSort(int* a, int n)
{
	//向上调整堆 -- O(N*logN)
	//降序
	/*for (int i = 0; i < n; i++)
	{
		AdjustUp(a, i);
	}*/

	//向下调整堆 -- O(N)
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, i, n);
	}
	int end = n - 1;
	while (end)
	{
		//升序 -- O(N * logN)
		swap(&a[0], &a[end]);
		AdjustDown(a, 0, end);
		end--;
	}
}

void swap(int* a, int * b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}

时间复杂度：O(N*logN)

5. 冒泡排序

基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排
序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

void BubbleSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{//冒泡 n - 1 次
		int exchange = 0;
		for (int j = 0; j < n - i - 1; j++)
		{//每次都是n - i - 1上的位置确定
			if (a[j] > a[j + 1])
				swap(&a[j], &a[j + 1]);
				exchange = 1;
		}

		if (exchange == 0)
		{//没有交换就说明有序了
			break;
		}
	}
}

冒泡排序在已经有序的数列效率最高。
时间复杂度：O(N^2)
空间复杂度：O(1)

6. 快速排序

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

将区间按照基准值划分为左右两半部分的常见方式：

1. hoare版本

第11章：C语言数据结构与算法初阶之排序,# C语言之数据结构初阶,c语言,排序算法,算法
key:最左边的值或最右边的值
单趟排序：左边比key要小，右边比key要大

1. 分割出左右区间，左区间比key小，右区间比key大
2. key已经落到他的正确的位置，排序后的最终位置
剩下的问题：
3. 左区间有序，右区间有序，那么整体就有序了

左边做key，右边先走，右边做key，左边先走；
左边做key，右边先走，保证相遇位置比key小；
右边做key，左边先走，保证相遇位置比key大；

相遇的位置：
如果左边做key，右边先走
一种是R停住的，L遇到R，相遇位置就是R停住的位置；
一种是L停住的，R遇到L，相遇位置就是L停住的位置；
这两种位置都比key要小

int PartSort1(int* a, int begin, int end)
{//hoare法

	int mid = GetMidIndex(a, begin, end);
	swap(a + begin, a + mid);

	int left = begin;
	int right = end;
	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);
	keyi = left;
	
	return keyi;
	
}

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

第11章：C语言数据结构与算法初阶之排序,# C语言之数据结构初阶,c语言,排序算法,算法
平均时间复杂度：O(N*log2N)

第11章：C语言数据结构与算法初阶之排序,# C语言之数据结构初阶,c语言,排序算法,算法
最坏时间复杂度：O(N2)

优化版本：三数取中法选key
//三数取中
//begin mid end
int GetMidIndex(int* a, int begin, int end)
{
	int mid = (begin + end) / 2;
	if (a[begin] > a[end])
	{
		if (a[mid] > a[begin])
			return a[begin];
		else if (a[mid] > a[end])
			return a[mid];
		else
			return a[end];
	}
	else
	{//a[begin] <= a[end]
		if (a[mid] > a[end])
			return a[end];
		else if (a[mid] > a[begin])
			return a[mid];
		else
			return a[begin];
	}

}


void QuickSort(int* a, int begin, int end)
{
	if (begin >= end) return;
	

	int left = begin;
	int right = end;
	int keyi = left;

	int mid = GetMidIndex(a, begin, end);
	swap(a + keyi, a + mid);
	

	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);
	keyi = left;
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
	
}

三数取中将最坏时间复杂度降为：O(N*log2N)

优化版本：递归到小的子区间时，可以考虑使用插入排序

小区间优化：快排分割到小区间时，用直接插入排序，节省大部分递归

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end) return;
	
	if (end - begin + 1 < 10)
	{
		// 小区间用直接插入代替，减少递归调用次数
		InsertSort(a+begin, end - begin + 1);
	}
	else
	{
		int left = begin;
		int right = end;
		int keyi = left;


		int mid = GetMidIndex(a, begin, end);
		swap(a + keyi, a + mid);


		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);
		keyi = left;
		QuickSort(a, begin, keyi - 1);
		QuickSort(a, keyi + 1, end);
	}
	
	
}
2. 挖坑版本

第11章：C语言数据结构与算法初阶之排序,# C语言之数据结构初阶,c语言,排序算法,算法

int PartSort2(int* a, int begin, int end)
{	//挖坑法
	//左挖坑，右填坑，右挖坑，左填坑。

	int mid = GetMidIndex(a, begin, end);
	swap(a + begin, a + mid);

	int left = begin;
	int right = end;
	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[right] = a[left];
		hole = left;
	}
	a[hole] = key;
	return hole;
	
}

1. 右边找到一个坑位，要填左边的坑，再挖该坑位。
2. 左边找到一个坑位，要填右边的坑，再挖该坑位。

3. 前后指针版本

第11章：C语言数据结构与算法初阶之排序,# C语言之数据结构初阶,c语言,排序算法,算法

int PartSort3(int* a, int begin, int end)
{//把大的推到右边去，把小的推到左边去
	int mid = GetMidIndex(a, begin, end);
	swap(a + begin, a + mid);

	int cur = begin + 1;
	int prev = begin;
	int keyi = begin;
	/*for (; cur < end + 1; cur++)
	{
		if (a[cur] > a[keyi])
		{
			prev++;
			swap(a + prev, a + cur);
		}
	}*/
	while (cur <= end)
	{
		if (a[cur] > a[keyi] && ++prev != cur)
		{
			swap(&a[++prev], &a[cur]);
		}
		cur++;
		
	}
	swap(a + prev, a + keyi);
	return prev;
}

1. cur找key小，找到后停下来。
2. ++prev,交换prev位置和cur位置。

4. 快速排序非递归实现版本

第11章：C语言数据结构与算法初阶之排序,# C语言之数据结构初阶,c语言,排序算法,算法
进栈顺序图

void QuickSortNonR(int* a, int begin, int end)
{
	ST st;
	StackInit(&st);
	StackPush(&st, begin);
	StackPush(&st, end);
	while (!StackEmpty(&st))
	{
		int right = StackTop(&st);
		StackPop(&st);
		int left = StackTop(&st);
		StackPop(&st);

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

		if (keyi + 1 < right)
		{
			StackPush(&st, keyi + 1);
			StackPush(&st, right);
		}
		
		if (left < keyi - 1)
		{
			StackPush(&st, left);
			StackPush(&st, keyi - 1);
		}
		
	}
}

快速排序的特性总结：

时间复杂度：O(N*logN)
空间复杂度：O(logN)
大量的重复数据，那么key就是这个重复的数时，就会导致时间复杂度上升为O(N2)。
第11章：C语言数据结构与算法初阶之排序,# C语言之数据结构初阶,c语言,排序算法,算法
可以用三路划分来解决重复数。

1.a[c] < key 交换a[l]和a[c]的位置，l++，c++ => 比key小的数甩到左边
2.a[c] == key c++=> 跟key相等的值，往后推，跟key相等的就会在中间
3.a[c] > key 交换c和r的位置，r–=>比key大的甩到右边
结束条件：c > r 结束
第11章：C语言数据结构与算法初阶之排序,# C语言之数据结构初阶,c语言,排序算法,算法

7. 归并排序

基本思想：归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
归并排序核心步骤：

归并排序的几种实现方式

1. 递归法

第11章：C语言数据结构与算法初阶之排序,# C语言之数据结构初阶,c语言,排序算法,算法

void _MergeSort(int* a, int begin, int end, int* tmp)
{
	if (begin >= end) return;
	int mid = (begin + end) / 2;
	_MergeSort(a, begin, mid, tmp);
	_MergeSort(a, mid + 1, end, tmp);

	//归并
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int i = begin;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] > a[begin2])
		{
			tmp[i++] = a[begin1++];
		}
		else
		{
			tmp[i++] = a[begin2++];
		}
	}

	while (begin1 <= end1)tmp[i++] = a[begin1++];
	while (begin2 <= end2)tmp[i++] = a[begin2++];

	memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));



}

void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	_MergeSort(a, 0, n - 1, tmp);

	free(tmp);
	tmp = NULL;

}

两端有序区间，依次得比较小的元素，尾插进新的数组序列
时间复杂度：O(N*logN)
空间复杂度：O(logN)

2. 非递归法
void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	//归并每组数据个数，从1开始，因为1个认为是有序的，可以直接归并
	int rangeN = 1;

	while (rangeN < n)
	{
		for (int i = 0; i < n; i += 2 * rangeN)
		{
			//归并
			int begin1 = i, end1 = i + rangeN - 1;
			int begin2 = i + rangeN, end2 = i + 2 * rangeN - 1;
			
			if (end1 >= n)
			{//end1 begin2 end2 越界
				//修正区间 ->拷贝数据 
				end1 = n - 1;
				//不存在区间
				begin2 = n;

				end2 = n - 1;
			}
			else if (begin2 >= n)
			{//begin2 end2 越界
				begin2 = n;

				end2 = n - 1;
			}
			else if (end2 >= n)
			{//end2 越界
				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, tmp, sizeof(int)* (n));
		rangeN *= 2;
	}
	
	free(tmp);
	tmp = NULL;
}

8. 计数排序

思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。 操作步骤：
1. 统计相同元素出现次数
2. 根据统计的结果将序列回收到原来的序列中
第11章：C语言数据结构与算法初阶之排序,# C语言之数据结构初阶,c语言,排序算法,算法

void CountSort(int* a, int n)
{//计数排序
	int max = a[0], min = a[0];
	for (int i = 1; i < n; i++)
	{
		if (a[i] > max) max = a[i];
		if (a[i] < min) min = a[i];
	}
	int range = max - min + 1;
	int* countA = (int*)calloc(range,sizeof(int));
	if (countA == NULL)
	{
		printf("calloc fail");
		exit(-1);
	}
	//1. 统计次数
	for (int i = 0; i < n; i++)
	{
		countA[a[i] - min]++;
	}
	//2. 排序
	int k = 0;
	for (int j = 0; j < range; j++)
	{
		while (countA[j]--)
			a[k++] = j + min;
	}

	free(countA);
}

时间复杂度：O(MAX(N,range))
空间复杂度：O(Range)
适合范围集中的数据，只适合整型

排序算法复杂度及稳定性分析

稳定性：相同的数保证它们的相对顺序不变，那么就是稳定的。
第11章：C语言数据结构与算法初阶之排序,# C语言之数据结构初阶,c语言,排序算法,算法
第11章：C语言数据结构与算法初阶之排序,# C语言之数据结构初阶,c语言,排序算法,算法
第11章：C语言数据结构与算法初阶之排序,# C语言之数据结构初阶,c语言,排序算法,算法
归并排序可以是内排序或外排序，其他排序是内排序。

总结

排序是非常重要的算法，一定要理解每种算法的原理。
真正的才智是刚毅的志向。——拿破仑文章来源地址https://www.toymoban.com/news/detail-532724.html

到了这里，关于第11章：C语言数据结构与算法初阶之排序的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

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

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 数据结构初阶之二叉树的详细解析

    数据结构初阶之二叉树的详细解析

    个人主页：点我进入主页 专栏分类：C语言初阶      C语言程序设计————KTV       C语言小游戏     C语言进阶 C语言刷题       数据结构初阶    Linux 欢迎大家点赞，评论，收藏。 一起努力,共赴大厂。 目录 1.前言  2.二叉树各个功能代码实现 2.1二叉树结构体 2.2二叉

    2024年02月05日
    浏览(26)
  • 数据结构初阶之二叉树性质练习与代码练习

    数据结构初阶之二叉树性质练习与代码练习

    个人主页：点我进入主页 专栏分类：C语言初阶      C语言程序设计————KTV       C语言小游戏     C语言进阶 C语言刷题       数据结构初阶    Linux 欢迎大家点赞，评论，收藏。 一起努力,共赴大厂。 目录 1.前言 2.性质练习 3.代码练习  3.1单值二叉树 3.2检查两颗树

    2024年02月04日
    浏览(30)
  • 『初阶数据结构 • C语言』⑥ - 插入排序&希尔排序

    『初阶数据结构 • C语言』⑥ - 插入排序&希尔排序

    学习目标 写在前面 1.插入排序 2.插入排序实战  3.插入排序的实现  4.插入排序的效率 5.平均情况 6.希尔排序 7.希尔排序的实现 8.希尔排序的效率 9.总结   之前我们衡量一个算法的效率时，都是着眼于它在最坏情况下需要多少步。原因很简单，连最坏的情况都做足准备了，其

    2024年02月15日
    浏览(26)
  • 『初阶数据结构 • C语言』④ - 冒泡排序

    『初阶数据结构 • C语言』④ - 冒泡排序

      本文内容借鉴一本我非常喜欢的书——《数据结构与算法图解》。学习之余，我决定把这本书精彩的部分摘录出来与大家分享。      本章内容 写在前面 1.冒泡排序 2.冒泡排序实战 3.冒泡排序的实现 4.冒泡排序的效率 5.二次问题 6.线性解决 7.总结     大 O记法能客观地衡量

    2024年02月16日
    浏览(26)
  • 『初阶数据结构 • C语言』⑤ - 选择排序

    『初阶数据结构 • C语言』⑤ - 选择排序

    本文内容借鉴一本我非常喜欢的书——《数据结构与算法图解》。学习之余，我决定把这本书精彩的部分摘录出来与大家分享。     目录 写在前面 1.选择排序 2.选择排序实战 3.选择排序的实现 4.选择排序的效率 5.忽略常数 6.大O的作用 7.总结     大 O 是一种能够比较算法效

    2024年02月14日
    浏览(30)
  • 【数据结构初阶】八大排序算法+时空复杂度

    【数据结构初阶】八大排序算法+时空复杂度

    学会控制自己是人生的必修课 1.直接插入排序思想： 假设现在已经有一个有序序列，如果有一个数字插入到这段序列的末尾，我们会选择拿这个数和它前面的每个数字都比较一遍，如果前面的数字比他大，那我们就让前面的数字赋值到这个被插入的数字位置，依次与前面的数

    2024年02月01日
    浏览(55)
  • 『初阶数据结构 • C语言』⑬ - 堆排序详解【附完整源码】

    『初阶数据结构 • C语言』⑬ - 堆排序详解【附完整源码】

     = 目录 0.写在前面 1.什么是堆？ 2. 堆排序 2.1 建堆 2.1.1 AdjustUp（向上调整算法） 2.1.2 AdjustDown（向下调整算法） 2.2 两种建堆算法的时间复杂度 2.2.1 AdjustUp建堆的时间复杂度 2.2.2 AdjustDown建堆的时间复杂度 2.3 排序 3.堆排序的时间复杂度 完整源码 你是否对堆排序早有耳闻？身

    2024年02月16日
    浏览(29)
  • 『初阶数据结构 • C语言』② - 算法为何重要

    『初阶数据结构 • C语言』② - 算法为何重要

    本文内容借鉴一本我非常喜欢的书——《数据结构与算法图解》。学习之余，我决定把这本书精彩的部分摘录出来与大家分享。   算法这个词听起来很深奥，其实不然。它只是解决某个问题的一套流程。  准备一碗麦片的流程也可以说是一种算法，它包含以下 4步（对我来说

    2024年02月14日
    浏览(21)
  • 【数据结构初阶】十、快速排序(比较排序)讲解和实现（三种递归快排版本 + 非递归快排版本 -- C语言实现）

    【数据结构初阶】十、快速排序(比较排序)讲解和实现（三种递归快排版本 + 非递归快排版本 -- C语言实现）

    ========================================================================= 相关代码gitee自取 ： C语言学习日记: 加油努力 (gitee.com)  ========================================================================= 接上期 ： 【数据结构初阶】九、排序的讲解和实现（直接插入 希尔 直接选择 堆 冒泡 -- C语言）

    2024年02月08日
    浏览(32)
  • 『初阶数据结构 • C语言』⑰ - 快速排序（hoare法、挖坑法、前后指针法与非递归实现）

    『初阶数据结构 • C语言』⑰ - 快速排序（hoare法、挖坑法、前后指针法与非递归实现）

    目录 1. hoare法 方法与步骤 代码实现 2. 挖坑法 方法与步骤 代码实现 3. 前后指针法 方法与步骤 代码实现  4. 快速排序的缺点与优化 1.快速排序的缺点 2.快速排序的优化 ① 三数取中法选 key 代码实现 ② 小区间优化 代码实现 5. 快速排序的非递归实现 附录﹡完整源码 快速排序

    2024年02月13日
    浏览(28)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包