上节介绍了如何使用起泡排序的思想对无序表中的记录按照一定的规则进行排序,本节再介绍一种排序算法——快速排序算法(Quick Sort)。
C语言中自带函数库中就有快速排序——qsort函数 ,包含在 <stdlib.h> 头文件中。
快速排序算法是在起泡排序的基础上进行改进的一种算法,其实现的基本思想是:通过一次排序将整个无序表分成相互独立的两部分,其中一部分中的数据都比另一部分中包含的数据的值小,然后继续沿用此方法分别对两部分进行同样的操作,直到每一个小部分不可再分,所得到的整个序列就成为了有序序列。
例如,对无序表{49,38,65,97,76,13,27,49}
进行快速排序,大致过程为:
{27,38,13,49,65,97,76,49}
;
{27,38,13}
和{65,97,76,49}
,继续采用此种方法分别对两个子表进行排序;
{13,27,38}
,此部分已经有序;后部分子表以 65 为支点,排序后的子表为{49,65,97,76}
;
{49}
和{97,76}
,前者不需排序,后者排序后的结果为{76,97}
;
整个过程中最重要的是实现第 2 步的分割操作,具体实现过程为:
该操作过程的具体实现代码为:
//交换两个记录的位置 //快速排序,分割的过程 //直到两指针相遇,程序结束 //high指针左移,直至遇到比pivotkey值小的记录,指针停止移动 //交换两指针指向的记录 //low 指针右移,直至遇到比pivotkey值大的记录,指针停止移动 //交换两指针指向的记录
该方法其实还有可以改进的地方:在上边实现分割的过程中,每次交换都将支点记录的值进行移动,而实际上只需在整个过程结束后(low==high),两指针指向的位置就是支点记录的准确位置,所以无需每次都移动支点的位置,最后移动至正确的位置即可。
所以上边的算法还可以改写为:
//此方法中,存储记录的中,下标为 0 的位置时空着的,不放任何记录,记录从下标为 1 处开始依次存放 //直到两指针相遇,程序结束 //high指针左移,直至遇到比pivotkey值小的记录,指针停止移动 //直接将high指向的小于支点的记录移动到low指针的位置。 //low 指针右移,直至遇到比pivotkey值大的记录,指针停止移动 //直接将low指向的大于支点的记录移动到high指针的位置 //将支点添加到准确的位置
//此方法中,存储记录的数组中,下标为 0 的位置时空着的,不放任何记录,记录从下标为 1 处开始依次存放 //直到两指针相遇,程序结束 //high指针左移,直至遇到比pivotkey值小的记录,指针停止移动 //直接将high指向的小于支点的记录移动到low指针的位置。 //low 指针右移,直至遇到比pivotkey值大的记录,指针停止移动 //直接将low指向的大于支点的记录移动到high指针的位置 //将支点添加到准确的位置 //对支点左侧的子表进行排序 //对支点右侧的子表进行排序
为O(nlogn)
,是所有时间复杂度相同的排序方法中性能最好的排序算法。
版权声明:文章内容来源于网络,版权归原作者所有,如有侵权请点击这里与我们联系,我们将及时删除。