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

数据结构与算法之手撕排序算法

9月前 作者：小白苦学IT 分类：Toy博客 阅读(47) 违法举报

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

前言

为什么要学习排序算法？
根据统计，早起大型机CPU资源的四分之一都花在了数据排序上面。排序算法作为最基础的算法，各种操作系统、编程语言都提供了内置的实现。既然排序实现随处可见，我们为什么还要自己动手实现呢？虽然经典算法要动手写写加深印象的道理都懂，但直到最近才发现，每种排序算法里都“暗藏玄机”。排序算法看似简单，其实不同的算法中蕴涵着经典的算法策略。通过熟练掌握排序算法，就可以掌握基本的算法设计思想，包括暴力枚举法、时间空间置换、子问题的分治以及随机化。

目录

一.排序的概念及其应用
二.排序分类
1.插入排序
2.选择排序
3.交换排序
4.归并排序

一.排序的概念及其应用

1.1排序的概念

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍
在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

1.2排序运用

数据结构与算法之手撕排序算法

数据结构与算法之手撕排序算法

1.3 常见的排序算法

数据结构与算法之手撕排序算法

// 排序实现的接口
// 插入排序
void InsertSort(int* a, int n);
// 希尔排序
void ShellSort(int* a, int n);
// 选择排序
比特就业课
void SelectSort(int* a, int n);
// 堆排序
void AdjustDwon(int* a, int n, int root);
void HeapSort(int* a, int n);
// 冒泡排序
void BubbleSort(int* a, int n)
// 快速排序
void QuickSort(int* a, int left, int right);
// 归并排序
void MergeSort(int* a, int n)
// 测试排序的性能对比
void TestOP()
{
	srand(time(0));
	const int N = 100000;
	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);
	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];
	}
	int begin1 = clock();
	InsertSort(a1, N);
	int end1 = clock();
	int begin2 = clock();
	ShellSort(a2, N);
	int end2 = clock();
	int begin3 = clock();
	SelectSort(a3, N);
	int end3 = clock();
	int begin4 = clock();
	HeapSort(a4, N);
	int end4 = clock();
	int begin5 = clock();
	QuickSort(a5, 0, N-1);
	int end5 = clock();
	int begin6 = clock();
	MergeSort(a6, N);
	int end6 = clock();
	printf("InsertSort:%d\n", end1 - begin1);
	printf("ShellSort:%d\n", end2 - begin2);
	printf("SelectSort:%d\n", end3 - begin3);
	printf("HeapSort:%d\n", end4 - begin4);
	printf("QuickSort:%d\n", end5 - begin5);
	printf("MergeSort:%d\n", end6 - begin6);
	free(a1);
	free(a2);
	free(a3);
	free(a4);
	free(a5);
	free(a6);
}

二.排序算法分类

1.插入排序

1.1基本思想：

直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。
实际中我们玩扑克牌时，就用了插入排序的思想
数据结构与算法之手撕排序算法

1.2直接插入排序：

当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置
上的元素顺序后移
数据结构与算法之手撕排序算法
直接插入排序的特性总结：

  1. 元素集合越接近有序，直接插入排序算法的时间效率越高
  2. 时间复杂度：O(N^2)
  3. 空间复杂度：O(1)，它是一种稳定的排序算法
  4. 稳定性：稳定

代码实现：

打印数组中的元素的函数

// 假设都用升序来讲，降序就是反过来

void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; ++i)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

// 插入排序
// 时间复杂度是多少？O(N^2)
// 什么情况下最坏？逆序  1+2+3+...+n-1
// 什么情况下最好？顺序有序  O(N)
void InsertSort(int* a, int n)
{
	// [0, end]有序  end+1位置的值插入[0, end]，让[0, end+1]有序
	for (int i = 0; i < n-1; ++i)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];
				--end;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

void TestInsertSort()
{
	int a[] = { 2,4,1,6,8,3,9,0,-1,9 };
	InsertSort(a, sizeof(a) / sizeof(int));
	printf("InsertSort: ");
	ArrayPrint(a, sizeof(a) / sizeof(int));
}

int main()
{
	TestInsertSort();
	//TestShellSort();
	//TestSelectSort();
	//TestHeapSort();
	//TestBubbleSort();
	//TestPartSort2();

	//TestOP()
	return 0;
}

运行结果：
数据结构与算法之手撕排序算法

