【数据结构】_排序

【本节目标】

1. 排序的概念及其运用
2. 常见排序算法的实现
3. 排序算法复杂度及稳定性分析

1.排序的概念及其运用

1.1排序的概念

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

1.2特性及分类

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

1.3常见的排序算法

2.常见排序算法的实现

2.1 插入排序

2.1.1基本思想：

直接插入排序是一种简单的插入排序法，其基本思想是：

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。

2.1.2直接插入排序

单趟排序（排一个数据）

//单趟排序
void InsertSort(int* a, int n)
{
	assert(a);
	int end;//有序序列最后一个下标
	int tmp = a[end + 1];//先保存下标为end后面那个数字，也就是要插入的数字
	while (end >= 0)//=0表示极端，也就是要插入的数比任何一个都小
	{
		if (tmp < a[end])
		{
			a[end + 1] = a[end];//end挪动到end+1处
			end--;
		}
		else
		{
			break;
		}
	}
	a[end + 1] = tmp;//把tmp这个要插入的数放到下标为end的后面end+1处
}

多趟排序（在单趟排序的基础上加上一个for循环）

void InsertSort(int* a, int n)
{
	assert(a);
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;//i表示已排序部分的最后一个元素的下标
		int tmp = a[end + 1];//先保存下标为end后面那个数字，也就是要插入的数字
		while (end >= 0)//=0表示极端，也就是要插入的数比任何一个都小
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];//end挪动到end+1处
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;//把tmp这个要插入的数放到下标为end的后面end+1处
	}
}

🤔🤔思考：

这里for循环为什么是i<n-1呢？

运行结果：

2.1.3 希尔排序

希尔排序法又称缩小增量法。希尔排序法的基本思想是：通过将原始数组分成多个子序列进行局部插入排序，逐步缩小子序列的间隔（增量），最终使整个数组基本有序，最后进行一次完整的插入排序。（希尔排序是在直接插入排序的基础上优化）

其分为两个步骤：

1. 预排序（数组接近有序）gap>1
   预排序：把间距为gap的值分为一组，进行插入排序

2. 直接插入排序 gap==1

由上可知，gap的核心原理为：

gap越大，前面大的数据可以越快到后面，后面小的数，可以越快到前面。gap越大，越不接近有序；gap越小越接近有序。如果gap==1其实就相当于直接插入排序，就有序了

画图分析：

代码解析：

// 希尔排序
void ShellSort(int* a, int n)
{
	//1.gap>1相当于预排序，让数组接近有序
	//2，gap == 1就相当于直接插入排序，保证有序
	int gap = n;
	
	while (gap > 1)
	{
		gap = gap / 3 + 1;//希尔研究发现三倍三倍走好一点；+1保证最后一次一定是1
		//多组并排
		// 对间隔为gap的所有子序列进行插入排序
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = a[end + gap];
			// 对当前子序列进行插入排序
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];//往后挪 元素后移gap位
					end -= gap;//end往前走 向前移动gap位继续比较
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;//插入元素
		}
	}
}

🤔🤔🤔思考：为什么循环条件需要 i < n - gap

因为int end = i;和int tmp = a[end + gap];这两段代码表明i从0开始下标索引，i=end，所以假设gap=4并且一共有10个数，那么当i循环到6时，i+gap=10；下标为10的时候，已超出范围，所以会造成越界访问，所以这时候i<n-gap==10-4=6，也就是i<6时这样才不会越界访问；至于为什么要这个关于i的循环？？那其实是为了实现多组并排！！

1.防止数组越界

核心问题是：当我们访问a[i+gap]时，必须确保i+gap是一个有效的数组索引。

• 数组索引范围：0 到 n-1

• 所以必须保证：i + gap ≤ n - 1

• 推导出：i ≤ n - 1 - gap

• 在循环中我们写成：i < n - gap (因为从0开始)

2.具体例子说明

假设有一个数组，n = 8，当前gap = 3：

• 索引: 0 1 2 3 4 5 6 7
• 值: [5,3,8,9,1,2,7,4]
• 计算n - gap = 8 - 3 = 5，所以循环条件是i < 5，即i从0到4。

让我们看看每次循环时i+gap的值：

如果循环条件是i < 6（即i最大到5）：

• 当i=5时，i+gap=8，但数组最大索引是7，这就越界了！

🤔🤔🤔那为什么要：gap = gap / 3 + 1;

研究表明，gap 按3倍递减 的效率较高（比常见的2倍递减更快）。这是经验性的结论，由希尔排序的研究者提出。
+1 是为了保证 最后一次gap一定是 1，从而确保最终进行一次完整的插入排序。

