【数据结构—排序—交换排序】

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

---

前言

世上有两种耀眼的光芒，一种是正在升起的太阳，一种是正在努力学习编程的你!一个爱学编程的人。各位看官，我衷心的希望这篇博客能对你们有所帮助，同时也希望各位看官能对我的文章给与点评，希望我们能够携手共同促进进步，在编程的道路上越走越远！

---

提示：以下是本篇文章正文内容，下面案例可供参考

一、排序的概念及其运用

1、排序的概念

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

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

2、排序运用

3、 常见的排序算法

二、交换排序

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

1、冒泡排序

1.1算法讲解

以下是冒泡排序的动图，想具体了解冒泡排序，请点击这里！

冒泡排序的特性总结：
1. 冒泡排序是一种非常容易理解的排序
2. 时间复杂度：O(N^2)?
3. 空间复杂度：O(1)
4. 稳定性：稳定

1.2冒泡排序的实现：

1.2.1头文件的实现—(Sort.h)

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <time.h>

//打印数组
void PrintArray(int* a, int n);

//插入排序(最坏的情况下：逆序，才是等差数列)
void InsertSort(int* a, int n);
//冒泡排序(等差数列)
void BubbleSort(int* a, int n);

//希尔排序
void ShellSort(int* a, int n);

//选择排序
void SelectSort(int* a, int n);
//快速排序(有序的情况下，快速排序会很吃亏)
void QuickSort(int* a, int begin, int end);

//快速排序非递归
void QuickSortNonR(int* a, int begin, int end);

1.2.2源文件的实现—(Sort.c)

#define _CRT_SECURE_NO_WARNINGS 1
#include"Sort.h"
#include"Stack.h"

//打印数组
void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

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

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

1.2.3测试文件的实现—(test.c)

#define _CRT_SECURE_NO_WARNINGS 1
#include"Sort.h"

void TestBubbleSort()
{
	int a[] = { 3,2,6,8,4,6,0,9,5,1,7 };
	BubbleSort(a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));
}

int main()
{
	//TestInsertSort();
	TestBubbleSort();
	//TestShellSort();
	//TestSelectSort();

	//TestQuickSort();

	//TestOP();
	return 0;
}

1.2.4数据测试展示

2、快速排序

2.1算法讲解

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

1. hoare版本

对于快速排序来说有两个优化方法。（三数取中、小区间优化）

对于快速排序的单趟排序有三种方法。(hoare、挖坑法、前后指针法)

对于快速排序的实现有两种方法：递归和非递归（用栈实现）

2.2各大算法的代码实现

2.2.1快速排序hoare版本

Sort.h

//快速排序hoare版本(如果左边有序，右边也有序，那么整体就有序)
//闭区间【begin,end】
void QuickSort(int* a, int begin, int end);

Sort.c

//打印数组
void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

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



//快速排序hoare版本(如果左边有序，右边也有序，那么整体就有序)
//闭区间【begin,end】
void QuickSort(int* a, int begin, int end)
{
	//当只剩最后一个数的时候就排序成功了 和 右区间不存在的时候
	if (begin >= end)
		return;

	int left = begin, right = end;//left:必须要初始化成begin,不能初始化成begin+1
	int keyi = begin;//key一般取最左边的数值，记录keyi所在位置的下标
	//为什么要记录keyi下标所在的位置？
	//是因为keyi是局部变量，我们期望的是数组中的值进行交换，而不是数组中的值与局部变量的值进行交换

	//单趟排序
	while (left < right)
	{
		//右边找小
		while (left < right && a[right] >= a[keyi])
		{
			//加入left < right的条件是为了防止left和right停不下来
			right--;
		}
		//左边找大
		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}
		Swap(&a[left], &a[right]);
	}
	//左右两边相遇的时候，所对应的值一定比keyi小，为什么呢？因为右边先走
	Swap(&a[left], &a[keyi]);
	keyi = left;//left == right,此时左右两边相遇

	//【begin,keyi-1】 keyi 【keyi+1,end】
	//      左边       keyi       右边

	//递归
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
	
}

左右两边相遇的时候，所对应的值一定比keyi小，为什么呢？因为右边先走

2.2.2快速排序hoare改进版三数取中选key法

