mysql快速排序怎么实现的_排序篇 - 快速排序的实现

亦凉 2022-11-05 03:22 127阅读 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

\#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;

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 ) \{

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.

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.

\* @param arr an array of Objects.

\* @param idx1 the index of the first element.

\* @param idx2 the index of the second element.

\*/

public static 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.

\* @param arr an array of Comparable items.

\*/

public static > void quicksort( T\[\] arr ) \{

quicksort( arr, 0, arr.length - 1 );

/\*\*

\* get the median of the left, center and right.

\* order these and hide the pivot by put it the end of

\* of the array.

\* @param arr an array of Comparable.

\* @param left the most-left index of the subarray.

\* @param right the most-right index of the subarray.

\* @return T

\*/

public static >

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.

\* @param arr an array of Comparable items.

\* @param start the begining position.

\* @param end the end position.

\*/

public static >

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.

\* @param arr an array of Comparable Items.

\* @param left the left-most index of the subarray.

\* @param right the right-most index of the subarray.

\*/

private static >

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 );

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

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

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

有问题我们一起讨论。

![13.gif][]

[13.gif]: /images/20221023/69957128a68e4e239ebbf7ed8fb60b32.png

mysql快速排序怎么实现的_排序篇 - 快速排序的实现

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关 php实现快速排序原地排序

相关 mysql快速排序怎么实现的_排序篇 - 快速排序的实现

相关快速排序的java_快速排序的Java实现

相关快速排序实现

相关快速排序、归并排序、堆排序的实现

相关 [排序算法]--快速排序的Java实现

相关快速排序的简单实现

相关快速排序之一路快速排序（Java实现）

相关快速排序的js实现

相关快速排序实现