首页 > 代码库 > 闲来无事，温习一下快速排序法
闲来无事，温习一下快速排序法
快速排序法，还是很常用的。不论是面试还是写代码。这里说一下怎么coding出快速排序法。至于什么复杂度之类的，请参考http://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F#C.
快速排序法的核心是分治法(Divide and conquer)，也就是把一个数组一分为二，二分为四....直到不能分了，也就完成排序了。所以快速排序法也就是怎么分的问题。怎么分？当然是按大小分了。所以快速排序法的升序步骤描述为：
- 选择一个基准元素
- 交换数组元素。把小于基准值的放到左边；大于基准值放右边；等于的放任意一边。保证基准元素就是分割线的位置。
- 将基准值左、右边的元素作为子数组（都不包括基准元素），重复上面两个步骤直到数组元素数量小于2
现在得出C++下代码：
#include <iostream>using namespace std;#define MAX_ARRAY 10/** * @brief divide 分割数组 * @param list * @param length * @return 分割位置 * 以数组第一个元素为基准分割数组， * 左边为小于基准，右边大于基准 * 以移动分割线的方法实现分割 */int divide( int *list,int length ){ int divide_line = 0; /* 默认分割线 */ int pivot = list[0]; /* 默认选择第一个作为基准 */ swap ( list[0],list[length-1] ); /* 把基准放到最后，这样最后一个永远不会被交换 */ for ( int i = 0;i < length;i ++ ) { if ( list[i] < pivot ) /* 小于基准，要放到分割线左边 */ { swap( list[i],list[divide_line] ); /* 交换 */ /* 小于基准的元素增长，分割线右移,保证分割线(包括分割线)右边都不小于基准 */ divide_line ++; } } swap ( list[divide_line],list[length-1] ); /* 把最后一个交换到分割线，保证分割线值为基准值 */ return divide_line;}/** * @brief conquer 排序子数组 * @param list * @param length * 将数组进行分割，并对子数组进行排序 */void conquer( int *list,int length ){ if ( length <= 1 ) //已分解为一个元素不再分解 return; int divide_line = divide( list,length ); /* 得到分割线 */ conquer( list,divide_line ); //排序左边的数组 conquer( list+divide_line+1,length - divide_line - 1 ); //排序右边的数组,基准值不再需要排序}/** * @brief quick_sort 快速排序法 * @param list * @param length * 快速排序法 */void quick_sort( int *list,int length ){ conquer( list,length );}int main(){ int list[MAX_ARRAY] = { 9,0,1,3,5,8,4,6,2,7 }; quick_sort( list,MAX_ARRAY ); for ( int i = 0;i < MAX_ARRAY;i ++ ) { cout << list[i] << " "; } cout << endl; return 0;}
当然，这只是一个原始的版本，旨在说明快速排序法的算法。当然还有更高级的版本，更优化的版本。一般情况下，我基本不会自己再去写一个快速排序法。现在C、C++的库都已包含大量排序算法。
C里的快速排序法linux下man qsort即可看到用法及用例。
闲来无事，温习一下快速排序法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。