C语言实现快速排序算法
更新时间:2020年4月25日 17:27 点击:1434
一、快速排序算法(Quicksort)
1. 定义
快速排序由C. A. R. Hoare在1962年提出。快速排序是对冒泡排序的一种改进,采用了一种分治的策略。
2. 基本思想
通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
3. 步骤
a. 先从数列中取出一个数作为基准数。
b. 分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。
c. 再对左右区间重复第二步,直到各区间只有一个数。
二、C语言实现代码(仅供参考)
/***************************************************** File name:Quicksort Author:Zhengqijun Version:1.0 Date: 2016/11/04 Description: 对数组进行快速排序 Funcion List: 实现快速排序算法 *****************************************************/ #include <stdio.h> #include <stdlib.h> #define BUF_SIZE 10 /************************************************** *函数名:display *作用:打印数组元素 *参数:array - 打印的数组,maxlen - 数组元素个数 *返回值:无 **************************************************/ void display(int array[], int maxlen) { int i; for(i = 0; i < maxlen; i++) { printf("%-3d", array[i]); } printf("\n"); return ; } /******************************** *函数名:swap *作用:交换两个数的值 *参数:交换的两个数 *返回值:无 ********************************/ void swap(int *a, int *b) { int temp; temp = *a; *a = *b; *b = temp; return ; } /************************************ *函数名:quicksort *作用:快速排序算法 *参数: *返回值:无 ************************************/ void quicksort(int array[], int maxlen, int begin, int end) { int i, j; if(begin < end) { i = begin + 1; // 将array[begin]作为基准数,因此从array[begin+1]开始与基准数比较! j = end; // array[end]是数组的最后一位 while(i < j) { if(array[i] > array[begin]) // 如果比较的数组元素大于基准数,则交换位置。 { swap(&array[i], &array[j]); // 交换两个数 j--; } else { i++; // 将数组向后移一位,继续与基准数比较。 } } /* 跳出while循环后,i = j。 * 此时数组被分割成两个部分 --> array[begin+1] ~ array[i-1] < array[begin] * --> array[i+1] ~ array[end] > array[begin] * 这个时候将数组array分成两个部分,再将array[i]与array[begin]进行比较,决定array[i]的位置。 * 最后将array[i]与array[begin]交换,进行两个分割部分的排序!以此类推,直到最后i = j不满足条件就退出! */ if(array[i] >= array[begin]) // 这里必须要取等“>=”,否则数组元素由相同的值时,会出现错误! { i--; } swap(&array[begin], &array[i]); // 交换array[i]与array[begin] quicksort(array, maxlen, begin, i); quicksort(array, maxlen, j, end); } } // 主函数 int main() { int n; int array[BUF_SIZE] = {12,85,25,16,34,23,49,95,17,61}; int maxlen = BUF_SIZE; printf("排序前的数组\n"); display(array, maxlen); quicksort(array, maxlen, 0, maxlen-1); // 快速排序 printf("排序后的数组\n"); display(array, maxlen); return 0; }
执行程序后的结果如下所示:
上诉代码结合了我自己对快速排序的看法和理解,仅供参考。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持猪先飞。
上一篇: C语言中求字符串长度的函数的几种实现方法
下一篇: 详解c++种gmock单元测试框架
相关文章
- 这篇文章主要为大家详细介绍了C语言实现放烟花的程序,有音乐播放,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-02-23
- 本篇文章主要介绍C语言中char的知识,并附有代码实例,以便大家在学习的时候更好的理解,有需要的可以看一下...2020-04-25
- 作者:Sabine 【导读】本文介绍了C#的四种排序算法:冒泡排序、选择排序、插入排序和希尔排序 冒泡排序 using System; namespace BubbleSorter { public class Bubb...2020-06-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
图文详解Heap Sort堆排序算法及JavaScript的代码实现
这篇文章以图文详解Heap Sort堆排序算法及JavaScript的代码实现,堆排序算法基于类二叉树的堆数据结构,需要的朋友可以参考下...2016-05-05- 这篇文章主要介绍了C语言中send()函数和sendto()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25
- 今天小编就为大家分享一篇C语言实现从文件读入一个3*3数组,并计算每行的平均值,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-04-25
- 这篇文章主要介绍了使用C语言操作文件的基本函数整理,包括创建和打开以及关闭文件的操作方法,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言中memcpy 函数的用法详解的相关资料,需要的朋友可以参考下...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实现linux下的数据库备份的方法和具体的源码,十分的实用,有需要的小伙伴可以参考下。...2020-04-25