快速排序：有序的情况下，快速排序会很吃亏，比插入都慢，为什么呢？
因为我们在这使用了一个固定选keyi，比如：在升序的情况下，还要排升序，右边找小，左边找大，因为开始是升序的，所以右边找小找不到，所以keyi只能自己跟自己交换。

正常情况下，快排的时间复杂度：近似认为每一层都是O(N)，所以是O(N^2)。

快排最理想的情况下，每次选keyi，都是二分，类似于递归（根、左子树、右子树）那么时间复杂度：近似的认为每一层都是O(N),总共右LogN层，合计O(N*LogN)

快排有两种优化的方法：

优化一：三数取中法选key
左边、右边和中间下标所对应的数值，三数值取中，去选不是最大，也不是最小的那个数值作keyi。

优化二：小区间优化

递归有一个问题：如果是满二叉树的最后一层占%50的节点，倒数第二层占%25的节点，倒数第三层占%12.5的节点快排这里用递归的话，当区间的数据量小于一定程度后，我们在这里就可以不用递归了，一般到最后3到4层后，我们用插入排序，因为最后三层占据了%87.5的递归。（不过这种优化一般效果几乎没有）

Sort.h

//快速排序hoare改进版三数取中选key法(如果左边有序，右边也有序，那么整体就有序)
//闭区间【begin,end】
void QuickSort(int* a, int begin, int end);

Sort.c

//打印数组
void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

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


//优化一：三数取中：左边、右边和中间下标所对应的数值，三数值取中，去选不是最大，也不是最小的那个数值作keyi
int GetMidi(int* a, int begin, int end)
{
	//如果是有序的情况下，就从最坏变成最好了
	int midi = (begin + end) / 2;
	//如果是无序的情况下
	if (a[begin] < a[midi])
	{
		if (a[midi] < a[end])
			return midi;
		else if (a[begin] > a[end])
			return begin;
		else
			return end;
	}
	else  //a[begin] > a[midi]
	{
		if (a[midi] > a[end])
			return midi;
		else if (a[begin] < a[end])
			return begin;
		else
			return end;
	}
}


//快速排序hoare改进版三数取中选key法(如果左边有序，右边也有序，那么整体就有序)
//闭区间【begin,end】
void QuickSort(int* a, int begin, int end)
{
	//当只剩最后一个数的时候就排序成功了 和 右区间不存在的时候
	if (begin >= end)
		return;


		//优化一：三数取中
		int midi = GetMidi(a, begin, end);
		Swap(&a[midi], &a[begin]);

		int left = begin, right = end;//left:必须要初始化成begin,不能初始化成begin+1
		int keyi = begin;//key一般取最左边的数值，记录keyi所在位置的下标
		//为什么要记录keyi下标所在的位置？
		//是因为keyi是局部变量，我们期望的是数组中的值进行交换，而不是数组中的值与局部变量的值进行交换
		while (left < right)
		{
			//右边找小
			while (left < right && a[right] >= a[keyi])
			{
				//加入left < right的条件是为了防止left和right停不下来
				right--;
			}
			//左边找大
			while (left < right && a[left] <= a[keyi])
			{
				left++;
			}
			Swap(&a[left], &a[right]);
		}
		//左右两边相遇的时候，所对应的值一定比keyi小，为什么呢？因为右边先走
		Swap(&a[left], &a[keyi]);
		keyi = left;//left == right,此时左右两边相遇

		//【begin,keyi-1】 keyi 【keyi+1,end】
		//      左边       keyi       右边

		//递归
		QuickSort(a, begin, keyi - 1);
		QuickSort(a, keyi + 1, end);

}

2.2.3快速排序hoare版本改进版小区间优化法

Sort.h

//快速排序hoare版本(如果左边有序，右边也有序，那么整体就有序)
//闭区间【begin,end】
void QuickSort(int* a, int begin, int end);

Sort.c

//打印数组
void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

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



