【常见的六大排序算法】插入排序、希尔排序、选择排序、冒泡排序、堆排序、快速排序

个人主页
创作不易，感谢大家的关注！

前言

在实现排序前，我们要先知道什么是排序。排序：简单的来说就是把一串数据按照一定的方式依次排序。例如：可以按照数字的大小升序或降序排列，或者按照英文字母的先后顺序排列等。使用这一系列的方式，就可以将一串无序状态下的数据排列成有序的数据。

🎡一、插入排序

1. 基本思路：

   1. 默认第一个元素为有序的，从第二个元素开始排序。
   2. 取出下一个元素tmp，往前进行比较。
   3. 如果该元素比tmp大，则将该元素往后移动一位，直到找到比tmp小于或者等于的元素。
   4. 找到比tmp小于或者等于的元素，将tmp插入到该元素的下一位。
   5. 不断重复上述步骤。

2. 动图演示：
   

3. 时间复杂度： 最坏情况下为 O(N ^ 2)，此时待排序的序列状况为逆序或者接近逆序。最好情况下为 O(N)，此时待排序列为升序，或者说接近升序。

4. 空间复杂度： O(1)。

代码实现：

// 插入排序
void InsertSort(int* a, int n)
{
    //遍历数组
	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;
			}
		}
		//将tmp放到比插入的数小的后面
		a[end + 1] = tmp;
	}
}

🌲二、希尔排序

1. 基本思路：

   希尔排序是插入排序的一个优化方案，其本质上还是插入排序。但它们的时间复杂度却并不相同。

   1. 先将待排序列进行预排序，使得待排序列接近有序，然后再进行插入排序。
   2. 将待排序的数据分为多个组，使每组间隔gap为2或3…。
   3. 如果第一个元素大于最后一个元素，则将它们两个元素进行交换。
   4. 不断重复上述操作，直到每组间隔只有1时，说明所有的数据已经完成排序。

2. 动图演示：

3. 时间复杂度： O(N ^ 1.3)。

4. 空间复杂度： O（1）。

代码实现：

// 希尔排序
void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		// +1保证当n的值小于3时，gap最低为1，依次进行插入排序
		gap = gap / 3 + 1;
		for (size_t i = 0; i < n - gap; i += gap)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];
					end = end - gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}

🎉三、选择排序

1. 基本思路：
   1. 从待排序序列中选出最小值mini，放在序列的起始位置。
   2. 每次遇到比mini小的值就更新mini，直到遍历完整个序列。
   3. 然后将该值放到序列的排列好的有序序列的下一个位置。
   4. 重复上述步骤，直到待排序只剩下一个元素，说明排序完成。
2. 动图演示：
   
3. 时间复杂度： O（N^2）。有n个数，每趟选一个最大或最小值，需要选n趟。
4. 空间复杂度： O（1）。

代码实现

// 选择排序
void SelectSort(int* a, int n)
{
	//定义一个begin和end分别指向数组的头下标和尾下标
	int begin = 0;
	int end = n - 1;
	while (begin < end)
	{
		//定义mini和begin分别表示最小值和最大值的下标
		int mini = begin, maxi = begin;
		for (int i = begin + 1; i <= end; i++)
		{
			if (a[i] > a[maxi])
				maxi = i;
			if (a[i] < a[mini])
				mini = i;
		}
		Swap(&a[begin], &a[mini]);
		//需要注意的是，当最大值在最小值位置的时候，a[maxi]的值会与a[mini]的值进行交换，因此需要提前将maxi置为mini
		if (begin == maxi)
		{
			maxi = mini;
		}
		Swap(&a[end], &a[maxi]);
		begin++;
		end--;
	}
}

总结： 效率相对较低，实际中很少使用。

🎀四、冒泡排序

1. 基本思路：
   根据序列中两个记录键值的比较结果来交换这两个记录在序列中的位置，一前一后两个下标的值进行比较，如果前一个值比后一个值大就进行交换。
