c语言实现快速排序递归

今天编程学习网为大家讲解c语言实现快速排序递归，有需要的小伙伴可以参考一下：

一、快速排序

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

二、快速排序之“挖坑法”

2.1 挖坑法思路

单趟排序：单趟排序的目的就是使当前的key值放到它最终的位置，左边全是比它小的数，右边全是比它大的数。我们一般选取第一个值或者最后一个值做key，pivot初始值为初始的key值的位置，这里也就是第一个位置。当pivot在begin的位置时，end从右往左开始找比key小的值，找到后将它放到pivot的地方，也就是填坑，填完之后自己形成新的坑位；pivot在end的位置时，begin从左往右开始找比key大的数，找到之后进行填坑，直到begin和end相遇时，最后将key放至相遇点即可。

2.2 挖坑法图解

第一步：定义begin，end，key，pivot这四个变量。这里选第一个值最为key，那么第一个值自然就是pivot。

第二步：将key值拿走，第一个值成为pivot。

第三步：这时候pivot在begin位置，那么end就开始从右至左找比key小的值，找到后放入pivot。所以将2放到pivot的位置，end成为新的pivot。

第四步：这时候pivot在end位置，那么begin开始从左至右找比key大的值，找到后放入pivot。所以将8放到pivot的位置，begin成为新的pivot。

第五步：end继续找小，找到4放到pivot，end成为新的pivot。

第六步：begin继续找大，这里与end汇合了，停止循环，把key放到相遇位置即可。

2.3 挖坑法动图展示

2.4 单趟排序的代码

void QuickSort(int* arr, int n)
{
int begin = 0;
int end = n-1;
int key = arr[begin];
int pivot = begin;
while (begin < end)
{
//pivot在begin那边，则end这边找比key小
while (begin < end&&arr[end] >= key)
{
end--;
}
//循环结束则为找到该小值,将之赋值给arr[pivot]
arr[pivot] = arr[end];
//自己形成新的坑位
pivot = end;
//piovt在end那边，则begin这边找比key大
while (begin < end&&arr[begin] <= key)
{
begin++;
}
//循环结束则为找到该大值,将之赋值给arr[pivot]
arr[pivot] = arr[begin];
//自己形成新的坑位
pivot = begin;
}
//循环结束代表begin和end相遇，并且相遇在坑（pivot）
pivot = begin;//这里给begin和end都可以
//将key放到pivot
arr[pivot] = key;
}

2.5 挖坑法总体代码实现

单趟排完后，已经有一个值被放到了正确的位置，以该值做分割，此时区间被分为左右两个子区间，然后对左右两个子区间进行递归即可。

#include<stdio.h>
void Print(int* arr, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
}
void QuickSort(int* arr, int left,int right)
{
//当区间被分到只有1个元素时，则返回
//=代表只有一个元素，>代表没有右区间，为什么会出现大于可以看下面递归图
if (left >= right)
{
return;
}
int begin = left;
int end = right;
int key = arr[begin];
int pivot = begin;
while (begin < end)
{
//pivot在begin那边，则end这边找比key小
while (begin < end&&arr[end] >= key)
{
end--;
}
//循环结束则为找到该小值,将之赋值给arr[pivot]
arr[pivot] = arr[end];
//自己形成新的坑位
pivot = end;
//piovt在end那边，则begin这边找比key大
while (begin < end&&arr[begin] <= key)
{
begin++;
}
//循环结束则为找到该大值,将之赋值给arr[pivot]
arr[pivot] = arr[begin];
//自己形成新的坑位
pivot = begin;
}
//循环结束代表begin和end相遇，并且相遇在坑（pivot）
pivot = begin;//这里给begin和end都可以
//将key放到pivot
arr[pivot] = key;
//将区间分为[left,pivot-1] pivot [pivot+1,right]
//采用分治递归，左边有序了，右边有序了，则整体有序
QuickSort(arr, left, pivot - 1);
QuickSort(arr, pivot + 1, right);
}
void test01()
{
int arr1[] = { 5,8,1,4,9,6,2 };
int n = sizeof(arr1) / sizeof(arr1[0]);
QuickSort(arr1, 0, n - 1);
Print(arr1, n);
}
int main()
{
test01();
return 0;
}

2.6 递归展开图（用于理解）

三、时间复杂度分析

3.1 计算时间复杂度

我们先计算单趟排序的时间复杂度，很简单，单趟排序就是begin和end两个指针往中间一起走知道汇合，将数组遍历了一遍，所以单趟排序的时间复杂度为O(N)。

递归的时间复杂度，我们假设每次取到的数都是中间数，也就是接近二分，看下图:

把它看出一颗完全二叉树，每一层都是N个数，总共有logN层，所以总体的时间复杂度为O(N*logN)。但是这是理想情况，那么最坏情况又是什么时候呢？没错，就是序列有序时最坏。看下图：

每次只排好一个上数，那么我们递归的深度就是N，每趟时间复杂度O(N)，那么N趟下来就是O(N^2)。

3.2 优化最坏时间复杂度（三数取中）

由上面的时间复杂度分析可知，当序列有序时，时间复杂度为O（N^2）。这是因为我们选的key值总是最大或者最小，所以我们只要保证所选的值不是最大或者最小就能达到优化的效果。这里我们采取三数取中。

三数取中基本思想：取序列中的左右中三个数选出中间值最为key值进行排序。

三数取中的代码为：

int GetMinIndex(int* arr,int left,int right)
{
int mid = (left + right) >> 1;
if (arr[left] < arr[mid])
{
if (arr[mid] < arr[right])
{
return mid;
}
if (arr[left] < arr[right] && arr[right] < arr[mid])
{
return right;
}
return left;
}
else//arr[left] >= arr[mid]
{
if (arr[left] < arr[right])
{
return left;
}
if (arr[mid]<arr[right] && arr[right] < arr[left])
{
return right;
}
return mid;
}
}

将之运用到快速排序代码：

void Swap(int* p1, int*p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void QuickSort(int* arr, int left,int right)
{
//当区间被分到只有1个元素时，则返回
if (left >= right)
{
return;
}
int index = GetMinIndex(arr, left, right);
//因为我们下面的逻辑都是把第一个数作为key，
//为了避免改动代码，这里我们直接交换就可以
Swap(&arr[left], &arr[index]);
int begin = left;
int end = right;
int key = arr[begin];
int pivot = begin;
while (begin < end)
{
//pivot在begin那边，则end这边找比key小
while (begin < end&&arr[end] >= key)
{
end--;
}
//循环结束则为找到该小值,将之赋值给arr[pivot]
arr[pivot] = arr[end];
//自己形成新的坑位
pivot = end;
//piovt在end那边，则begin这边找比key大
while (begin < end&&arr[begin] <= key)
{
begin++;
}
//循环结束则为找到该大值,将之赋值给arr[pivot]
arr[pivot] = arr[begin];
//自己形成新的坑位
pivot = begin;
}
//循环结束代表begin和end相遇，并且相遇在坑（pivot）
pivot = begin;//这里给begin和end都可以
//将key放到pivot
arr[pivot] = key;
//将区间分为[left,pivot-1] pivot [pivot+1,right]
//采用分治递归，左边有序了，右边有序了，则整体有序
QuickSort(arr, left, pivot - 1);
QuickSort(arr, pivot + 1, right);
}

采取三数取中后，快排不会出现最快情况，时间复杂度就是O(N*logN)。

以上就是“c语言实现快速排序递归”的详细内容，想要了解更多C语言教程欢迎持续关注编程学习网