网络建站的费用/php搭建一个简单的网站

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;elsemax = y;if (arr[max] < arr[z])max = z;if (arr[y] > arr[x])min = x;elsemin = 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;elsemax = y;if (arr[max] < arr[z])max = z;if (arr[y] > arr[x])min = x;elsemin = 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);
}