前言：C语言实现快速排序及其系统优化和分析

目录

一.快速排序的实现

1.实现思路

2.QSort实现

3.函数Partition()的实现

4.完整代码

 二.对快速排序的系统优化

1.对关键字pivotkey的选择优化

2.优化不必要的交换（把交换变成赋值）

3.优化递归操作

4.！！！！优化后的完整代码！！！！！

 三.结语

快速排序的基本思路是：先在待排序数组中随便找一个数（其实找这个数也是有技巧的，后面会讲到），这个数也称作关键字，通过一趟排序将数组分成左右两部分，左边的部分都比关键字小，中间是关键字，右边的部分都比关键字大。然后左右两部分又可以继续进行和刚刚一样的排序，直到整个数组有序。

例如

无序数组 26,1,7,56,34,23,77,87,22,43,16,66

1.我们先选出一个关键字，例如选了26

2.经过第一次排序后   就分成左右两部分  左边的部分比关键字小   中间是关键字  右边的部分比关键字大  

即16 1 7 22 23     26      77 87 34 43 56 66

3. 16 1 7 22 23 是左边部分

4.  26是关键字，即中间部分

5. 77 87 34 43 56 66 是右边部分

6.然后我们就可以对左右两部分继续这样的操作，所以快速排序的核心代码，就是如何把数组分成左右两部分！！是不是听起来很简单！！接下来我们就来实现

这里随便定义了一个数组int arr[] = { 26,1,7,56,34,23,77,87,22,43,16,66 }，我们要做的就是在"pivot = Partition(arr, low, high)"中获取关键字的下标，并把数组变成 ：

1.关键字在中间

2.关键字的左边均小于等于关键字的数值 

3.关键字的右边均大于等于关键字的数值

这也是函数Partition()的功能，所以接下来我们就要想办法实现函数Partition()。

经过依次Partition()后，数组arr[]就变成了arr= 16 1 7 22 23     26      77 87 34 43 56 66以数组arr首元素26为中心的两部分，26右边的都比26大，26左边的都比26小，接着再次对左右两边继续递归排序就可以了，也就是下图画红线的两句代码

运行效果：

  前面我们为了方便，都是选择数组的第一个元素当作关键字，这么随意肯定会有不好的地方，例如刚刚的待排序数组变成了arr[] = { 1,26,7,56,34,23,77,87,22,43,16,66 }，若我们选择了第一个元素1，和选择其它任何一个数相比，很明显选择1就会显得很不合理，所以我们刚开始选择的关键字对我们排序速度的快慢有很大的影响。

  因此，我们想出了一个办法，在数组的左 中 右分别取一个数，然后再拿这三个数居中的那一个来当关键字pivotkey。在规模较小的排序中，这的确是一个好办法，但是在规模较大的数组中，其作用也是微乎其微，所以在规模较大的排序中，有时也有27数取9再取3再取1，也有9取3再取1的，其道理都一样，就是为了找出一个合适的关键字，加快排序的速度。

因此我们在确定关键字pivotkey前加上这几行代码

函数Paritition()就变成了这样

我们只需在把数组分成左右两部分之前，将关键字备份一份，然后在排序的过程中，数字间的交换直接改成赋值，会少了很多交换的步骤

原理也是一样，在右边找到小的数，赋值到左边   在左边找大的数，赋值到右边   反正到最后，low和high都会同时指向关键字的下标，这时再把关键字的值还给它就得了。

经过上面几番操作，我们的Partition()函数变成了这样

我们将QSort()的函数改为

这样我们就减少了递归的次数，速度大大提高！！

运行效果

其实很多计算机语言的库函数都有快速排序这个函数，虽然各有不同，但是效果和速度都是差不多的，如果大家对C语言的快速排序库函数qsort感兴趣的话，可以翻阅博主的另一篇关于qsort的讲解，非常详细~最后大家有什么不懂的欢迎留言~

✨喜欢和觉得有用的不妨点个赞和关注吧~❤️