2.2 选择排序

2.2.1基本思想：

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

2.2.2 直接选择排序

void SelectSort(int* a, int n)
{
	int begin = 0;
	while (begin < n - 1)
	{
		int min = begin;//假设第一个下标为最小值
		//循环遍历看看有没有更小的,以自身为起点
		for (int i = begin; i < n; i++)
		{
			if (a[i] < a[min])
			{
				min = i;
			}
		}
		Swap(&a[begin], &a[min]);//交换的是假设的最小的和实际的最小的
		begin++;
	}
}

上面选择的是选一个值，下面我们就优化一下选两个值：

这里我们用的方法是：选出小的数放左边，选出大的数放右边；然后再缩小区间，但是我们会发现，选出之后那个数就被覆盖了，会找不到，因此这里我们就要用下标来做

// 选择排序
void SelectSort(int* a, int n)
{
	assert(a);
	//区间定义 定义两个下标
	int begin = 0;
	int end = n - 1;
	//还未相遇
	while (begin < end)
	{
		//在[begin,end]之间找到最小的数和最大的数的下标
		int mini = begin;
		int maxi = begin;
		for (int i = begin+1; i <= end; i++)
		//i<=end表示在这个区间之中选择;begin+1是因为begin已经给了第一个值，那就从其后一个位置开始走
		{
			if (a[i] > a[maxi])
			{
				maxi = i;//说明i位置这个值更大
			}
			if (a[i] < a[mini])
			{
				mini = i;
			}
		}
		//交换排升序
		Swap(&a[begin], &a[mini]);

		//如果maxi和begin位置重叠，则maxi的位置需要修正
		if (begin == maxi)
		{
			maxi = mini;
		}
		Swap(&a[end], &a[maxi]);

		begin++;
		end--;
	}
}

🤔🤔🤔思考：为什么要下面这串代码？

//如果maxi和begin位置重叠，则maxi的位置需要修正
if (begin == maxi)
{
	maxi = mini;
}

2.2.3 堆排序

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

// 堆排序
void AdjustDwon(int* a, int n, int root)
{
	//向下调整算法
	int parent = root;
	//找出左右孩子中大的那一个
	int child = parent * 2 + 1;//child先指向左孩子
	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)
{
	//排升序，建大堆
	//倒数第一个叶子节点
	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--;
	}
}

2.3 交换排序

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

2.3.1冒泡排序

// 冒泡排序
void BubbleSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		for (int j = 0; j < n - 1 - i; j++)
		{
			if (a[j] > a[j + 1])
			{
				Swap(&a[j], &a[j + 1]);
			}
		}
	}
}

2.3.2 快速排序

（1）左右指针法

// 快速排序递归实现

//获取三数取中的下标（防止栈溢出）
int GetMidIndex(int* a, int begin, int end)
{
	int mid = (begin + end) / 2;
	//找3个数里面不是最大也不是最小数的下标
	if (a[begin] < a[mid])
	{
		if (a[mid] < a[end])
		{
			return mid;
		}
		else if (a[begin] > a[end])
		{
			return begin;
		}
		else
		{
			return end;
		}
	}
	else//a[begin] > a[mid]
	{
		if (a[end] > a[mid])
		{
			return end;
		}
		else if (a[begin] < a[mid])
		{
			return begin;
		}
		else
		{
			return end;
		}
	}
}

// 单趟排序
int PartSort1(int* a, int begin, int end)
{
	//int key = a[end];//假设key位置在右边

	int keyindex = end;//下标key

	int midIndex = GetMidIndex(a, begin, end);
	Swap(&a[midIndex], &a[end]);//确保这个中间值做key在右边

	while (begin < end)//未相遇
	{
		//key在右边，那就左边先走，也就是begin先走
		//begin找大
		while (begin < end && a[begin] <= a[keyindex])
		{
			begin++;
		}
		//end找小
		while (begin < end && a[end] >= a[keyindex])
		{
			end--;
		}
		Swap(&a[begin], &a[end]);
	}
	Swap(&a[begin], &a[keyindex]);
	return begin;
}


// 快速排序hoare版本
int QuickSort1(int* a, int left, int right)
{
	assert(a);
	if (left >= right)
	{
		return;
	}
	int div = PartSort1(a, left, right);//div有划分意思，先走一个单趟排序
	//这时就划分成了三部分[left,div-1] div [div+1,right]
	QuickSort1(a, left, div - 1);
	QuickSort1(a, div + 1, right);

}