1.3 希尔排序( 缩小增量排序 )

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

  1. 希尔排序是对直接插入排序的优化。
  2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
  3. 希尔排序的时间复杂度不好计算，需要进行推导，推导出来平均时间复杂度： O(N1.3—N2）
  4. 稳定性：不稳定

代码实现：

// 直接插入排序的基础上的优化
// 1、先进行预排序，让数组接近有序
// 2、直接插入排序
// 时间复杂度：O(logN*N) 或者 O(log3N*N)
// 平均的时间复杂度是O(N^1.3)
void ShellSort(int* a, int n)
{
	int gap = n;

	while (gap > 1)
	{
		//gap = gap / 2;  // logN
		gap = gap / 3 + 1; // log3N 以3为底数的对数
		// gap > 1时都是预排序  接近有序
		// gap == 1时就是直接插入排序 有序

		// gap很大时，下面预排序时间复杂度O(N)
		// gap很小时，数组已经很接近有序了，这时差不多也是(N)

		// 把间隔为gap的多组数据同时排
		for (int i = 0; i < n - gap; ++i)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}	
}


//希尔排序测试
void TestShellSort()
{
	int a[] = { 2,4,1,6,8,3,9,0,-1,9 };
	ShellSort(a, sizeof(a) / sizeof(int));
	printf("ShellSort: ");
	ArrayPrint(a, sizeof(a) / sizeof(int));
}

int main()
{
	//TestInsertSort();
	TestShellSort();
	//TestSelectSort();
	//TestHeapSort();
	//TestBubbleSort();
	//TestPartSort2();

	//TestOP()
	return 0;
}

运行结果：
数据结构与算法之手撕排序算法

2选择排序

2.1基本思想：

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

2.2 直接选择排序:

在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素
若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换
在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素
数据结构与算法之手撕排序算法
直接选择排序的特性总结：

  1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
  2. 时间复杂度：O(N^2)
  3. 空间复杂度：O(1)
  4. 稳定性：不稳定

代码实现：

//交换函数
void Swap(int* p1, int* p2)
{
	int temp = *p1;
	*p1 = *p2;
	*p2 = temp;
}

// 选择排序
void SelectSort(int* a, int n)
{
	int start = 0;
	int end = n - 1;
	while (start < end)
	{
		int mini = start;
		int maxi = start;
		//找出数组中最大的数和最小的数
		for (int i = start; i <= end; i++)
		{
			if (a[i] < a[mini])
			{
				mini = i;
			}
			if (a[i] > a[maxi])
			{
				maxi = i;
			}
		}
		//把最小的数和start位置的数进行交换
		Swap(&a[start], &a[mini]);
		if (a[start] == a[maxi])
		{
			maxi = mini;
		}
		//把最大的数和end 位置的数交换
		Swap(&a[end], &a[maxi]);
		start++;
		end--;
	}
}

//直接选择排序测试
void TestSelectSort()
{
	int a[] = { 2,4,1,6,8,3,9,0,-1,9 };
	SelectSort(a, sizeof(a) / sizeof(int));
	printf("SelectSort: ");
	ArrayPrint(a, sizeof(a) / sizeof(int));
}
int main()
{
	//TestInsertSort();
	//TestShellSort();
	TestSelectSort();
	//TestHeapSort();
	//TestBubbleSort();
	//TestPartSort2();

	//TestOP()
	return 0;
}

运行结果：
数据结构与算法之手撕排序算法

2.3 堆排序

数据结构与算法之手撕排序算法
数据结构与算法之手撕排序算法
数据结构与算法之手撕排序算法

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
数据结构与算法之手撕排序算法
堆排序的特性总结：

  1. 堆排序使用堆来选数，效率就高了很多。
  2. 时间复杂度：O(N*logN)
  3. 空间复杂度：O(1)
  4. 稳定性：不稳定

代码实现：

// 堆排序

//建堆
void AdjustDwon(int* a, int n, int root)
{
	int parent = root;
	//默认左孩子
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child] < a[child + 1])
		{
			child += 1;
		}

		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void HeapSort(int* a, int n)
{
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDwon(a, n, i);
	}
	int end = n - 1;
	while (end > 0)
	{
		//新堆中的最大数跟最后面那个数交换
		Swap(&a[0], &a[end]);
		AdjustDwon(a, end, 0);
		end--;
	}
}
//堆排序测试
void TestHeapSort()
{
	int a[] = { 2,4,1,6,8,3,9,0,-1,9 };
	HeapSort(a, sizeof(a) / sizeof(int));
	printf("HeapSort: ");
	ArrayPrint(a, sizeof(a) / sizeof(int));
}
int main()
{
	//TestInsertSort();
	//TestShellSort();
	//TestSelectSort();
	TestHeapSort();
	//TestBubbleSort();
	//TestPartSort2();

	//TestOP()
	return 0;
}

