八大排序算法

发布于：2025-08-04 ⋅ 阅读:(19) ⋅ 点赞:(0)

前言

        排序是计算机科学中最基础、应用最广泛的算法之一。它将一组无序的数据元素（或记录）按照某种特定的顺序（如升序或降序）重新排列，是数据检索、统计分析、高效算法设计等众多领域的基石。本章总结了学习过程中八大排序算法，包括比较排序和非比较排序。如图所示：

一、插入排序

1.1直接插入排序

当插⼊第 i(i>=1) 个元素时，前⾯的 array[0],array[1],…,array[i-1] 已经排好序，此时⽤ array[i] 的排序码与 array[i-1],array[i-2],… 的排序码顺序进⾏⽐较，找到插⼊位置即将 array[i] 插⼊，原来位置上的元素顺序后移（归根结底就是前面数据都是顺序的，插入的与前面数据进行比较大小，然后交换，成为有序。进而继续将下一个数据为待插入数据，继续比较以此类推而得到有序排列）。

 

//直接插入排序
void InsertSort(int* arr, int num)
{
	for (int i = 0; i < num; i++)
	{
		int end = i;
		int tmp = arr[end];
		while (end > 0)
		{
			//tmp < arr[end-1]将end上的位置给end-1
			if (tmp < arr[end - 1])
			{
				arr[end] = arr[end - 1];
				end--;
			}
			//tmp >= arr[end-1]不移动
			else
			{
				break;
			}
		}
		arr[end] = tmp;
	}
}
1. 元素集合越接近有序，直接插⼊排序算法的时间效率越⾼
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)

1.2希尔排序

希尔排序法⼜称缩⼩增量法。希尔排序法的基本思想是：先选定⼀个整数（通常是gap = n/3+1），把待排序⽂件所有记录分成各组，所有的距离相等的记录分在同⼀组内，并对每⼀组内的记录进⾏排序，然后gap=gap/3+1得到下⼀个整数，再将数组分成各组，进⾏插⼊排序，当gap=1时，就相当于直接插⼊排序（希尔排序用途就是为了将小的数据放到前面，顺便将大的数据放入后面，以达到直接插入排序排序次数大幅度减少）。 
void ShellSort(int* arr, int num)
{
	int gap = num;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		//将数组后面小的数据移动到前面，大幅减少次数
		for (int i = 0; i < num-gap; i++)
		{
			int end = i;
			int tmp = arr[end+gap];
			while (end >= 0)
			{
				if (arr[end] > tmp)
				{
					arr[end+gap] = arr[end];//将大的数据arr[end]移动到end+gap位置上
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end+gap] = tmp;
		}
	}
}
1. 希尔排序是对直接插⼊排序的优化。
2. 当 gap > 1 时都是预排序，⽬的是让数组更接近于有序。当 gap == 1 时，数组已经接近有序的了，这样就会很快。这样整体⽽⾔，可以达到优化的效果。

二、选择排序

2.1直接选择排序

每⼀次从待排序的数据元素中选出最⼩（或最⼤）的⼀个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 (在一段序列中不断寻找最大最小值，并将最大移到右边，将最小移到左边)。

 

void Swap(int* change1, int* change2)
{
	int tmp = *change1;
	*change1 = *change2;
	*change2 = tmp;
}
void SelectSort(int* arr, int num)
{
	int right = num-1;
	int left = 0;
	while (left < right)//等于时跳出
	{
		//这里设置是为了后面改变right和left时可以把初始值改变
		int max = right;
		int min = left;
		//寻找最大值
		for (int i = left+1; i <= right;i++)
		{
			if (arr[i] > arr[max])
			{
				max = i;
			}
			if (arr[i] < arr[min])
			{
				min = i;
			}
		}
		//接下来就是分别插入到最大最小到right和left
		Swap(&arr[left], &arr[min]);
		//这里发现只要arr[left]和max重合时才会使得max下标指的最小值，因此这里需要条件限制
		if (left == max)
		{
			max = min;
		}
		Swap(&arr[right], &arr[max]);
		left++;
		right--;
	}
}

这里需要注意的是left和max相同时需要避免把最大值和最小值调换，但是这里还要顺序可言，不能把这个条件判断放到最小值交换过程（这里因为时未来避免最小值不在right上，但是max和min相同，导致排序错误）。 

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

2.2堆排序

