算法基础之快速排序算法和代码

作者:课课家更新于： 2016-12-02 15:48:43

　　C语言中的算法多种多样，在之前的学习中我们了解了选择排序算法、冒泡排序算法和插入排序算法，因此今天课课家笔者给大家简单介绍C语言中的快速排序算法和代码。那么到底什么是C语言中的快速排序算法呢？它的具体编写运算是怎么样的呢？下面由笔者给大家慢慢一一道来。

　　所谓快速排序（Quicksort），它其实是冒泡法排序的一种改进算法，在之前的学习中我们了解到冒泡排序的概念为重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。快速排序算法的基本思想是：将所要进行排序的数分为左右两个部分，其中一部分的所有数据都比另外一部分的数据小，然后将所分得的两部分数据进行同样的划分，重复执行以上的划分操作，直到所有要进行排序的数据变为有序为止。接下来笔者以对n个无序数列A[0],A[1]…,A[n-1]采用快速排序方法进行升序排列为例给大家进行讲解，具体分为以下6个步骤：

　　①定义两个变量low和high，将low、high分别设置为要进行排序的序列的起始元素和最后一个元素的下标。第一次，low和high的取值分别为0和n-1，接下来的每次取值由划分得到的序列起始元素和最后一个元素的下标来决定。

　　②定义一个变量key并以key的取值为基准将数组A划分为左右两个部分，通常key值为要进行排序序列的第一个元素值。第一次的取值为A[0]，以后毎次取值由要划分序列的起始元素决定。

　　③从high所指向的数组元素开始向左扫描，扫描的同时将下标为high的数组元素依次与划分基准值key进行比较操作，直到high不大于low或找到第一个小于基准值key的数组元素，然后将该值赋值给low所指向的数组元素，同时将low右移一个位置。

　　④如果low依然小于high，那么由low所指向的数组元素开始向右扫描，扫描的同时将下标为low的数组元素值依次与划分的基准值key进行比较操作，直到low不小于high或找到第一个大于基准值key的数组元素，然后将该值赋给high所指向的数组元素，同时将high左移一个位置。

　　⑤重复步骤3、4，直到low的植不小于high为止，这时成功划分后得到的左右两部分分别为A[low……pos-1]和A[pos+1……high]，其中pos下标所对应的数组元素的值就是进行划分的基准值key，所以在划分结束时还要将下标为pos的数组元素赋值为key。

　　⑥将划分得到的左右两部分A[low……pos-1]和A[pos+1……high]继续采用以上操作步骤进行划分，直到得到有序序列为止。

　　看完上面的步骤解释可能大家还是一头雾水，为了使大家加深对此的理解，接下来笔者通过一段代码来让大家更明了的了解快速排序的具体实现方法。

　　#include

　　#include

　　#defineN6

　　intpartition(intarr[],intlow,inthigh){

　　intkey;

　　key=arr[low];

　　while(low

　　while(low=key)

　　high--;

　　if(low

　　arr[low++]=arr[high];

　　while(low

　　low++;

　　if(low

　　arr[high--]=arr[low];

　　}

　　arr[low]=key;

　　returnlow;

　　}

　　voidquick_sort(intarr[],intstart,intend){

　　intpos;

　　if(start

　　pos=partition(arr,start,end);

　　quick_sort(arr,start,pos-1);

　　quick_sort(arr,pos+1,end);

　　}

　　return;

　　}

　　intmain(void){

　　inti;

　　intarr[N]={32,12,7,78,23,45};

　　printf("排序前\\n");

　　for(i=0;i

　　printf("%d\\t",arr[i]);

　　quick_sort(arr,0,N-1);

　　printf("\\n排序后\\n");

　　for(i=0;i

　　printf("%d\\t",arr[i]);

　　printf("\\n");

　　system("pause");

　　return0;

　　}

　　输出结果：

　　排序前

　　32127782345

　　排序后

　　71223324578

　　在上面的代码中，我们根据前面介绍的步骤一步步实现快速排序算法。接下来笔者通过示意图来演示第一次划分操作，共5个步骤，以下是具体的示意图：

　　①在第一次划分操作中，首先我们进行初始设置，key的值是进行划分的基准，其值为要划分数组的第一个元素值，在上面的排序序列中为第一个元素值32，同时将low设置为要排序数组中第一个元素的下标，第一次排序操作时其值为0，将high设置为要排序序列最后一个元素的下标，在上面的排序序列中其第一次取值为5。

　　②将下标为high的数组元素与key进行比较，由于该元素值大于key，因此high向左移动一个位置继续扫描。由于接下来的值为23，小于key的值，因此将23赋值给下标为low所指向的数组元素。

　　③接下来将low右移一个位置，将low所指向的数组元素的值与key进行比较，由干接下来的12、7都小于key，因此low继续右移扫描，直至下标low所指向的数组元素的值为78即大于key为止，将78赋值给下标为high所指向的数组元素，同时将high左移一个位置。

　　④由于low不再小于high，划分结束。此时我们需要注意的地方是，在进行划分的过程中，都是将扫描的值与key的值进行对比，如果小于key，那么将该值赋值给数组中的另外一个元素，而该元素的值并没有改变，从上图中我们可以清楚看出这一点，所以需要在划分的最后将作为划分基准的key值赋值给下标为pos的数组元素，这个元素不再参与接下来的划分操作。

　　⑤第一轮划分结束后，得到了左右两部分序列A[0]、A[1]、A[2]和A[4]、A[5]，接下来我们继续进行划分，也就是对毎轮划分后得到的两部分序列继续划分，直至得到有序序列为止。

　　以上就是快速排序方法具体的实现。

　　本次算法基础之快速排序算法和代码的讲解到此暂告一段落，如果以后有什么相关的内容进行补充或者修改的话，笔者会继续在此进行相关内容的补充或者修改的工作，同时也欢迎大家对本次的讲解提出自己的建议和补充。最后笔者希望本次的讲解对大家学习C语言能够起到一定的帮助作用！