交换排序的两种方法

C语言实现交换排序的两种方法：冒泡排序和快排。

冒泡排序：冒泡排序十分简单，在这里简要分析：

算法步骤：

比较相邻的元素。如果第一个比第二个大，就交换他们两个。

对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

针对所有的元素重复以上的步骤，除了最后一个。

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

 冒泡排序的特性：

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

void Swap(int* e1, int* e2)
{
	int tmp = *e1;
	*e1 = *e2;
	*e2 = tmp;
}
 
void BubbleSort(int* arr, int len)
{
	int i = 0;
	for (i = 0; i < len; i++)
	{
		for (int j = 0; j < len - i - 1; j++)
		{
            //交换两个数的大小
			if (arr[j] > arr[j + 1])
				Swap(&arr[j], &arr[j + 1]);
		}
	}
}

下面讲解快排

快排基本思想：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

快排有递归和非递归两种写法，先来讲解递归的方法

快速排序的特性总结：
1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(logN)
4. 稳定性：不稳定
 

递归的有三种写法：基本法，挖坑法，指针法。

基本法：基本法就是建立一个基准值，基准值可以随机选取，但随机选取的可能是数组中最大值或者是数组中的最小值，所以最好的方法是三目取中法，就是选取数组左右两端的数据和中间的数据，然后判断这三个数中那个是中间值，然后将这个数有最左端或最右端的数交换，这样做的目的是为了减小排序的次数。然后就是一趟排序了。

基本法就是基准值在左边的时候，右边先走然后再走左边，当右边的数小于基准值，左边的数大于基准值使，交换左右两边的数。

 代码如下：

//排序一趟的方法
//交换数据
void Swap(int* e1, int* e2)
{
	int tmp = *e1;
	*e1 = *e2;
	*e2 = tmp;
}
 
//三目取中法
int GetMinNum(int* arr, int left, int right)
{
	int x = left;
	int y = right;
	int z = (x + y) / 2;
	int max = arr[x];
	int min = arr[left];
	int sum = x + y + z;
	if (arr[x] > arr[y])
		max = x;
	else
		max = y;
	if (arr[max] < arr[z])
		max = z;
	if (arr[y] > arr[x])
		min = x;
	else
		min = y;
	if (arr[min] > arr[z])
		min = z;
	return sum-max-min;
}
//基础法
int Partion1(int* arr, int left, int right)
{
	int key = GetMinNum(arr, left, right);
	//int key = left;
	//Swap(&key, &arr[left]);
	while (left < right)
	{
		//左右两边的数交换
		while (left < right && arr[right] >= arr[key])
		{
			right--;
		}
		while (left < right && arr[left] <= arr[key])
		{
			left++;
		}
		Swap(&arr[left], &arr[right]);
	}
	//右边的数有基准值交换
	Swap(&arr[left], &arr[key]);
	//返回两边相遇的数的下标
	return left;
}

 2，挖坑法

挖坑法和基础法差不多，假设基准值在左边，则将基准值保留下来，然后右边的指针找比基准值小的数，左边的找比基准值大的数，然后交换，交换的地方变成一个新坑，具体看代码

//交换数据
void Swap(int* e1, int* e2)
{
	int tmp = *e1;
	*e1 = *e2;
	*e2 = tmp;
}
 
//挖坑法，排一边的时候
int Partion2(int* arr, int left, int right)
{
	int key = left;
	int dig = key;
	while (left < right)
	{
		while (left < right && arr[right] >= arr[key])
		{
			right--;
		}
		while (left < right && arr[left] <= arr[key])
		{
			left++;
		}
		Swap(&arr[left], &arr[right]);
	}
	Swap(&arr[left], &arr[dig]);
	return left;
}

然后是指针法

指针法就是定义一个前后指针，假设基准值在左边，在起始位置，后指针比前指针多一步，（如果基准值在右边，则后指针在数组起始位置，后指针为空），然后后指针找小，找到比基准值小的数之后前指针加一之后与后指针交换，如果后指针走到结尾，则结束。

//交换函数
void Swap(int* e1, int* e2)
{
	int tmp = *e1;
	*e1 = *e2;
	*e2 = tmp;
}
int Partion3(int* arr, int left, int right)
{
	int key = left;
	int cur = left + 1;
	int pre = left;
	while (cur <= right)
	{
		/*while (arr[cur] >= arr[key] && cur <= right)
		{
			cur++;
		}
		if(cur<=right)
			Swap(&arr[cur], &arr[++pre]);*/
		if (arr[cur] < arr[key] && arr[++pre] != arr[cur])
		{
			Swap(&arr[cur], &arr[pre]);
		}
		cur++;
 
	}
	Swap(&arr[key], &arr[pre]);
	return pre;
}

完整代码