代码运行结果：
数据结构与算法之手撕排序算法

3. 交换排序

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

3.1冒泡排序

数据结构与算法之手撕排序算法
冒泡排序的特性总结：

  1. 冒泡排序是一种非常容易理解的排序
  2. 时间复杂度：O(N^2)
  3. 空间复杂度：O(1)
  4. 稳定性：稳定

代码实现：

// 冒泡排序
// 时间复杂度：O（N*N）
// 最好情况:O(N)
// N-1
// N-2
// ...
// 跟直接插入排序相比？谁更好 -》 直接插入更好
void BubbleSort(int* a, int n)
{
	for (int j = 0; j < n; ++j)
	{
		int exchange = 0;
		for (int i = 1; i < n - j; ++i)
		{
			if (a[i - 1] > a[i])
			{
				Swap(&a[i - 1], &a[i]);
				exchange = 1;
			}
		}

		if (exchange == 0)
		{
			break;
		}
	}
}

//冒泡排序测试
void TestBubbleSort()
{
	int a[] = { 2,4,1,6,8,3,9,0,-1,9 };
	BubbleSort(a, sizeof(a) / sizeof(int));
	printf("BubbleSort: ");
	ArrayPrint(a, sizeof(a) / sizeof(int));
}
int main()
{
	//TestInsertSort();
	//TestShellSort();
	//TestSelectSort();
	//TestHeapSort();
	TestBubbleSort();
	//TestPartSort2();

	//TestOP()
	return 0;
}

数据结构与算法之手撕排序算法

3.2 快速排序

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
将区间按照基准值划分为左右两半部分的常见方式有：
数据结构与算法之手撕排序算法
整体实现思想：
数据结构与算法之手撕排序算法
快速排序的特性总结：

  1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
  2. 时间复杂度：O(N*logN)

数据结构与算法之手撕排序算法
3. 空间复杂度：O(logN)
4. 稳定性：不稳定

代码实现：

// 快速排序挖坑法
void PartSort2(int* a, int left, int right)
{
	if (left >= right)
		return;
	int start = left;
	int end = right;
	int pivot = start;
	int key = a[start];
	while (start < end)
	{
		//右边找比key小的数
		while (start < end && a[end] >= key)
		{
			end--;
		}
		//找到后放到坑里去
		a[pivot] = a[end];
		//原来位置变成坑
		pivot = end;
		//左边找比key小的数
		while (start < end && a[start] <= key)
		{
			start++;
		}
		//找到后放到坑里去
		a[pivot] = a[start];
		//原来位置变成坑
		pivot = start;

	}//以上是快排的单趟排序

	pivot = start;
	a[pivot] = key;
	//左子区间和右子区间有序，该序列就有序了，采用分治递归解决
	PartSort2(a, left, pivot - 1);
	PartSort2(a, pivot + 1, right);
}

//快速排序挖坑法测试
void TestPartSort2()
{
	int a[] = { 2,4,1,6,8,3,9,0,-1,9 };
	PartSort2(a, 0,sizeof(a)/sizeof(int)-1);
	printf("PartSort2: ");
	ArrayPrint(a, sizeof(a) / sizeof(int));
}

int main()
{
	//TestInsertSort();
	//TestShellSort();
	//TestSelectSort();
	//TestHeapSort();
	//TestBubbleSort();
	TestPartSort2();

	//TestOP()
	return 0;
}

代码运行结果：
数据结构与算法之手撕排序算法

4.归并排序

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

数据结构与算法之手撕排序算法
数据结构与算法之手撕排序算法
归并排序的特性总结：

  1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
  2. 时间复杂度：O(N*logN)
  3. 空间复杂度：O(N)
  4. 稳定性：稳定

代码实现：

