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 <stdio.h> #include <stdlib.h> #define N 6 int partition(int arr[], int low, int high){ int key; key = arr[low]; while(low<high){ while(low <high && arr[high]>= 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; return low; } void quick_sort(int arr[], int start, int end){ int pos; if (start<end){ pos = partition(arr, start, end); quick_sort(arr,start,pos-1); quick_sort(arr,pos+1,end); } return; } int main(void){ int i; int arr[N]={32,12,7, 78, 23,45}; printf("排序前 \n"); for(i=0;i<N;i++) printf("%d\t",arr[i]); quick_sort(arr,0,N-1); printf("\n 排序后 \n"); for(i=0; i<N; i++) printf("%d\t", arr[i]); printf ("\n"); system("pause"); return 0; }
运行结果:
排序前
32 12 7 78 23 45
排序后
7 12 23 32 45 78
在上面的代码中,根据前面介绍的步骤一步步实现了快速排序算法。接下来通过示意图来演示第一次划分操作。
在第一次划分操作中,先进行初始设置,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语言快速排序的详解,希望能帮助学习 C语言的同学掌握快速排序算法.
相关文章
- 这篇文章主要为大家详细介绍了C语言实现放烟花的程序,有音乐播放,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-02-23
- 本篇文章主要介绍C语言中char的知识,并附有代码实例,以便大家在学习的时候更好的理解,有需要的可以看一下...2020-04-25
- 这篇文章主要介绍了详解如何将c语言文件打包成exe可执行程序,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-25
- free函数是释放之前某一次malloc函数申请的空间,而且只是释放空间,并不改变指针的值。下面我们就来详细探讨下...2020-04-25
- 这篇文章主要介绍了C语言中计算正弦的相关函数总结,包括正弦和双曲线正弦以及反正弦的函数,需要的朋友可以参考下...2020-04-25
详解C语言中的rename()函数和remove()函数的使用方法
这篇文章主要介绍了详解C语言中的rename()函数和remove()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25- 这篇文章主要介绍了C语言中求和、计算平均值、方差和标准差的实例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-12-10
- 本篇文章主要讲解C语言 基本语法,这里提供简单的示例和代码来详细讲解C语言的基本语法,开始学习C语言的朋友可以看一下,希望能够给你带来帮助...2021-09-18
- 这篇文章主要为大家详细介绍了js实现数组冒泡排序、快速排序的原理,感兴趣的小伙伴们可以参考一下...2016-03-10
- 这篇文章主要介绍了C语言中send()函数和sendto()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25
- 今天小编就为大家分享一篇C语言实现从文件读入一个3*3数组,并计算每行的平均值,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-04-25
- 这篇文章主要介绍了C语言中memcpy 函数的用法详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了使用C语言操作文件的基本函数整理,包括创建和打开以及关闭文件的操作方法,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言中查找字符在字符串中出现的位置的方法,分别是strchr()函数和strrchr()函数的使用,需要的朋友可以参考下...2020-04-25
- 很多同学在学习c语言的时候是不是会碰到a++和++a都有甚么作用啊。今天我们就来探讨下...2020-04-25
- 这篇文章主要对C语言中const关键字的用法进行了详细的分析介绍,需要的朋友可以参考下...2020-04-25
- 下面小编就为大家带来一篇C语言实现时间戳转日期的算法(推荐)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2020-04-25
- 这篇文章主要介绍了C语言之整数划分问题(递归法)实例代码的相关资料,需要的朋友可以参考下...2020-04-25
C语言正则表达式详解 regcomp() regexec() regfree()用法详解
C语言处理正则表达式常用的函数有regcomp()、regexec()、regfree()和regerror(),这里就为大家介绍一下,需要的朋友可以参考一下啊...2020-04-25- 本文给大家简单介绍下c实现linux下的数据库备份的方法和具体的源码,十分的实用,有需要的小伙伴可以参考下。...2020-04-25