//快排
//基础版
//交换函数
void Swap(int* e1, int* e2)
{
	int tmp = *e1;
	*e1 = *e2;
	*e2 = tmp;
}
//三目取中法
int GetMinNum(int* arr, int left, int right)
{
	int x = left;
	int y = right;
	int z = (x + y) / 2;
	int max = arr[x];
	int min = arr[left];
	int sum = x + y + z;
	if (arr[x] > arr[y])
		max = x;
	else
		max = y;
	if (arr[max] < arr[z])
		max = z;
	if (arr[y] > arr[x])
		min = x;
	else
		min = y;
	if (arr[min] > arr[z])
		min = z;
	return sum-max-min;
}
int Partion1(int* arr, int left, int right)
{
	int key = GetMinNum(arr, left, right);
	//int key = left;
	Swap(&key, &arr[left]);
	while (left < right)
	{
		//左右两边的数交换
		while (left < right && arr[right] >= arr[key])
		{
			right--;
		}
		while (left < right && arr[left] <= arr[key])
		{
			left++;
		}
		Swap(&arr[left], &arr[right]);
	}
	//右边的数有基准值交换
	Swap(&arr[left], &arr[key]);
	//返回两边相遇的数的下标
	return left;
}
//挖坑法
int Partion2(int* arr, int left, int right)
{
	int key = left;
	int dig = key;
	while (left < right)
	{
		while (left < right && arr[right] >= arr[key])
		{
			right--;
		}
		while (left < right && arr[left] <= arr[key])
		{
			left++;
		}
		Swap(&arr[left], &arr[right]);
	}
	Swap(&arr[left], &arr[dig]);
	return left;
}
//指针法
int Partion3(int* arr, int left, int right)
{
	int key = left;
	int cur = left + 1;
	int pre = left;
	while (cur <= right)
	{
		/*while (arr[cur] >= arr[key] && cur <= right)
		{
			cur++;
		}
		if(cur<=right)
			Swap(&arr[cur], &arr[++pre]);*/
		if (arr[cur] < arr[key] && arr[++pre] != arr[cur])
		{
			Swap(&arr[cur], &arr[pre]);
		}
		cur++;
 
	}
	Swap(&arr[key], &arr[pre]);
	return pre;
}
 
 
void QuickSort(int* arr, int left, int right)
{
	if (left >= right)
		return;
	int key1 = Partion1(arr, left, right);
    int key1 = Partion2(arr, left, right);
    int key1 = Partion3(arr, left, right);
	QuickSort(arr, left, key1 - 1);
	QuickSort(arr, key1 + 1, right);
	
}

递归与二叉树前序遍历规则非常像，同学们在写递归框架时可想想二叉树前序遍历规则即可快速写出来，后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。

非递归

非递归的思想与递归的思想几乎一样，只是方法不同，非递归的方法时间复杂度为O（N*logn）

非递归是由来排序数组元素出项大量重复的时候使用的，因为大量重复元素导致操作系统栈溢出，递归无法完成。

非递归可以用栈或者队列来实现，我们这里用栈来实现快排的非递归写法，由于我们使用C语言来写，所以需要自己写一个栈出来，具体实现看代码

//实现栈
#define _CRT_SECURE_NO_WARNINGS
#include "Stack.h"
//初始化栈
void STListInIt(ST* ps)
{
	ps->a = (STypeDate*)malloc(sizeof(STypeDate) * 4);
	if (ps->a == NULL)
	{
		perror("malloc fail");
		return;
	}
	ps->top = 0;
	ps->capacity = 4;
}
//销毁栈
void STListDestroy(ST* ps)
{
	free(ps->a);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}
 
//插入
void STListPush(ST* ps, STypeDate x)
{
	if (ps->top == ps->capacity)
	{
		STypeDate* pps = realloc(ps->a, sizeof(STypeDate) * ps->capacity * 2);
		if (pps == NULL)
		{
			perror("realloc file");
			return;
		}
		//ps->a = pps;
		ps->capacity *= 2;
	}
	ps->a[ps->top] = x;
	ps->top++;
}
//删除
void STListPop(ST* ps)
{
	assert(ps);
	ps->top--;
}
 
//计算栈的大小
int STListSize(ST* ps)
{
	assert(ps);
	assert(!STListEmpty(ps));
	return ps->top;
}
 
//判断是否为空
bool STListEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}
//出栈元素
STypeDate STListTop(ST* ps)
{
	assert(ps);
	assert(!STListEmpty(ps));
	return ps->a[ps->top - 1];
}
//交换函数
void Swap(int* e1, int* e2)
{
	int tmp = *e1;
	*e1 = *e2;
	*e2 = tmp;
}
 
//非递归
void QuickSortNonR(int* arr, int left, int right)
{
	ST ps;
	STListInIt(&ps);
	STListPush(&ps, left);
	STListPush(&ps, right);
	while (!STListEmpty(&ps))
	{
		int end = STListTop(&ps);
		STListPop(&ps);
 
		int begin = STListTop(&ps);
		STListPop(&ps);
 
		int key = Partion2(arr, begin, end);//排列一次的函数可以用上面的三个函数，任选其一
 
		if (key + 1 < end)
		{
			STListPush(&ps, key + 1);
			STListPush(&ps, end);
		}
		if (key - 1 > begin)
		{
			STListPush(&ps, begin);
			STListPush(&ps, key - 1);
		}
	}
	STListDestroy(&ps);
}