文档章节

排序篇 - 快速排序的实现

狮子的魂
 狮子的魂
发布于 2012/10/20 23:28
字数 1203
阅读 186
收藏 0

快速排序这个名字来源于它的实际效率。它也是使用分治算法实现的一种排序算法,对于基本数据类型的排序,它比归并排序的实际效率高些(100万数据的话,排序时间稳定为归并排序的1/2的样子)。

算法时间复杂度为O(N*logN),最坏算法为O(N^2),但是通过实际的编程可以避免这种情况的出现。

该算法的核心问题在于找“pivot(枢纽元)”(可以有效的避免O(n^2)的出现),和“分割策略”。本实现采用”左中又三值分割“法来获取枢纽元。

本实现中,对于小数据量,我采用的是”插入排序“来代替。

这里不介绍算法的具体过程,给出C和Java的实现(维基百科的实现,也是我写的。代码用了很久了,可以直接拿来用,已泛型化)。

C的实现:


/*
 * quick sort implements functions.
 * 
 * @author chenxin
 * @see http://www.webssky.com 
 */
#include <stdlib.h>
#include "jsort.h"

#define CUTOFF 11


/*
 * a static method to swap the value.
 * 
 * @param * the first pointer.
 * @param * the second pointer.
 * @param size the bytes of one item.
 */
void swap_value( void *a, void *b, size_t size ) {
	
	unsichar_t *__a = ( unsichar_t * ) a;
	unsichar_t *__b = ( unsichar_t * ) b;
	register unsichar_t tmp;
	
	do {
		tmp = *__a;
		*__a++ = *__b;
		*__b++ = tmp;
	} while ( --size > 0 ) ;
}

/*
 * a static function to get the median of the partition.
 * 
 * @param *a the pointer of the array to be sort.
 * @param left the left-most index of the subarray.
 * @param right the right-most index of the subarray.
 * @param comp the compare function pointer. 
 */
static unsichar_t *median( unsichar_t *a, size_t size, \
		compare_fn_t comp, size_t left, size_t right ) {
	register size_t center = ( left + right ) / 2;
	
	unsichar_t *lp = a + left * size;
	unsichar_t *cp = a + center * size;
	unsichar_t *rp = a + right * size;
	
	if ( comp( lp, cp ) > 0 )
		swap_value( lp, cp, size );
	if ( comp( lp, rp ) > 0 )
		swap_value( lp, rp, size );
	if ( comp( cp, rp ) > 0 )
		swap_value( cp, rp, size );
		
	//move the pivot to the right - a positon.
	swap_value( cp, rp - size, size );
	//return the pivot
	return rp - size;
	
}


/*
 * a static function to do the partition.
 * @see quicksort( void *, size_t, size_t, compare_fn_t );
 */
static void quick_sort( unsichar_t *a, size_t size, \
		compare_fn_t comp, size_t left, size_t right ) {
	if ( left + CUTOFF <= right ) {
		//get the privot of the subarray.
		unsichar_t *pivot = median( a, size, comp, left, right );
		//printf("pivot=%d\n", * (( int * ) pivot));
		//start partitioning.
		register i = left, j = right - 1;
		for ( ; ; ) {
			while ( comp( a + (++i * size), pivot ) < 0 ) ;
			while ( comp( a + (--j * size), pivot ) > 0) ;
			if ( i < j ) 
				swap_value( a + i * size, a + j * size, size );
			else
				break;
		}
		//printf("i=%d, j=%d\n", i, j);
		//swap the privot back to the small colleciton.
		//swap( a + i * size, a + ( right - 1 ) * size, size );
		swap_value( a + i * size, pivot, size );
		
		quick_sort( a, size, comp, left, i - 1 );		//sort the small collection
		quick_sort( a, size, comp, i + 1, right);
		
	} else {
		//if the number of the items is less than CUTOFF use insertion sort instead.
		insertion_sub_sort( a, size, comp, left, right );
	}
}

/*
 * quick sort algorithm.
 * 
 * @param *a the pointer of the array to be sort.
 * @param len the length of the array.
 * @param size the bytes of one item in the array.
 * @param comp the compare function pointer. 
 */
void quicksort( void *a, size_t len, size_t size, compare_fn_t comp ) {
	unsichar_t *__a = ( unsichar_t * ) a;
	quick_sort( __a, size, comp, 0, len - 1 );
}


jsort.h头文件可以在“排序篇 - 插入排序的实现”中找到。

Java的实现:


