看板 TL
作者 標題 [筆記]
時間 2013年01月27日 Sun. PM 06:54:31
演算法
───────────────────────────────────────
快速排序採用一種「分而治之、各個擊破」的觀念。
快速排序使用分治法（Divide and conquer）策略來把一個序列（list）分為兩個子序列（sub-lists）。
步驟為：
1.從數列中挑出一個元素，稱為 "基準"（pivot），
2.重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面
（相同的數可以到任一邊）。在這個分割結束之後，該基準就處於數列的中間位置。
這個稱為分割（partition）操作。
3.遞迴地（recursive）把小於基準值元素的子數列和大於基準值元素的子數列排序。
遞迴的最底部情形，是數列的大小是零或一，也就是永遠都已經被排序好了。
雖然一直遞迴下去，但是這個演算法總會結束，因為在每次的迭代（iteration）中，
它至少會把一個元素擺到它最後的位置去。
在簡單的虛擬碼中，此演算法可以被表示為：
function quicksort(q)
var list less, pivotList, greater
if length(q) ≤ 1 {
return q
} else {
select a pivot value pivot from q
for each x in q except the pivot element
if x < pivot then add x to less
if x ≥ pivot then add x to greater
add pivot to pivotList
return concatenate(quicksort(less), pivotList, quicksort(greater))
}
原地(in-place)分割的版本
───────────────────────────────────────
上面簡單版本的缺點是，它需要Ω(n)的額外儲存空間，也就跟歸併排序一樣不好。額外需要的記憶體空間配置，在實際上的實作，也會極度影響速度和快取的效能。有一個比較複雜使用原地（in-place）分割演算法的版本，且在好的基準選擇上，平均可以達到O(log n)空間的使用複雜度。
function partition(a, left, right, pivotIndex)
pivotValue := a[pivotIndex]
swap(a[pivotIndex], a[right]) // 把 pivot 移到結尾
storeIndex := left
for i from left to right-1
if a[i] < pivotValue
swap(a[storeIndex], a[i])
storeIndex := storeIndex + 1
swap(a[right], a[storeIndex]) // 把 pivot 移到它最後的地方
return storeIndex
這是原地分割演算法，它分割了標示為 "左邊（left）" 和 "右邊（right）" 的序列部份，藉由移動小於a[pivotIndex]的所有元素到子序列的開頭，留下所有大於或等於的元素接在他們後面。在這個過程它也為基準元素找尋最後擺放的位置，也就是它回傳的值。它暫時地把基準元素移到子序列的結尾，而不會被前述方式影響到。由於演算法只使用交換，因此最後的數列與原先的數列擁有一樣的元素。要注意的是，一個元素在到達它的最後位置前，可能會被交換很多次。
一旦我們有了這個分割演算法，要寫快速排列本身就很容易：
procedure quicksort(a, left, right)
if right > left
select a pivot value a[pivotIndex]
pivotNewIndex := partition(a, left, right, pivotIndex)
quicksort(a, left, pivotNewIndex-1)
quicksort(a, pivotNewIndex+1, right)
這個版本經常會被使用在命令式語言中，像是C語言。
C
#include<stdio.h>
int a[100];
void prt(int n)
{
int i;
for(i=1;i<=n;i++)
printf("%d ",a[i]);
}
void quicksort(int a[],int l,int h)
{
if (l>=h)return ;
int j ,i,key;
i=l;j=h;key=a[i];
while(i<j)
{
while(i<j&&a[j]>key)j--;
if (i<j) a[i++]=a[j];
while (i<j&&a[i]<key)i++;
if (i<j) a[j--]=a[i];
}
a[i]=key;
if (l<i-1)
quicksort(a,l,i-1);
if (i+1<h)
quicksort(a,i+1,h);
}
int main()
{
int i,n;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
quicksort(a,1,n);
prt(n);
scanf("%d",&a[i]);
return 0;
}
int a[100];
void prt(int n)
{
int i;
for(i=1;i<=n;i++)
printf("%d ",a[i]);
}
void quicksort(int a[],int l,int h)
{
if (l>=h)return ;
int j ,i,key;
i=l;j=h;key=a[i];
while(i<j)
{
while(i<j&&a[j]>key)j--;
if (i<j) a[i++]=a[j];
while (i<j&&a[i]<key)i++;
if (i<j) a[j--]=a[i];
}
a[i]=key;
if (l<i-1)
quicksort(a,l,i-1);
if (i+1<h)
quicksort(a,i+1,h);
}
int main()
{
int i,n;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
quicksort(a,1,n);
prt(n);
scanf("%d",&a[i]);
return 0;
}
Java
import java.util.Comparator;
import java.util.Random;
public class Quicksort {
public static final Random RND = new Random();
private static void swap(Object[] array, int i, int j) {
Object tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
private static <E> int partition(E[] array, int begin, int end, Comparator<? super E> cmp) {
int index = begin + RND.nextInt(end - begin + 1);
E pivot = array[index];
swap(array, index, end);
for (int i = index = begin; i < end; ++ i) {
if (cmp.compare(array[i], pivot) <= 0) {
swap(array, index++, i);
}
}
swap(array, index, end);
return (index);
}
private static <E> void qsort(E[] array, int begin, int end, Comparator<? super E> cmp) {
if (end > begin) {
int index = partition(array, begin, end, cmp);
qsort(array, begin, index - 1, cmp);
qsort(array, index + 1, end, cmp);
}
}
public static <E> void sort(E[] array, Comparator<? super E> cmp) {
qsort(array, 0, array.length - 1, cmp);
}
}
/*
* more efficient implements for quicksort. <br />
* use left, center and right median value (@see #median()) for the pivot, and
* the more efficient inner loop for the core of the algorithm.
*/
class Sort {
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 items. <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 )
swapRef( arr, left, center );
if ( arr[left].compareTo( arr[right] ) > 0 )
swapRef( arr, left, right );
if ( arr[center].compareTo( arr[right] ) > 0 )
swapRef( arr, center, right );
swapRef( arr, center, right - 1 );
return arr[ right - 1 ];
}
/**
* 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 )
swapRef( arr, i, j );
else
break;
}
//swap the pivot reference back to the small collection.
swapRef( 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 (cause it much more efficient).
insertionSort( arr, left, right );
}
}
/**
* method to swap references 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 swapRef( T[] arr, int idx1, int idx2 ) {
T tmp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = tmp;
}
/**
* 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 ];
}
arr[ i ] = tmp;
}
}
}
import java.util.Random;
public class Quicksort {
public static final Random RND = new Random();
private static void swap(Object[] array, int i, int j) {
Object tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
private static <E> int partition(E[] array, int begin, int end, Comparator<? super E> cmp) {
int index = begin + RND.nextInt(end - begin + 1);
E pivot = array[index];
swap(array, index, end);
for (int i = index = begin; i < end; ++ i) {
if (cmp.compare(array[i], pivot) <= 0) {
swap(array, index++, i);
}
}
swap(array, index, end);
return (index);
}
private static <E> void qsort(E[] array, int begin, int end, Comparator<? super E> cmp) {
if (end > begin) {
int index = partition(array, begin, end, cmp);
qsort(array, begin, index - 1, cmp);
qsort(array, index + 1, end, cmp);
}
}
public static <E> void sort(E[] array, Comparator<? super E> cmp) {
qsort(array, 0, array.length - 1, cmp);
}
}
/*
* more efficient implements for quicksort. <br />
* use left, center and right median value (@see #median()) for the pivot, and
* the more efficient inner loop for the core of the algorithm.
*/
class Sort {
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 items. <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 )
swapRef( arr, left, center );
if ( arr[left].compareTo( arr[right] ) > 0 )
swapRef( arr, left, right );
if ( arr[center].compareTo( arr[right] ) > 0 )
swapRef( arr, center, right );
swapRef( arr, center, right - 1 );
return arr[ right - 1 ];
}
/**
* 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 )
swapRef( arr, i, j );
else
break;
}
//swap the pivot reference back to the small collection.
swapRef( 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 (cause it much more efficient).
insertionSort( arr, left, right );
}
}
/**
* method to swap references 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 swapRef( T[] arr, int idx1, int idx2 ) {
T tmp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = tmp;
}
/**
* 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 ];
}
arr[ i ] = tmp;
}
}
}
--
Shaken, Not Stirred.
--
※ 作者: TL 時間: 2013-01-27 18:54:32
※ 編輯: TL 時間: 2013-01-27 18:55:40
※ 看板: TL 文章推薦值: 0 目前人氣: 0 累積人氣: 18
回列表(←)
分享