2. 动图演示：
3. 时间复杂度： O（N ^2）。该排序每次都要和相邻的两个数进行比较，最坏情况下比较n次，跑n躺。
4. 空间复杂度： O（1）。

代码实现：

// 冒泡排序
void BubbleSort(int arr[], int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		//假设没有发生判断，如果发生判断，就将flag置为，否则就退出
		int flag = 0;
		for (int j = 0; j < n - 1 - i; j++)
		{
			int tmp = 0;
			tmp = arr[j];
			arr[j] = arr[j + 1];
			arr[j + 1] = tmp;
			flag = 1;
		}
		if (flag == 0)
		{
			break;
		}
	}
}

结论： 该排序效率低下，实际中几乎不使用。

🚘五、堆排序

1. 基本思路：
   将一组无序的数据，按照升序或降序的方式对其进行排序。
   注意： 在堆排序中，升序建大堆，降序建小堆。 因为堆排序的逻辑是将根节点与最后一个节点依次发生交换。不断交换，大堆排序完，堆尾的数据就是最大的值，并且不断向堆顶的数据依次缩小；相反，小堆排序完后，堆尾的数据就是最小的值，并不断向堆顶的数据依次增大。
2. 图片演示：
3. 时间复杂度： O（N * log(N)）堆排序建堆的时间复杂度为O（N），但是选数时都需要将堆顶和堆尾的数据进行交换，而堆的高度是log（N），而建堆的时间复杂的可以忽略不计，因此为O（N * log(N)）。
4. 空间复杂度： O（1）。

代码实现：

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

// 向下调整排序
void AdjustDown(int* a, int n, int parent)
{
	//假设左孩子大
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child + 1] < a[child])
		{
			child++;
		}
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

//堆排序
//假设使用建小堆的方法
void HeapSort(int* a, int n)
{
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}

总结： 排序效率高，实际中也可以使用。

🛵六、快速排序

一般我们使用快速排序方法的顺序：挖坑法 -> Hoare -> 前后指针法。

1. Hoare版本

1. 基本思路：
   1. 选出一个key，一般在最左边或在最右边。
   2. 定义一个begin为序列的头和end为序列的尾，begin从左向右开始走，end从右向左进行走。（注意： 如果选择最左边的数据为key，则需让end先走；若选择右边的数据为key，则让begin先走）
   3. 假设最左边为key，end开始先走。在走的过程中，如果end遇到比key小的数据，就停下，然后让begin开始走，直到begin遇到比key大的数据就停下，然后将begin里的值和end里的值进行交换，然后又继续从end开始先走，不断循环往复，直到begin和end相遇，则将相遇点的内容和key进行交换即可。
   4. 此时，key左边的数据都是小于key的，key右边的数据都是大于key的，说明key已在序列中排好序了。
   5. 因此，序列中划分出了三个区间，分别为 [left, key - 1],key,[key + 1, right] 这三个区间，然后不断对[left, key - 1]和[key + 1, right]这两个区间重复上述步骤，直到所有的key都排好序。
2. 单趟的动图演示如下：
   
   代码实现：

// 快速排序
void QuickSort(int* a, int left,int right)
{
	//只有一个数或区间不存在
	if (left >= right)
	{
		return;
	}

	int begin = left, end = right;
	while (begin < end)
	{
		//右边找小，begin < end是为了防止越界
		while (begin < end && a[end] >= a[keyi])
		{
			end--;
		}
		//左边找大
		while (begin < end && a[begin] <= a[keyi])
		{
			++begin;
		}
		//小的换到右边，大的换到左边
		Swap(&a[begin], &a[end]);
	}
	Swap(&a[keyi], &a[begin]);
	// [left,keyi-1] keyi [keyi+1,right]，使用递归的方法
	QuickSort(a, left, keyi - 1);
	QuickSort(a, keyi + 1, right);
}

代码优化：
在实际中，我们发现：快速排序在有序或接近有序数组中完成排序的效率低下。因此我们可以采用每次都取大小中等的值来作为数组中最左边的key，这样可以有效提升代码的运行效率，减少循环的次数。