堆排序(Heapsort)是指利⽤堆积树（堆）这种数据结构所设计的⼀种排序算法，它是选择排序的一种。它是通过堆来进⾏选择数据。需要注意的是排升序要建⼤堆，排降序建⼩堆。（走个过程，详细 堆数据结构_堆 数据结构-CSDN博客 ） 
void AdjustDown(int* arr,int parent,int num)
{
	int child = parent * 2 + 1;
	while (child < num)
	{
		//建大堆 <
		if (child+1 < num && arr[child] < arr[child + 1])
		{
			child++;
		}
		//大堆 <
		if (arr[parent] < arr[child])
		{
			Swap(&arr[parent], &arr[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
//堆排序
void HeapSort(int* arr,int num)
{
	//向下建堆
	for (int i = (num - 1 - 1) / 2; i >= 0; i--)
	{
		//利用堆思想筛选最值
		AdjustDown(arr, i,num);
	}
	//筛选最大值
	for (int i = num - 1; i > 0; i--)
	{
		Swap(&arr[0], &arr[i]);
		//调整堆
		AdjustDown(arr, 0, i);
	}

}
1. 时间复杂度： O (n*log   )以至于效率非常快
2. 空间复杂度： O (1)

三、交换排序

3.1冒泡排序

冒泡排序（Bubble Sort）是一种简单直观的排序算法。它通过重复地遍历要排序的数列，一次比较两个相邻的元素，如果它们的顺序错误就交换它们的位置。这个过程会一直重复，直到没有需要交换的元素为止，也就是说数列已经排序完成（不断比较当前下标和下边的下一个进行对比，把筛选的数据对换）

void Swap(int* change1, int* change2)
{
	int temp = *change1;
	*change1 = *change2;
	*change2 = temp;
}

void BubbleSort(int* arr, int num)
{
	for (int i = num - 1; i > 0; i--)
	{
		int flag = 1;//表示排序完成
		for (int j = 0; j <= i-1; j++)//这里i-1是因为后续j+1不越界
		{
			if (arr[j] > arr[j + 1])
			{
				Swap(&arr[j], &arr[j + 1]);
				flag = 0;
			}
		}
		if (flag == 1)
		{
			break;
		}
	}
}
1. 时间复杂度： O ( N 2 )
2. 空间复杂度： O (1)

3.2快速排序

快速排序是Hoare于1962年提出的⼀种⼆叉树结构的交换排序⽅法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两⼦序列，左⼦序列中所有元素均⼩于基准值，右⼦序列中所有元素均⼤于基准值，然后最左右⼦序列重复该过程，直到所有元素都排列在相应位置上为⽌（寻找基准值，将小于基准值的放到左边，大于等于基准值的放到右边，然后不断寻找基准值重复，这样排序就完成了）。

递归版本： 

//快速排序
void QuickSort(int* arr, int left, int right)
{
	//递归结束条件
	if (left > right)
	{
		return;
	}
	int keyi = Find(arr,left,right);//寻找基准值
	//左子树
	QuickSort(arr, left, keyi-1);
	QuickSort(arr, keyi + 1, right);
}

非递归版本：

 非递归版本需要保留左右子树的区间进行寻找基准值，这里我们可以使用数据结构栈和队列，为了便利，这里我们使用栈数据结构：

 

//快速排序（非递归）
void QuickSort(int* arr, int left, int right)
{
	ST st;
	StackInit(&st);
	StackPush(&st,left);
	StackPush(&st,right);
	//跳出条件
	while (!StackEmpty(&st))
	{
		int end = StackTop(&st);
		StackPop(&st);
		int begin = StackTop(&st);
		StackPop(&st);
		//寻找基准值
		int key = begin;
		int prev = begin; int cur = prev + 1;
		while (cur <= end)
		{
			if (arr[key] > arr[cur] && ++prev != cur)
			{
				Swap(&arr[prev], &arr[cur]);
			}
			cur++;
		}
		//找到
		Swap(&arr[key], &arr[prev]);
		key = prev;
		//插入左子树
		if(begin < key-1)
		{
			StackPush(&st, begin);
			StackPush(&st, key - 1);
		}
		if (key + 1 < end)
		{
			StackPush(&st, key + 1);
			StackPush(&st, end);
		}
	}
	//执行完销毁
	StackDestory(&st);
}

3.2.1基准值寻找方法

hoare法:

  

 

//寻找基准值
int Find(int* arr, int left, int right)
{
	int keyi = left;
	left++;
	while (left <= right)
	{
		//left寻找比基准值大
		while (left <= right && arr[left] < arr[keyi])
		{
			left++;
		}
		//right寻找比基准值小的
		while (left <= right && arr[right] > arr[keyi])
		{
			right--;
		}
		//出现left >right
		if (left <= right)
		{
			//找到了对应的值(交换)
			Swap(&arr[left], &arr[right]);
		}
	}
	//找到基准值下标
	Swap(&arr[keyi], &arr[right]);
	return right;
}

//快速排序
void QuickSort(int* arr, int left, int right)
{
	//递归结束条件
	if (left > right)
	{
		return;
	}
	int keyi = Find(arr,left,right);//寻找基准值
	//左子树
	QuickSort(arr, left, keyi-1);
	QuickSort(arr, keyi + 1, right);
}

挖坑法（很少用）：

创建左右指针。⾸先从右向左找出⽐基准⼩的数据，找到后⽴即放⼊左边坑中，当前位置变为新
的"坑"，然后从左向右找出⽐基准⼤的数据，找到后⽴即放⼊右边坑中，当前位置变为新的"坑"，结束循环后将最开始存储的分界值放⼊当前的"坑"中，返回当前"坑"下标（即分界值下标） 

//挖坑法
int Find(int* arr, int left, int right)
{
	int keyi = left;
	int temp = arr[keyi];
	int hole = left;
	while (left < right)
	{
		//right寻找比temp小
		while (left < right && arr[right] >= temp)//这里要等于是为了怕temp=arr[right]时后续填坑无实际意义，反而会导致死循环
		{
			right--;
		}
		//找到后，插入到hole这个洞中
		arr[hole] = arr[right];
		hole = right;
		//接下来left寻找比temp大的(right位置为空)
		while (left < right && arr[left] <= temp)
		{
			left++;
		}
		arr[hole] = arr[left];
		hole = left;
	}
	//寻找基准值
	//把洞补齐
	arr[hole] = temp;
	return right;
}

//快速排序
void QuickSort(int* arr, int left, int right)
{
	//递归结束条件
	if (left > right)
	{
		return;
	}
	int keyi = Find(arr,left,right);//寻找基准值
	//左子树
	QuickSort(arr, left, keyi-1);
	QuickSort(arr, keyi + 1, right);
}

lomuto前后指针法：

创建前后指针，从左往右找⽐基准值⼩的进⾏交换，使得⼩的都排在基准值的左边（和冒泡排序中的比较方法差不多，就是比较前（基准）后（数据）大小。在寻找比基准值小和基准值交换，然后把基准值移动，最前面的是试探指针，还有一个是用于把试探到比基准值小的数进行交换到）

 

//lomuto前后指针法
int Find(int* arr, int left, int right)
{
	int prev = left; int cur = prev + 1;
	int i = left;
	while (cur <= right)
	{
		if (arr[cur] < arr[i])
		{
			//先++prev再交换
			++prev;
			Swap(&arr[cur], &arr[prev]);
		}
		cur++;
	}
	//最后找到基准值下标
	Swap(&arr[prev], &arr[i]);
	return prev;
}

//快速排序
void QuickSort(int* arr, int left, int right)
{
	//递归结束条件
	if (left >= right)
	{
		return;
	}
	int keyi = Find(arr,left,right);//寻找基准值
	//左子树
	QuickSort(arr, left, keyi-1);
	QuickSort(arr, keyi + 1, right);
}
1. 时间复杂度： O ( nlogn )
2. 空间复杂度： O ( logn )
对于非递归时间复杂度：O( _n{}^{2} )，而空间复杂度就变为o(1)

四、归并排序

4.1归并排序

归并排序（MERGE-SORT）是建⽴在归并操作上的⼀种有效的排序算法,该算法是采⽤分治法（Divide and Conquer）的⼀个⾮常典型的应⽤。将已有序的⼦序列合并，得到完全有序的序列；即先使每个⼦序列有序，再使⼦序列段间有序。若将两个有序表合并成⼀个有序表，称为⼆路归并（就是通过二分不断将无序变为一个数据，此时就是有序数据了，然后通过之前学到的合并两个有序序列，不断合并为有序）。

 

递归版： 

//归并排序
void MergeSort(int* arr, int left, int right,int* tmp)
{
	//递归结束条件
	if (left >= right)
	{
		return;
	}
	int mid = (left + right) / 2;
	MergeSort(arr, left, mid,tmp);
	MergeSort(arr, mid + 1, right,tmp);

	//合并有序
	int begin1 = left; int end1 = mid;
	int begin2 = mid + 1; int end2 = right;
	int index = left;//计数
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] > arr[begin2])
		{
			tmp[index++] = arr[begin2++];
		}
		else
		{
			tmp[index++] = arr[begin1++];
		}
	}
	//begin1 end1 还有没比较的数据
	while (begin1 <= end1)
	{
		tmp[index++] = arr[begin1++];
	}
	//begin2 end2 还有没比较的
	while (begin2 <= end2)
	{
		tmp[index++] = arr[begin2++];
	}
	//将tmp数组数据放入到arr中
	while (left <= right)
	{
		arr[left]=tmp[left];
		left++;
	}
}
void test01()
{
	int arr[] = { 10,6,7,1,3,9,4,2 };
	int size = sizeof(arr) / sizeof(arr[0]);
	int* newarr = malloc(sizeof(arr));
	if (newarr == NULL)
	{
		return;
	}
	MergeSort(arr, 0, size - 1,newarr);
	//释放置空
	free(newarr);
	newarr = NULL;
	for (int i = 0; i < size; i++)
	{
		printf("%d ", arr[i]);
	}
}

非递归版本 ：

void MergeSort(int *arr,int num)
{
	int* tmp = (int*)malloc(sizeof(int) * num);
	if (tmp == NULL)
	{
		return;
	}
	int gap = 1;//一个区间元素个数
	while (gap < num)
	{
		//寻找归并元素
		for (int i = 0;i < num ;i += 2*gap)
		{
			int begin1 = i, end1 = i+ gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
            int index = begin1;
			//奇数
			if (begin2 >= num)//没有右序列
			{
				break;
			}
			if (end2 >= num)//右序列不满gap个
			{
				end2 = num-1;
			}
			//偶数
			//归并
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (arr[begin1] < arr[begin2])
				{
					tmp[index++] = arr[begin1++];
				}
				else
				{
					tmp[index++] = arr[begin2++];
				}
			}
			//begin1
			while (begin1 <= end1)
			{
				tmp[index++] = arr[begin1++];
			}
			//begin2
			while (begin2 <= end2)
			{
				tmp[index++] = arr[begin2++];
			}
			//放入原数组
			memcpy(arr + i, tmp + i, sizeof(int) * (end2-i+1));
		}
		gap *= 2;
	}
	free(tmp);
	tmp = NULL;
}
1. 时间复杂度： O ( nlogn)
2. 空间复杂度： O ( n )

五、计数排序

5.1计数排序

计数排序⼜称为鸽巢原理，是对哈希直接定址法的变形应⽤。 操作步骤：
1）统计相同元素出现次数
2）根据统计的结果将序列回收到原来的序列中
(这个计数排序就是通过记每个元素出现的个数放入一个数组中，这个数组的下标可以表示为排序数组中数据的元素，进而通过遍历记入出现元素个数的数组，遍历得到有序数组)。 
void CountSort(int* arr, int num)
{
	//寻找最值
	int min = arr[0]; int max = arr[0];
	for (int i = 0; i < num; i++)
	{
		if (arr[i] > max)
		{
			max = arr[i];
		}
		if (arr[i] < min)
		{
			min = arr[i];
		}
	}
	//创造为max-min+1个空间用于存储arr出现元素个数
	int range = max - min + 1;
	int* count = (int*)calloc(range, sizeof(int));
	if (count == NULL)
	{
		perror("calloc fail");
		return;
	}
	//计数
	for (int i = 0; i < num; i++)
	{
		count[arr[i]- min]++;
	}
	//排序
	int index = 0;
	for (int j = 0; j < range; j++)
	{
		while (count[j])
		{
			arr[index++] = min+j;
			count[j]--;
		}
	}
}
1. 计数排序在数据范围集中时，效率很⾼，但是适⽤范围及场景有限(对于范围比较大的数据如1到1万中中间数据没有或者很少，效率会很慢)。
2. 时间复杂度： O ( N + range )
3. 空间复杂度： O ( range )

六、排序复杂度和稳定性

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，⽽在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的（归根结底就是排序过程中遇到相同的元素时，看是否相对位置发生变化，如果第一个r[i]还在r[j]前面那就稳定的，反则不稳定）。
排序方法 时间平均情况 时间最好情况 时间最坏情况 空间复杂度 稳定性
冒泡排序 O(N_{}^{2}) O(N_{}^{2}) O(N_{}^{2}) O(1) 稳定
快速排序 O(N\log N) O(N\log N) O(N_{}^{2}) O(\log N)~O(N) 不稳定
直接插入排序 O(N_{}^{2}) O(N) O(N_{}^{2}) O(1) 稳定
希尔排序 O(N\log N)~O(N_{}^{2}) O(N^{1.3}) O(N_{}^{2}) O(1) 不稳定
直接选择排序 O(N_{}^{2}) O(N_{}^{2}) O(N_{}^{2}) O(1) 不稳定
堆排序 O(N\log N) O(N\log N) O(N\log N) O(1) 不稳定
归并排序 O(N\log N) O(N\log N) O(N\log N) O(N) 稳定
计数排序 O(N+range) O(N+range) O(N_{}^{2}) O(range) 稳定

 

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布