常见的排序算法

07-14 1569阅读

1.排序的概念及其运用

1.1排序的概念

1.排序：排序简而言之就是使一串记录，按照其中某个或者某些关键词的大小对其进行升序或降序排列

2.稳定性：在一串序列中需要根据某些关键词大小进行排序的序列，但两个关键词大小相同，在不将原来序列中关键词大小相同的两个的前后顺序调换的排序就是稳定的

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

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

1.2排序的运用

在生活中很多都需要用到排序算法，比如学生成绩的排序，手机销量的排序，抖音热榜的排序

2.常见的排序算法

2.1冒泡排序

算法思想：

将最大或者最小的数据元素排到最后

算法实现：

void BubbleSort(int* a, int n)
{
	int flag = 0;
	for (int i = 0; i  a[j + 1])
			{
				Swap(&a[j], &a[j + 1]);
				flag = 1;
			}
		}
		if (flag == 0)
		{
			break;
		}
	}
}

复杂度分析

时间复杂度：

最好：O(N)

最坏：O(N^2)

空间复杂度：O(1)

2.2选择排序

算法思想：

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

这里我将其优化了一下，及在待排序序列中找到最大和最小的数据元素，分别将其排到序列的起始位置和最后位置。

算法实现:

void SelectSort(int* a, int n)
{
	int end = n - 1;
	int begin = 0;
	while (begin  
复杂度分析 
时间复杂度
最好：O(N^2)
最坏：O(N^2)
空间复杂度：O(1) 
2.3直接插入排序 
算法思想： 
将为排序的数据元素插入到已排序序列中进行排序，如：排升序时，排到第i个元素时，前面i-1个元素已经排好序了，将第i个元素与第i-1个元素相比较，如果大于第i-1个元素，就不需要继续比较，如果小于第i-1个元素，交换两个元素，在将其于第i-2个元素比较，以此类推直到整个序列排序完成。
 
算法实现： 
void InsertSort(int* a, int n)
{
	for (int i = 0; i = 0)
		{
			if (tmp  
复杂度分析 
时间复杂度：
最好：O(N)
最坏：O(N^2)
空间复杂度：O(1) 
2.4希尔排序 
算法思想： 
希尔排序的思想和直接插入排序的思想有异曲同工之妙，希尔排序就是在直接插入排序上做了一些优化，先对代拍序列进行预排序，减小预排序之间gap的大小，知道为1，为直接插入排序，但由于序列i已经部分有序，直接插入排序的时间复杂度也大幅度降低
 
算法实现： 
void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap/3 + 1;
		for (int i = 0; i = 0)
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}
 
复杂度分析 
时间复杂度：
最好：O(NlogN)（具体来说是O(N^1.3)根据大量实验测得）
最坏：O(N^2)
空间复杂度·：O(1) 
2.5快速排序 
2.5.1hoare版本 
算法思想： 
定义两个变量left和right,分别指向区间的开头和结尾，定义一个变量key值，key值为数组所在区间的第一个值a[left],在从right开始想左找比key值小的元素，找到了再从left开始向右找比key值大的元素，找到了在将两个数交换，直到left>=right就跳出循环
 
算法实现： 
void QuickSort(int* a , int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int begin = left;
	int end = right;
	int keyi = left;
	while (left = a[keyi])
		{
			right--;
		}
		while (left = a[keyi])
		{
			right--;
		}
		while (left = right)
	{
		return;
	}
	//小区间优化
	if (right - left + 1 = a[keyi] && left =a[keyi]，cur++，否则，prev++，交换a[cur]和a[prev]，cur++，直到循环结束，交换a[prev]和a[keyi] 
算法实现： 
void quicksort(int* a, int left, int right)
{
	while (left >= right)
	{
		return;
	}
	int keyi = left;
	int prev = left;
	int cur = left;
	while (cur 
		if (a[cur] = key && left