void _MergeSort(int* a, int left, int right, int* tmp)
{
	if (left >= right)
		return;

	int mid = (left + right) >> 1;
	// 假设 [left, mid] [mid+1, right]
	有序，那么我们就可以归并了
	_MergeSort(a, left, mid, tmp);
	_MergeSort(a, mid+1, right, tmp);

	// 归并
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int index = left;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
		{
			tmp[index++] = a[begin1++];
		}
		else
		{
			tmp[index++] = a[begin2++];
		}
	}

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

	while (begin2 <= end2)
	{
		tmp[index++] = a[begin2++];
	}
	
	// 拷贝回去
	for (int i = left; i <= right; ++i)
	{
		a[i] = tmp[i];
	}
}

void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int)*n);
	_MergeSort(a, 0, n - 1, tmp);
	free(tmp);
}

void TestMergeSort()
{
	int a[] = { 2,4,1,6,8,3,9,0,-1,9 };
	MergeSort(a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));
}
int main()
{
	//TestOP();

	//TestShellSort();
	//TestHeapSort();
	//TestSelectSort();
	//TestBubbleSort();
	//TestPartSort2();
	TestMergeSort();

	return 0;
}

代码运行结果：
数据结构与算法之手撕排序算法

我们再来测试一下各个排序之间的性能：

// 测试排序的性能对比
void TestOP()
{
	srand(time(0));
	const int N = 1000000;
	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();
		//a1[i] = i;
		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 begin1 = clock();
	//InsertSort(a1, N);
	int end1 = clock();

	int begin2 = clock();
	ShellSort(a2, N);
	int end2 = clock();

	int begin3 = clock();
	//SelectSort(a3, N);
	int end3 = clock();

	int begin4 = clock();
	HeapSort(a4, N);
	int end4 = clock();

	int begin5 = clock();
	QuickSort(a5, 0, N - 1);
	//QuickSort(a4, 0, N - 1);
	int end5 = clock();

	int begin6 = clock();
	//MergeSort(a6, N);
	int end6 = clock();

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

	printf("InsertSort:%d\n", end1 - begin1);
	printf("ShellSort:%d\n", end2 - begin2);
	printf("SelectSort:%d\n", end3 - begin3);
	printf("HeapSort:%d\n", end4 - begin4);
	printf("BubbleSort:%d\n", end7 - begin7);

	printf("QuickSort:%d\n", end5 - begin5);
	/*printf("MergeSort:%d\n", end6 - begin6);*/

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

}

int main()
{
	TestOP();

	//TestShellSort();
	//TestHeapSort();
	//TestSelectSort();
	//TestBubbleSort();
	//TestQuickSort();
	//TestMergeSort();

	return 0;
}

各个排序算法测试对一百万个数排序所消耗的时间为：
数据结构与算法之手撕排序算法

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

数据结构与算法之手撕排序算法
总结：
各个排序算法有各个排序算法的不同使用场景，但是整体来说快排更有优势，所以快排更为常用。文章来源地址https://www.toymoban.com/news/detail-415099.html

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

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

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