整体结构

GetMidIndex函数：实现"三数取中"策略，选择begin、mid、end三个位置中的中间值作为基准，避免最坏情况。

PartSort1函数：实现单趟排序（分区操作），返回基准值的最终位置。

QuickSort1函数：递归实现快速排序的主函数。

（2）挖坑法

// 快速排序递归实现

//获取三数取中的下标（防止栈溢出）
int GetMidIndex(int* a, int begin, int end)
{
	int mid = (begin + end) / 2;
	//找3个数里面不是最大也不是最小数的下标
	if (a[begin] < a[mid])
	{
		if (a[mid] < a[end])
		{
			return mid;
		}
		else if (a[begin] > a[end])
		{
			return begin;
		}
		else
		{
			return end;
		}
	}
	else//a[begin] > a[mid]
	{
		if (a[end] > a[mid])
		{
			return end;
		}
		else if (a[begin] < a[mid])
		{
			return begin;
		}
		else
		{
			return end;
		}
	}
}

//2.挖坑法
int PartSort2(int* a, int begin, int end)
{
	//三数取中
	int midIndex = GetMidIndex(a, begin, end);
	Swap(&a[midIndex], &a[end]);//确保这个中间值做key在右边

	//坑
	int key = a[end];//保存坑这个值
	while (begin < end)
	{
		//begin找比key大的
		while (begin < end && a[begin] <= key)
		{
			begin++;
		}
		//找到后填到坑里，begin位置就形成了新的坑
		a[end] = a[begin];

		//右边找小
		while (begin < end && a[end] >= key)
		{
			end--;
		}
		//右边找到比key小的填到左边的坑，end位置就形成的新的坑
		a[begin] = a[end];
	}
	a[begin] = key;//begin和end相遇后，找不到了就把key填到这个坑里
	return begin;//begin和end都行
	
}

void QuickSort1(int* a, int left, int right)
{
	assert(a);
	if (left >= right)
	{
		return;
	}
	int div = PartSort2(a, left, right);//div有划分意思，先走一个单趟排序
	//这时就划分成了三部分[left,div-1] div [div+1,right]
	QuickSort1(a, left, div - 1);
	QuickSort1(a, div + 1, right);

}

其他的不变，就是改了一个PartSort2部分

（3）前后指针法

//3.前后指针法
int PartSort3(int* a, int begin, int end)
{
	int prev = begin - 1;
	int cur = begin;
	int keyindex = end;
	while (cur < end)
	{
		if (a[cur] < a[keyindex] && ++prev != cur)//注意这里prev先++，因为相等交不交换都一样
		{
			Swap(&a[prev], &a[cur]);
		}
		cur++;
	}
	//交换完以后，将prev先++，再和key交换
	Swap(&a[++prev], &a[keyindex]);
	return prev;//返回这个分界点
}

2.3.3 快速排序非递归

递归改非递归：
1、改循环（斐波那契数列求解）一些简单递归才能改循环
2、栈模拟存储数据非递归
非递归的好处：
1、提高效率（递归建立栈帧还是有消耗的，但是对于现代的计算机，这个优化微乎其微可以忽略不计）
2、递归最大缺陷是，如果栈帧的深度太深，可能会导致栈溢出。因为系统栈空间一般不大在M（兆）级别
数据结构栈模拟非递归，数据是存储在堆上的，堆是G级别的空间

//快速排序非递归实现
void QuickSortNonR(int* a, int left, int right)
{
	//栈模拟实现
	Stack st;
	StackInit(&st);

	StackPush(&st, right);//先入右，先出的就是左
	StackPush(&st, left);

	while (!StackEmpty(&st))
	{
		int begin = StackTop(&st);//栈顶就是左
		StackPop(&st);
		int end = StackTop(&st);//左出完就是右（因为入栈时是个区间，所以要入两个数）
		StackPop(&st);

		//[begin,end]
		int div = PartSort3(a, begin, end);//单趟排序
		//[begin,div-1] div [div+1,end]

		//先处理右,再处理左
		if (div + 1 < end)
		{
			//入栈
			StackPush(&st, end);
			StackPush(&st, div + 1);
		}
		if (begin < div - 1)
		{
			//入栈
			StackPush(&st, div - 1);
			StackPush(&st, begin);
		}
	}
	StackDestory(&st);
}

2.4 归并排序

