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）
非递归是由来排序数组元素出项大量重复的时候使用的，因为大量重复元素导致操作系统栈溢出，递归无法完成。文章来源：https://www.toymoban.com/news/detail-423264.html
非递归可以用栈或者队列来实现，我们这里用栈来实现快排的非递归写法，由于我们使用C语言来写，所以需要自己写一个栈出来，具体实现看代码文章来源地址https://www.toymoban.com/news/detail-423264.html
//实现栈
#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);
}到了这里，关于交换排序的两种方法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