相关文章

  • 排序算法终极篇之手撕常见排序算法

    排序算法终极篇之手撕常见排序算法

       文章目录 引入 一、插入排序 1、1 插入排序的实现思想 1、2 插入排序的代码实现及特点分析  二、希尔排序 2、1 希尔排序的实现思想 2、2 希尔排序的代码实现及特点分析  三、选择排序 3、1 选择排序的实现思想 3、2 选择排序的代码实现及特点分析 四、堆排序 五、冒泡

    2023年04月16日
    浏览(38)
  • [数据结构 -- 手撕排序算法第七篇] 递归实现归并排序

    [数据结构 -- 手撕排序算法第七篇] 递归实现归并排序

    目录 1、归并的思想 2、归并排序的思想 2.1 基本思想 2.2 图解分析 3、归并排序递归版本代码实现 3.1 代码解析 3.2 注意事项 3.2.1错误划分：[begin, mid-1]，[mid, end] 3.2.2 正确划分：[begin, mid], [mid+1, end] 4、归并排序的测试 5、时间复杂度、空间复杂度分析 5.1 时间复杂度 5.2 空间复杂

    2024年02月16日
    浏览(45)
  • 【数据结构与算法篇】手撕八大排序算法之快排的非递归实现及递归版本优化(三路划分)

    【数据结构与算法篇】手撕八大排序算法之快排的非递归实现及递归版本优化(三路划分)

    ​👻内容专栏： 《数据结构与算法篇》 🐨本文概括： 利用数据结构栈(Stack)来模拟递归，实现快排的非递归版本；递归版本测试OJ题时，有大量重复元素样例不能通过，导致性能下降，优化快速排序通过将数组划分为三个区域，可以更有效地处理重复元素。 🐼本文作者：

    2024年02月11日
    浏览(81)
  • [数据结构 -- 手撕排序算法第六篇] 递归实现快速排序（集霍尔版本，挖坑法，前后指针法为一篇的实现方法，很能打）

    [数据结构 -- 手撕排序算法第六篇] 递归实现快速排序（集霍尔版本，挖坑法，前后指针法为一篇的实现方法，很能打）

    目录 1、常见的排序算法 1.1 交换排序基本思想 2、快速排序的实现方法 2.1 基本思想 3 hoare（霍尔）版本 3.1 实现思路 3.2 思路图解 3.3 为什么实现思路的步骤2、3不能交换 3.4 hoare版本代码实现 3.5 hoare版本代码测试 4、挖坑法 4.1 实现思路 4.2 思路图解 4.3 挖坑法代码实现 4.4 挖坑

    2024年02月16日
    浏览(44)
  • 【数据结构】手撕排序

    【数据结构】手撕排序

    🔥 博客主页 ： 小羊失眠啦. 🎥 系列专栏 ： 《C语言》 《数据结构》 《Linux》 《Cpolar》 ❤️ 感谢大家点赞👍收藏⭐评论✍️ 排序 ：所谓排序就是使一串记录，按照其中的某个或某些的大小， 递增或递减 的排列起来的操作。排序算法，就是如何使得记录按照要求

    2024年02月05日
    浏览(49)
  • [数据结构 -- 手撕排序第三篇] 冒泡排序

    [数据结构 -- 手撕排序第三篇] 冒泡排序

    目录 1、常见的排序算法 1.1 交换排序基本思想 2、冒泡排序的实现 2.1 基本思想 2.2 单趟排序 2.2.1 单趟排序分析 2.2.2 单趟排序实现代码 3、冒泡排序完整代码实现 3.1 思路分析 3.2 代码实现 4、时间复杂度 5、优化算法 5.1 优化算法思路 5.2 优化算法代码实现 6、冒泡排序的特性总

    2024年02月13日
    浏览(44)
  • [数据结构 -- 手撕排序第一篇] 插入排序

    [数据结构 -- 手撕排序第一篇] 插入排序

    目录 1、常见的排序算法 2、插入排序的思路 2.1 基本思想 2.2 直接插入排序 2.2.1 单趟排序的思路 2.2.2 单趟排序代码实现 3、插入排序代码 4、插入排序+打印测试 5、插入排序的时间复杂度 5.1 最坏情况 5.2 最好情况 6、直接插入排序的特性总结   直接插入排序是一种简单的插入

    2024年02月12日
    浏览(53)
  • 【数据结构】手撕排序NO.1----排序初识

    【数据结构】手撕排序NO.1----排序初识

    目录  一. 前言 二. 排序的概念及运用         2.1 排序的概念         2.2 排序的运用         2.3 常见的排序算法 三. 冒泡and选择排序         3.1 冒泡排序         3.2 选择排序 四. 各大排序算法的复杂度和稳定性        从本期开始，我们的数据结构将迎来一个新的

    2024年02月16日
    浏览(54)

  • 【算法与数据结构】--前言

    欢迎来到《算法与数据结构》专栏！这个专栏将引领您进入计算机科学领域中最重要、最精彩的领域之一：算法与数据结构。不管您是一名初学者，还是已经拥有一定编程经验的开发者，都可以从这里找到有益的知识和实践。 在计算机科学的世界里，算法和数据结构是至关重

    2024年02月07日
    浏览(245)
  • 【数据结构】手撕归并排序（含非递归）

    【数据结构】手撕归并排序（含非递归）

    目录 一，归并排序（递归） 1，基本思想  2，思路实现 二，归并排序（非递归） 1，思路实现 2，归并排序的特性总结： 1，基本思想 归并排序 （MERGE-SORT） 是建立在 归并操作 上的一种 有效的排序算法 ,该算法是采用 分治法（Divide and Conquer） 的一个非常典型的应用； 将 已

    2024年02月08日
    浏览(46)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包