2.4.1递归实现

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

	//分割
	int mid = (left + right) / 2;
	//[left,mid]  [mid+1,right]有序，则可以合并，现在他们没有序，子问题解决
	_MergeSort(a, left, mid, tmp);
	_MergeSort(a, mid+1, right, tmp);

	//归并[left,mid]  [mid+1,right]有序
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	// 声明并初始化index变量，指向当前子数组的起始位置
	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++];
	}

	//把归并好的在tmp的数据再拷贝回到原数组
	for (int i = left; i <= right; i++)
	{
		a[i] = tmp[i];
	}
}


//归并排序递归实现
void MergeSort(int* a, int n)// a 是待排序数组，n 是数组长度。
{
	assert(a);
	int* tmp = malloc(sizeof(int) * n);
	_MergeSort(a, 0, n - 1, tmp);

	free(tmp);
	//功能：分配一个与原数组大小相同的临时数组 tmp，调用递归排序函数，最后释放临时内存。
}

归并排序的基本思想

1. 分解（Divide）：将数组分成两个子数组，递归地对每个子数组进行排序。
2. 合并（Conquer）：将两个已排序的子数组合并成一个有序数组。

归并排序由两个主要函数组成：

• MergeSort：对外接口，分配临时数组并调用递归函数。
• _MergeSort：递归实现排序和合并逻辑。

举例说明：

2.4.2非递归实现

归并排序的核心思想是分治法，将数组分成两个子数组，分别排序后再合并。非递归版本通过迭代方式，逐步增大子数组的规模，直到整个数组有序。

//用于合并两个已排序的子数组
void MergeArr(int* a, int begin1, int end1, int begin2, int end2,int* tmp)
{
	int left = begin1;
	int right = end2;
	int index = begin1;
	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++];
	}

	//把归并好的在tmp的数据再拷贝回到原数组
	for (int i = left; i <= right; i++)
	{
		a[i] = tmp[i];
	}
}


// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
{
	assert(a);
	int* tmp = malloc(sizeof(int) * n);
	int gap = 1;//间距为1 一个一个归并
	while (gap<n)
	{
		for (int i = 0; i < n; i += 2 * gap)
		{
			//[i, i + gap-1)[i + gap, i + 2 * gap-1)闭区间
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
			//1、合并时只有第一组，就不需要合并
			if (begin2 >= n)
			{
				break;
			}
			//2、合并时第二组只有部分数据，需要修正end2边界
			if (end2 >= n)
			{
				end2 = n - 1;
			}

			MergeArr(a, begin1, end1, begin2, end2, tmp);
		}
		PrintArray(a, n);
		gap *= 2;
	}
	
	free(tmp);
}

MergeArr函数

思考：MergeSortNonR这个函数里面为什么要修正边界

在MergeSortNonR函数中修正边界是为了处理数组长度不是2的幂时的特殊情况。归并排序的非递归实现通过迭代逐步合并相邻的子数组，每次迭代中子数组的大小（gap）翻倍。当子数组大小超过数组长度的一半时，可能会出现以下两种边界情况：

2.5 非比较排序

💡💡思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。 操作步骤：

1. 统计相同元素出现次数
2. 根据统计的结果将序列回收到原来的序列中
   （计数排序只适用于整形，如果浮点数或者字符串排序，还得用比较排序）

❗❗❗注意：这下面的代码写的是绿色框里面的相对位置法

// 计数排序
void CountSort(int* a, int n)
{
	assert(a);
	//分别求出最小数和最大数
	int min = a[0];
	int max = a[0];
	//求范围
	for (int i = 1; i < n; i++)
	{
		if (a[i] > max)
		{
			max = a[i];
		}
		if (a[i] < min)
		{
			min = a[i];
		}
	}
	int range = max - min + 1;//求的是范围
	//为什么要+1呢？
	//因为假设最大值9，最小值0；9-0=9但实际是10个数据
	int* countArr = (int*)malloc(sizeof(int) * range);//开辟一个数组容纳空间
	memset(countArr, 0, sizeof(int) * range);//初始化

	//统计次数
	for (int i = 0; i < n; i++)
	{
		//对应值就在其对应位置加加
		countArr[a[i] - min]++;//这里是相对位置（减去最小值的位置）
		//假设a[0]=1000,1000-1000=0;那么就在这个新开的countArr[0]处++

	}

	//排序
	int index = 0;
	for (int j = 0; j < range; j++)
	{
		while (countArr[j]--)
		{
			a[index++] = j + min;//j+min表示对应的值,这里是放到新数组a里面
		}
	}
	free(countArr);
}

🎉🎉🎉
友友们
到这里我们就结束啦~
我们下期见噢~