数据结构初阶之排序（上）

排序的概念及其应用

排序的概念

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

排序的应用

如下图：

---

样例数组

下面我们给出一组乱序的数组，接下来的算法我们都将以该数组为例进行排序测试。

int a[] = {5, 3, 9, 6, 2, 4, 7, 1, 8};

常见的排序算法

排序在我们的日常生活中可谓是无处不在，它潜移默化的影响着我们的生活。那么今天，我将为大家介绍一下几种常见的排序算法-----我们先来看一下总览图：

插入排序

顾名思义，插入排序就好比打扑克时的理牌。

直接插⼊排序是⼀种简单的插⼊排序法，其基本思想是：把待排序的记录按其关键码值的⼤⼩逐个插⼊到⼀个已经排好序的有序序列中，直到所有的记录插⼊完为⽌，得到⼀个新的有序序列。

下面我们通过一张动图来了解直接插入排序：

代码的实现：

首先来写一个交换元素的过程：

void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}

void InsertSort(int* arr, int n)
{
	//n-2
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = arr[end + 1];
 
		while (end >= 0)
		{
			if (arr[end] > tmp)
			{
				arr[end + 1] = arr[end];
				end--;
			}
			else {
				break;
			}
		}
		arr[end + 1] = tmp;
	}
}

直接插入排序的特征

直接插⼊排序的特性总结

1. 元素集合越接近有序，直接插⼊排序算法的时间效率越⾼

2. 时间复杂度：O(N^2)

3. 空间复杂度：O(1)

那么问题来了，直接插入排序的时间复杂度来到了惊人的N^2，它是否还能继续优化呢？

答案是肯定的：

希尔排序

希尔排序法⼜称缩⼩增量法。

希尔排序法的基本思想是：先选定⼀个整数（通常是gap=n/3+1），把待排序⽂件所有记录分成各组，所有的距离相等的记录分在同⼀组内，并对每⼀组内的记录进⾏排序，然后gap=gap/3+1得到下⼀个整数，再将数组分成各组，进⾏插⼊排序，当gap=1时，就相当于直接插⼊排序。

希尔排序是在直接插⼊排序算法的基础上进⾏改进⽽来的，综合来说它的效率肯定是要⾼于直接插⼊排序算法的。

如图所示：

希尔排序的特征

1. 希尔排序是对直接插⼊排序的优化。

2. 当 gap > 1 时都是预排序，⽬的是让数组更接近于有序。当 gap == 1 时，数组已经接近有序的了，这样就会很快。这样整体⽽⾔，可以达到优化的效果。

3.

代码的实现：

//希尔排序时间复杂度大约为：O（n^1.3)
void ShellSort(int* arr, int n)
{
	int gap = n;//6
 
	while (gap > 1)
	{
		gap = gap / 3 + 1;//保证最后一次gap一定为1
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;//n-gap-1
			int tmp = arr[end + gap];
			while (end >= 0)
			{
				if (arr[end] > tmp)
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else {
					break;
				}
			}
			arr[end + gap] = tmp;
		}
	}
}

希尔排序的时间复杂度大约在（N^1.3），它对直接插入排序进行了分组预排序处理。大大提高了算法效率

---

选择排序

选择排序的基本思想：

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

我们还是用一张动图来了解选择排序的工作原理：

代码的实现：

//时间复杂度为O(n^2)
void SelectSort(int* arr, int n)
{
	int begin = 0;
	int end = n - 1;
 
	while (begin < end)
	{
		int mini = begin, maxi = begin;
		for (int i = begin+	1; i <= end; i++)
		{
			if (arr[i] > arr[maxi])
			{
				maxi = i;
			}
			if (arr[i] < arr[mini])
			{
				mini = i;
			}
		}
		//mini begin
		//maxi end
		//避免maxi begini都在同一个位置，begin和mini交换之后，maxi数据变成了最小的数据
		if (maxi == begin)
		{
			maxi = mini;
		}
		Swap(&arr[mini], &arr[begin]);
		Swap(&arr[maxi], &arr[end]);
 
		++begin;
		--end;
	}
	
}

直接选择排序的特征

1. 直接选择排序思考⾮常好理解，但是效率不是很好。实际中很少使⽤

2. 时间复杂度：O(N^2 )

3. 空间复杂度：O(1)

---

堆排序（选择排序的一种）

堆排序(Heapsort)是指利⽤堆积树（堆）这种数据结构所设计的⼀种排序算法，它是选择排序的⼀ 种。它是通过堆来进⾏选择数据。需要注意的是排升序要建⼤堆，排降序建⼩堆。

堆排序是通过比较每一层父节点与子节点间的大小后进行的递归性的排序，相较于直接选择排序与直接插入排序，它是相当高效的，下面我们来欣赏一下它的代码实现：

代码的实现：

首先便是向下调整的过程：

void AdjustDown(int* arr, int parent, int n)
{
	int child = parent * 2 + 1;//左孩子
	//while (parent < n)
	while (child < n)
	{
		//小堆：找左右孩子中找最小的
		//大堆：找左右孩子中找大的
		if (child + 1 < n && arr[child] > arr[child + 1])
		{
			child++;
		}
		if (arr[child] < arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
 
		}
		else
		{
			break;
		}
	}
}

接下来便是建堆，堆顶与堆底元素的交换后向下调整的过程：

//堆排序
//空间复杂度为0(1)
//时间复杂度为O(n*logn)
void HeapSort(int* arr, int n)
{
	//建堆
	//升序---大堆
	//降序----小堆
	//向下调整算法建堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, i, n);
	}
 
	//循环将堆顶数据跟最后位置（会变化，每次减少一个数据）的数据进行交换
	int end = n - 1;
	while (end > 0)
	{
		Swap(&arr[0], &arr[end]);
		AdjustDown(arr, 0, end);
		end--;
	}
}

---

交换排序

交换排序基本思想：

所谓交换，就是根据序列中两个记录键值的⽐较结果来对换这两个记录在序列中的位置

交换排序的特点是：将键值较⼤的记录向序列的尾部移动，键值较⼩的记录向序列的前部移动

交换排序中最为基础也最为典型的便是冒泡排序。

冒泡排序：

我们通过一张图来了解：

该排序算法可谓是通俗易懂，但是它的缺点也相当明显（它的时间复杂度相当差）

代码的实现：

void BubbleSort(int* a, int n) 
{
 int exchange = 0;
 for (int i = 0; i < n; i++)
 {
 for (int j = 0; j <n-i-1 ; j++)
 {
 if (a[j] > a[j + 1]) 
 {
 exchange = 1;
 swap(&a[j], &a[j + 1]);
 }
 }
 if (exchange == 0) 
 {
 break;
 }
 }
}

冒泡排序的特征

• 时间复杂度：O(N^2)

• 空间复杂度：O(1)

---

结尾

以上便是本期的全部内容，下期我将继续为大家分享剩下的快速排序算法，敬请期待哦~