C语言快速排序算法及代码.docx

C语言快速排序算法及代码C语言快速排序算法及代码快速排序是对冒泡法排序的一种改进。那么有关C语言快速排序算法和代码分别又是怎样的呢？以下仅供参考！快速排序算法的基本思想是：将所要进行排序的数分为左右两个部分，其中一部分的所有数据都比另外一部分的数据小，然后将所分得的两部分数据进行同样的划分，重复执行以上的划分操作，直到所有要进行排序的数据变为有序为止。可能仅根据基本思想对快速排序的认识并不深，接下来以对n个无序数列A[0],A[1]…,A[n-1]采用快速排序方法进行升序排列为例进行讲解。(1)定义两个变量low和high，将low、high分别设置为要进行排序的序列的起始元素和最后一个元素的下标。第一次，low和high的取值分别为0和n-1，接下来的每次取值由划分得到的序列起始元素和最后一个元素的下标来决定。(2)定义一个变量key，接下来以key的取值为基准将数组A划分为左右两个部分，通常，key值为要进行排序序列的第一个元素值。第一次的取值为A[0]，以后毎次取值由要划分序列的起始元素决定。(3)从high所指向的数组元素开始向左扫描，扫描的同时将下标为high的数组元素依次与划分基准值key进行比较操作，直到high不大于low或找到第一个小于基准值key的数组元素，然后将该值赋值给low所指向的数组元素，同时将low右移一个位置。(4)如果low依然小于high，那么由low所指向的数组元素开始向右扫描，扫描的同时将下标为low的数组元素值依次与划分的基准值key进行比较操作，直到low不小于high或找到第一个大于基准值key的数组元素，然后将该值赋给high所指向的数组元素，同时将high左移一个位置。(5)重复步骤(3)(4)，直到low的植不小于high为止，这时成功划分后得到的左右两部分分别为A[low……pos-1]和A[pos+1……high]，其中，pos下标所对应的数组元素的值就是进行划分的基准值key，所以在划分结束时还要将下标为pos的数组元素赋值为key。(6)将划分得到的左右两部分A[low……pos-1]和A[pos+1……high]继续采用以上操作步骤进行划分，直到得到有序序列为止。为了能够加深读者的理解，接下来通过一段代码来了解快速排序的具体实现方法。#include#include#defineN6intpartition(intarr[],intlow,inthigh){intkey;key=arr[low];while(low<high){while(low=key)high--;if(low<high)arr[low++]=arr[high];while(low<high&&arr[low]<=key)low++;if(low<high)arr[high--]=arr[low];}arr[low]=key;returnlow;}voidquick_sort(intarr[],intstart,intend){intpos;if(start<end){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("排序前");for(i=0;i<N;i++)printf("%d",arr[i]);quick_sort(arr,0,N-1);printf("排序后");for(i=0;i<N;i++)printf("%d",arr[i]);printf("");system("pause");return0;}运行结果：排序前32127782345排序后71223324578在上面的代码中，根据前面介绍的步骤一步步实现了快速排序算法。接下来通过示意图来演示第一次划分操作。在第一次划分操作中，先进行初始设置，key的值是进行划分的基准，其值为要划分数组的第一个元素值，在上面的`排序序列中为第一个元素值32，同时将low设置为要排序数组中第一个元素的下标，第一次排序操作时其值为0，将high设置为要排序序列最后一个元素的下标，在上面的排序序列中其第一次取值为5。先将下标为high的数组元素与key进行比较，由于该元素值大于key，因此high向左移动一个位置继续扫描。由于接下来的值为23，小于key的值，因此将23赋值给下标为low所指向的数组元素。接下来将low右移一个位置