/**
	 * method to swap elements in an array.<br />
	 * 
	 * @param arr an array of Objects. <br />
	 * @param idx1 the index of the first element. <br />
	 * @param idx2 the index of the second element. <br />
	 */
	public static <T> void swapReferences( T[] arr, int idx1, int idx2 ) {
		T tmp = arr[idx1];
		arr[idx1] = arr[idx2];
		arr[idx2] = tmp;
	}
	
	public static final int CUTOFF = 11; /**
	 * quick sort algorithm. <br />
	 * 
	 * @param arr an array of Comparable items. <br />
	 */
	public static <T extends Comparable<? super T>> void quicksort( T[] arr ) {
		quicksort( arr, 0, arr.length - 1 );
	}
	
	/**
	 * get the median of the left, center and right. <br />
	 * order these and hide the pivot by put it the end of
	 * of the array. <br />
	 * 
	 * @param arr an array of Comparable. <br />
	 * @param left the most-left index of the subarray. <br />
	 * @param right the most-right index of the subarray.<br />
	 * @return T
	 */
	public static <T extends Comparable<? super T>>
	T median( T[] arr, int left, int right ) {
		
		int center = ( left + right ) / 2;
		
		if ( arr[left].compareTo( arr[center] ) > 0 )
			swapReferences( arr, left, center );
		if ( arr[left].compareTo( arr[right] ) > 0 )
			swapReferences( arr, left, right );
		if ( arr[center].compareTo( arr[right] ) > 0 )
			swapReferences( arr, center, right );
		
		swapReferences( arr, center, right - 1 );
		return arr[ right - 1 ];
	}
	
	/**
	 * method to sort an subarray from start to end
	 * 		with insertion sort algorithm. <br />
	 * 
	 * @param arr an array of Comparable items. <br />
	 * @param start the begining position. <br />
	 * @param end the end position. <br />
	 */
	public static <T extends Comparable<? super T>> 
	void insertionSort( T[] arr, int start, int end ) {
		int i;
		for ( int j = start + 1; j <= end; j++ ) {
			T tmp = arr[j];
			for ( i = j; i > start && tmp.compareTo( arr[i - 1] ) < 0; i-- ) {
				arr[ i ] = arr[ i - 1 ];
			}
			if ( i < j ) arr[ i ] = tmp;
		}
	}
	
	/**
	 * internal method to sort the array with quick sort algorithm. <br />
	 * 
	 * @param arr an array of Comparable Items. <br />
	 * @param left the left-most index of the subarray. <br />
	 * @param right the right-most index of the subarray. <br />
	 */
	private static <T extends Comparable<? super T>> 
	void quicksort( T[] arr, int left, int right ) {
		if ( left + CUTOFF <= right  ) {
			//find the pivot
			T pivot = median( arr, left, right );
			
			//start partitioning
			int i = left, j = right - 1;
			for ( ; ; ) {
				while ( arr[++i].compareTo( pivot ) < 0 ) ;
				while ( arr[--j].compareTo( pivot ) > 0 ) ;
				if ( i < j )
					swapReferences( arr, i, j );
				else
					break;
			}
			
			//swap the pivot reference back to the small collection.
			swapReferences( arr, i, right - 1 );
			
			quicksort( arr, left, i - 1 );		//sort the small collection.
			quicksort( arr, i + 1, right );		//sort the large collection.
			
		} else {
			//if the total number is less than CUTOFF we use insertion sort instead.
			insertionSort( arr, left, right );
		}
	}


看到主程序中的高效的循环了,这是快速排序快于归并排序的主要原因。

这个主程序,只有在采用“三值分割法”取枢纽元的前提下才不会出问题。

(仔细想想?快速选择算法是不是出来了)。

有问题我们一起讨论。

© 著作权归作者所有

共有 人打赏支持
狮子的魂

狮子的魂

粉丝 205
博文 11
码字总数 11922
作品 7
深圳
CEO
私信 提问
对于JavaScript实现排序算法的一些其他测试

在我的上一篇文章中,总结了六种排序算法的JavaScript实现,以及每种算法的思想,掘金上的许多盆友提出了一些好的想法或者优化的方法,这里针对这些方法做一些新的测试,以验证盆友们的说法。...

DM.Zhong
2018/05/25
0
0
java排序之快速排序、归并排序、基数排序

前两篇说了Java排序中的冒泡、选择、插入、希尔等排序算法,今天就探讨一下剩下的三种常用排序。 快速排序: 当要求时间最快时,就可以用快速排序算法。 选择第一个数为p,小于p的数放在左边...

野小疯
2018/06/05
0
0
线程基础:多任务处理(16)——Fork/Join框架(排序算法性能补充)

1、概述 在之前的一篇文章《线程基础:多任务处理(13)——Fork/Join框架(解决排序问题)》中,我们使用了fork/join框架提高归并排序的性 能。那篇文章发布后,有的读者联系我,觉得单就归...

yinwenjie
2017/06/06
0
0
算法系列【希尔排序】篇

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: 关于时间复杂度: 1. 平方阶 (O(n2)) 排序各类简单排序:直接插入...

湖南小影
2017/05/18
0
0
算法系列【希尔排序】篇

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: 关于时间复杂度: 1. 平方阶 (O(n2)) 排序各类简单排序:直接插入...

湖南小影
2017/05/18
0
0

没有更多内容

加载失败,请刷新页面

加载更多

用 C 语言编写 Windows 服务程序的五个步骤(转)

摘要   Windows 服务被设计用于需要在后台运行的应用程序以及实现没有用户交互的任务。为了学习这种控制台应用程序的基础知识,C(不是C++)是最佳选择。本文将建立并 实现一个简单的服务程...

_编程菜鸟_
14分钟前
0
0
Linux各目录及每个目录的详细介绍

目录 /bin 存放二进制可执行文件(ls,cat,mkdir等),常用命令一般都在这里。 /etc 存放系统管理和配置文件 /home 存放所有用户文件的根目录,是用户主目录的基点,比如用户user的主目录就是/...

若杰
15分钟前
3
0
vue组件系列5、日期选择

插件部分源码 <template> <div class="date-picker" @click.stop> <input class="input" v-model="dateValue" v-on:mouseover="openPanel" /> <!-- 动画特效 --> <transi......

轻轻的往前走
16分钟前
0
0
SQL

BEGIN #定义一个变量来保存该记录是否存在 declare num int; #这条sql,就是查询对应的记录有多少条,注意 into num 这两句话,就是把count(*) 查出的值,赋给到num中 select co...

张泽立
17分钟前
1
0
云栖科技评论87期:建立AI规则非常重要 但充分对话更重要

【卷首语】建立AI规则非常重要 但充分对话更重要    2016年,谷歌CEO Sundar Pichai宣布谷歌战略从Mobile First(移动优先)转向AI First(人工智能优先),在此之后,谷歌不仅在AI领域持续投入...

Mr_zebra
18分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部