//优化一：三数取中：左边、右边和中间下标所对应的数值，三数值取中，去选不是最大，也不是最小的那个数值作keyi
int GetMidi(int* a, int begin, int end)
{
	//如果是有序的情况下，就从最坏变成最好了
	int midi = (begin + end) / 2;
	//如果是无序的情况下
	if (a[begin] < a[midi])
	{
		if (a[midi] < a[end])
			return midi;
		else if (a[begin] > a[end])
			return begin;
		else
			return end;
	}
	else  //a[begin] > a[midi]
	{
		if (a[midi] > a[end])
			return midi;
		else if (a[begin] < a[end])
			return begin;
		else
			return end;
	}
}

//快速排序hoare版本(如果左边有序，右边也有序，那么整体就有序)
//闭区间【begin,end】
void QuickSort(int* a, int begin, int end)
{
	//当只剩最后一个数的时候就排序成功了 和 右区间不存在的时候
	if (begin >= end)
		return;

	//优化二：小区间优化
	if (end - begin + 1 <= 10)
	{
		InsertSort(a+begin, end - begin + 1);
		//插入排序是：从a+begin的位置开始到end-begin+1的区间开始排序
		//因为递归(根、左右子树)的原因，插入排序的起始位置不一定是从a开始的。
	}
	else
	{
		//优化一：三数取中
		int midi = GetMidi(a, begin, end);
		Swap(&a[midi], &a[begin]);

		int left = begin, right = end;//left:必须要初始化成begin,不能初始化成begin+1
		int keyi = begin;//key一般取最左边的数值，记录keyi所在位置的下标
		//为什么要记录keyi下标所在的位置？
		//是因为keyi是局部变量，我们期望的是数组中的值进行交换，而不是数组中的值与局部变量的值进行交换
		while (left < right)
		{
			//右边找小
			while (left < right && a[right] >= a[keyi])
			{
				//加入left < right的条件是为了防止left和right停不下来
				right--;
			}
			//左边找大
			while (left < right && a[left] <= a[keyi])
			{
				left++;
			}
			Swap(&a[left], &a[right]);
		}
		//左右两边相遇的时候，所对应的值一定比keyi小，为什么呢？因为右边先走
		Swap(&a[left], &a[keyi]);
		keyi = left;//left == right,此时左右两边相遇

		//【begin,keyi-1】 keyi 【keyi+1,end】
		//      左边       keyi       右边

		//递归
		QuickSort(a, begin, keyi - 1);
		QuickSort(a, keyi + 1, end);
	}
}

2.2.4快速排序挖坑法（快速排序的单躺排序）

Sort.h

//快速排序挖坑法
void QuickSort1(int* a, int begin, int end);

Sort.c

//打印数组
void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

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


//挖坑法(单趟)
int PartSort1(int* a, int begin, int end)
{
	//三数取中
	int midi = GetMidi(a, begin, end);
	Swap(&a[midi], &a[begin]);
	 
	int key = a[begin];
	int holei = begin;
	while (begin < end)
	{
		//右边找小，填左边的坑
		while (begin < end && a[end] >= key)
		{
			--end;
		}
		a[holei] = a[end];
		holei = end;
		//左边找大，填到右边的坑
		while (begin < end && a[begin] <= key)
		{
			begin++;
		}
		a[holei] = a[begin];
		holei = begin;
	}
	a[holei] = key;

	return holei;
}

//快速排序挖坑法
void QuickSort1(int* a, int begin, int end)
{
	//当只剩最后一个数的时候就排序成功了 和 右区间不存在的时候
	if (begin >= end)
		return;

	int keyi = PartSort1(a, begin, end);//单趟
	QuickSort1(a, begin, keyi - 1);
	QuickSort1(a, keyi + 1, end);
}

2.2.5快速排序前后指针（快速排序的单躺排序）

Sort.h

//快速排序前后指针版本
void QuickSort2(int* a, int begin, int end);

Sort.c

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


//前后指针版本
int PartSort2(int* a, int begin, int end)
{
	//三数取中
	int midi = GetMidi(a, begin, end);
	Swap(&a[midi], &a[begin]);

	int keyi = begin;
	int prev = begin;
	int cur = prev + 1;
	while (cur <= end)
	{
		//cur找小
		if (a[cur] < a[keyi])
		{
			prev++;
			Swap(&a[prev], &a[cur]);
		}
		cur++;
	}
	Swap(&a[prev], &a[keyi]);
	keyi = prev;
	return keyi;
}