// 三数取中
int GetMidi(int* a, int left, int right)
{
	int midi = (left + right) / 2;
	if (a[left] < a[midi])
	{
		if (a[midi] < a[right])
			return midi;
		else if (a[left] < a[right])
			return right;
		else
		{
			return left;
		}
	}
	// a[left] > a[midi]
	else
	{
		if (a[midi] > a[right])
			return midi;
		// a[midi] < a[right]
		else if (a[left] < a[right])
			return left;
		else
			return right;
	}
}

2. 挖坑法

1. 基本思路：
   1. 选出最左边的元素存入key中，在此位置中形成一个坑位。
   2. 定义left从左到右开始遍历，定义right从右向左开始遍历。
   3. 当right遍历找到比key小的数据，就放入left当中的位置。
   4. 当left遍历找到比key大的数据，就放入right当中的位置
   5. 如果left和right下标相遇，则把key中的数据放入相交处。
2. 单趟动图演示：
   
   代码实现：

//挖坑法
int QuickSort1(int* a, int left, int right)
{
	int midi = GetMidi(a, left, right);
	Swap(&a[left], &a[midi]);
	midi = left;
	int key = a[midi];
	while (left < right)
	{
		// 左右开始遍历
		while (left < right && a[right] >= key)
		{
			--right;
		}
		a[midi] = a[right];
		midi = right;
		while (left < right && a[left] <= key)
		{
			++left;
		}
		a[midi] = a[left];
		midi = left;
	}
	a[midi] = key;
	return midi;
}

3. 前后指针法

1. 基本思路：
   1. 定义key来存储数组中最左边的数据，perv指向数组开始的位置，cur指向prev的下一个位置。
   2. 当cur下标中的元素小于key时，则让prev开始往后走。如果此时prev下标中的元素不等于cur下标中的元素，则两者进行交换。
   3. 否则cur一直往下走，当cur走完时，将prev下表中的元素和key中的数据进行交换
   4. 不断重复上述操作。
2. 单趟动图演示：
   
   代码实现：

//前后指针法
int QuickSort2(int* a, int left, int right)
{
	assert(a);
	int keyi = GetMidi(a, left, right);
	Swap(a[keyi], a[left]);
	keyi = left;
	int prev = left;
	int cur = prev + 1;
	while (cur <= right && a[cur] < a[keyi])
	{
		++prev;
		++cur;
	}
	while (cur <= right)
	{
		while (cur <= right && a[cur] >= a[keyi])
		{
			++cur;
		}
		if (cur <= right)
		{
			++prev;
			Swap(a[prev], a[cur]);
		}
		++cur;
	}
	Swap(&a[prev], &a[keyi]);
	return prev;
}

4. 非递归实现

基本思路：
1. 使用栈的形式，模拟递归实现
2. 因为每次都要对序列的左右边界进行传入，根据栈的性质：先进后出，后进先出。因此，我们要先传入左边界，再传入右边界，获取数据时要先取右边界，在获取左边界。
3. 注意：获取数据后要及时删除，避免影响栈头结点的数据。

代码实现：

// 非递归方法
void QuickSort3(int* a, int begin, int end)
{
	assert(a);
	Stack ST;
	StackInit(&ST);
	StackPush(&ST, begin);
	StackPush(&ST, end);
	while (!StackEmpty(&ST))
	{
		int right = StackTop(&ST);
		StackPop(&ST);
		int left = StackTop(&ST);
		StackPop(&ST);
		if (left >= right)
		{
			continue;
		}
		int keyi = QuickSort2(a, left, right);
		StackPush(&ST, keyi + 1);
		StackPush(&ST, right);
		StackPush(&ST, left);
		StackPush(&ST, keyi - 1);
	}
}

今天的分享就到这里啦，后续我还会新增一个排序算法-------归并排序，希望这篇文章可以帮助大家解决排序算法中的问题。我们下次再见，拜拜啦！