快速排序算法，快速排序算法 c语言

　　近日流行快速排序算法的有个以教育为目的帮助学习主要算法的python模块：pygorithm

　　使用pip3 install pygorithm安装后

　　就可以看到相应算法的实现代码了快速排序算法，还是挺方便的。主要运用了inspect标准库中的getsource函数：

　　顺便复习下利用分治思想的两大排序算法：归并排序和快速排序。

　　归并排序简述

归并排序(merge_sort)是分治思想的一个典型应用。

　　分治的简单理解就是将大问题分解为两个或多个更简单的小问题，组合小问题的解得到原问题的答案。

在归并排序中，对原数组排序等同于将原数组分为具有相近大小的两份，对这两个数组分别排序，然后合并它们。

图解与实现

对一乱序的英文字母列表排序，将其分为两半，分别对左右两部分排序，然后合并排序结果。

　　下图来自维基百科：将一个无序的数组自顶向下递归分解，每次二分，直到每份只有一个数，然后将它们逐层合并为有序数组，生成最终的排序结果。（分解与合并是对称的，即分解的过程限定了合并的路径）。

　　用代码表示上述过程

　　其中merge()为合并多个有序数组的函数：

　　输出，与图示相符：

　　merge()的简单实现，如何合并两个有序数组：对两个数组的队首元素进行比较，取出其中小的放入新数组，对取出该数后的两个数组的队首元素再进行比较，如此循环直到某一数组为空，将另一非空数组中的所有数按原序添加至新数组即可。

　　如对(b)中两个数组S1和S2，比较队首24和31的大小，选择较小的24放入新数组S的17的后面。

用代码表示上述过程

　　另一版本：

　　输出，与图示相符：

　　快速排序简述

快速排序同样应用了分治的思想。

　　回顾：分治是将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。

类似于归并排序，快排也是将要排序的原数组分成两份（这里不保证它们的大小相似），对这两个数组分别排序，然后合并它们。

不过，归并排序在分解时很轻松（直接二分），合并时比较费力（对两个有序子数组中的元素做了大量比较）快速排序算法；而快速排序在分割为两份时比较费力，要先从数组中任意选择一个基准数，使得分割得到的两份子数组中，一份中的所有数都小于该基准数，而另一份中所有数都大于它，而合并的时候，由于一组中所有数都比另一组所有数小，可以直接合并（在基准数两侧），所以合并很轻松。

图解与实现

代码实现:

　　另一版本（思路基本一致）：

这样看来用python实现真是非常简单，但是运算量较大，我们从C语言的角度看看如何实现分割过程的。

假设要对如下数组进行排序，我们选择第一个值72作为基准数。

　　实现分割，最简单的思路便是单方向逼近，如从最右边开始（索引j=9），将小于或等于基准数的值移动到基准数左边。

　　进一步，从左右两边逼近，将小于或等于基准数的值移动到基准数左边，且将大于基准数的值移动到基准数右边

　　代码

上一篇： REPLACEINTO，replaceinto语法

下一篇： 深入浅出hibernate，深入浅出小说