//快速排序前后指针版本
void QuickSort2(int* a, int begin, int end)
{
	//当只剩最后一个数的时候就排序成功了 和 右区间不存在的时候
	if (begin >= end)
		return;

	int keyi = PartSort2(a, begin, end);//单趟
	QuickSort2(a, begin, keyi - 1);
	QuickSort2(a, keyi + 1, end);
}

2.2.6快速排序非递归版

递归->非递归
1、循环
2、借助栈(后进先出)，改循环（栈里面存两个值，也就是栈里面存整个区间，比如：栈存0~9，0~9出栈，出来以后进行单趟排序，key在5的位置，分成两个子区间；栈里面存6~9和0~4，取出0~4，进行单趟排序，key在2的位置，分成3~4和0~1两个子区间入栈；0~1出栈，分成0~0和2~1两个子区间，这只剩下一个值了，可以不入栈，不进行处理；以此类推）

Stack.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>


typedef int STDataType;
typedef struct stack
{
	STDataType* a;
	int top;//标识栈顶的位置
	int capacity;
}ST;

//初始化
void STInit(ST* pst);
//销毁
void STDestory(ST* pst);

//压栈
void STPush(ST* pst, STDataType x);
//出栈
void STPop(ST* pst);

//获取栈顶元素
STDataType STTop(ST* pst);

//判空
bool STEmpty(ST* pst);

//统计栈内元素个数
int STSize(ST* pst);

Stack.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "Stack.h"

//初始化
void STInit(ST* pst)
{
	assert(pst);
	pst->a = NULL;
	//表示top指向栈顶元素的下一个位置
	pst->top = 0;

	//表示top指向栈顶元素
	//pst->top = -1;

	pst->capacity = 0;
}
//销毁
void STDestory(ST* pst)
{
	assert(pst);
	free(pst->a);
	pst->a = NULL;
	pst->capacity = pst->top = 0;
}

//压栈
void STPush(ST* pst, STDataType x)
{
	assert(pst);
	//判断数组栈空间是否足够
	if (pst->top == pst->capacity)
	{
		int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		pst->a = tmp;
		pst->capacity = newcapacity;
	}
	pst->a[pst->top] = x;
	pst->top++;
}
//出栈
void STPop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);
	pst->top--;
}

//获取栈顶元素
STDataType STTop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);
	return pst->a[pst->top - 1];
}

//判空
bool STEmpty(ST* pst)
{
	assert(pst);
	//判断数组栈为空
	//1、如果top是指向栈顶元素的下一个位置，那当top == 0时，栈为空
	//2、如果top时指向栈顶元素，那当top == -1时，栈为空
	/*if (pst->top == 0)
	{
		return true;
	}
	else
	{
		return false;
	}*/
	return pst->top == 0;
}

//统计栈内元素个数
int STSize(ST* pst)
{
	assert(pst);
	//1、如果top指向栈顶元素的话，栈内元素的个数为top+1；
	//2、如果top指向栈顶元素的下一个位置的话，栈内元素的个数为top；
	return pst->top;
}

Sort.h

//快速排序非递归
void QuickSortNonR(int* a, int begin, int end);

Sort.c

/快速排序非递归
//考察非递归的两种意义：1、有没有掌握快排；2、递归理解深不深刻
void QuickSortNonR(int* a, int begin, int end)
{
	ST s;
	STInit(&s);
	STPush(&s, end);
	STPush(&s, begin);

	while (!STEmpty(&s))
	{
		int left = STTop(&s);
		STPop(&s);
		int right = STTop(&s);
		STPop(&s);

		int keyi = PartSort2(a, left, right);
		//[left,keyi-1] keyi [keyi+1,right]
		if (left < keyi - 1)//不加等于号是等剩下一个值的时候，就不进栈了
		{
			//跟前面保持一直，先右后左
			STPush(&s, keyi - 1);
			STPush(&s, left);
		}
		if (keyi + 1 < right)
		{
			STPush(&s, right);
			STPush(&s, keyi + 1);
		}
	}

	STDestory(&s);
}

---

总结

好了，本篇博客到这里就结束了，如果有更好的观点，请及时留言，我会认真观看并学习。
不积硅步，无以至千里；不积小流，无以成江海。