資料結構之排序算法——快速排序

文章目錄

• 1. Quick sort (v1)
• • 1.1 C++實作
  • 1.2 Python實作
• 2. Quick sort (v2)
• • 2.1 C++實作
  • 2.2 Python實作
• 3. Quick sort (v3)
• • 3.1 C++實作
  • 3.2 Python實作

1. Quick sort (v1)

單路快速排序

1.1 C++實作

// 對arr[l...r]部分進行partition操作
// 傳回p, 使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p]
template <typename T>
int _partition(T arr[], int l, int r){
    // 随機在arr[l...r]的範圍中, 選擇一個數值作為标定點pivot
    // 如果固定選取标定點（例如選取最左邊的點），對于一個近乎有序的數組性能不佳
    swap( arr[l] , arr[rand()%(r-l+1)+l] );
    T v = arr[l];
    int j = l;
    for( int i = l + 1 ; i <= r ; i ++ )
        if( arr[i] < v ){
            j ++;
            swap( arr[j] , arr[i] );
        }
    swap( arr[l] , arr[j]);
    return j;
}

// 對arr[l...r]部分進行快速排序
template <typename T>
void _quickSort(T arr[], int l, int r){
    if( l >= r )
        return;
    // 這裡可以使用插入排序進行優化，替換上面兩行
    // if( r - l <= 15 ){
    //    insertionSort(arr,l,r);
    //    return;
    int p = _partition(arr, l, r);
    _quickSort(arr, l, p-1 );
    _quickSort(arr, p+1, r);
}

template <typename T>
void quickSort(T arr[], int n){
    srand(time(NULL));
    _quickSort(arr, 0, n-1);
}
           

1.2 Python實作

import random
def __partition(arr, l, r):
	ran = random.randint(l, r)
	arr[l], arr[ran] = arr[ran], arr[l]
	v = arr[l]
	j = l
	for i in range(l+1, r+1):
		if arr[i] < v:
			j += 1
			arr[j], arr[i] = arr[i], arr[j]
	arr[l], arr[j] = arr[j], arr[l]
	return j

def __quick_sort(arr, l, r):
	if l >= r:
		return
	p = __partition(arr, l, r)
	__quick_sort(arr, l, p-1)
	__quick_sort(arr, p+1, r)


def quick_sort_v1(arr):
	n = len(arr)
	__quick_sort(arr, 0, n-1)
           

2. Quick sort (v2)

雙路快速排序

2.1 C++實作

// 雙路快速排序的partition
// 傳回p, 使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p]
template <typename T>
int _partition2Ways(T arr[], int l, int r){
    // 随機在arr[l...r]的範圍中, 選擇一個數值作為标定點pivot
    swap( arr[l] , arr[rand()%(r-l+1)+l] );
    T v = arr[l];
    // arr[l+1...i) <= v; arr(j...r] >= v
    int i = l+1, j = r;
    while( true ){
        // 注意這裡的邊界, arr[i] < v, 不能是arr[i] <= v
        while( i <= r && arr[i] < v )
            i ++;
        // 注意這裡的邊界, arr[j] > v, 不能是arr[j] >= v
        while( j >= l+1 && arr[j] > v )
            j --;
        if( i > j )
            break;
        swap( arr[i] , arr[j] );
        i ++;
        j --;
    }
    swap( arr[l] , arr[j]);
    return j;
}

// 對arr[l...r]部分進行快速排序
template <typename T>
void _quickSort2Ways(T arr[], int l, int r){
    if( l >= r )
        return;
    // 這裡可以使用插入排序進行優化，替換上面兩行
    // if( r - l <= 15 ){
    //    insertionSort(arr,l,r);
    //    return;
    // 調用雙路快速排序的partition
    int p = _partition2Ways(arr, l, r);
    _quickSort2Ways(arr, l, p-1 );
    _quickSort2Ways(arr, p+1, r);
}

template <typename T>
void quickSort2Ways(T arr[], int n){
    srand(time(NULL));
    _quickSort2Ways(arr, 0, n-1);
}
           

2.2 Python實作

import random
def __partition(arr, l, r):
	ran = random.randint(l, r)
	arr[l], arr[ran] = arr[ran], arr[l]
	v = arr[l]
	i, j = l+1, r
	while True:
		while i <= r and arr[i] < v:
			i += 1
		while j >= l+1 and arr[j] > v:
			j -=1
		if i > j:
			break
		arr[i], arr[j] = arr[j], arr[i]
		i += 1
		j -= 1
	arr[l], arr[j] = arr[j], arr[l]
	return j


def __quick_sort(arr, l, r):
	if l >= r:
		return
	p = __partition(arr, l, r)
	__quick_sort(arr, l, p-1)
	__quick_sort(arr, p+1, r)


def quick_sort_v2(arr):
	n = len(arr)
	__quick_sort(arr, 0, n-1)
           

3. Quick sort (v3)

三路快速排序

3.1 C++實作

// 遞歸的三路快速排序算法
template <typename T>
void __quickSort3Ways(T arr[], int l, int r){
    if( l >= r )
        return;
    // 這裡可以使用插入排序進行優化，替換上面兩行
    // if( r - l <= 15 ){
    //    insertionSort(arr,l,r);
    //    return;

    // 随機在arr[l...r]的範圍中, 選擇一個數值作為标定點pivot
    swap( arr[l], arr[rand()%(r-l+1)+l ] );
    T v = arr[l];

    int lt = l;     // arr[l+1...lt] < v
    int gt = r + 1; // arr[gt...r] > v
    int i = l+1;    // arr[lt+1...i) == v
    while( i < gt ){
        if( arr[i] < v ){
            swap( arr[i], arr[lt+1]);
            i ++;
            lt ++;
        }
        else if( arr[i] > v ){
            swap( arr[i], arr[gt-1]);
            gt --;
        }
        else{ // arr[i] == v
            i ++;
        }
    }
    swap( arr[l] , arr[lt] );

    __quickSort3Ways(arr, l, lt-1);
    __quickSort3Ways(arr, gt, r);
}

template <typename T>
void quickSort3Ways(T arr[], int n){

    srand(time(NULL));
    __quickSort3Ways( arr, 0, n-1);
}
           

3.2 Python實作

import random
def __quick_sort(arr, l, r):
	if l >= r:
		return
	ran = random.randint(l, r)
	arr[l], arr[ran] = arr[ran], arr[l]
	v = arr[l]
	lt = l
	gt = r + 1
	i = l + 1
	while i < gt:
		if arr[i] < v:
			arr[i], arr[lt+1] =  arr[lt+1], arr[i]
			i += 1
			lt += 1
		elif arr[i] > v:
			arr[i], arr[gt-1] =  arr[gt-1], arr[i]
			gt -= 1
		else:
			i += 1
	arr[l], arr[lt] =  arr[lt], arr[l]
	__quick_sort(arr, l, lt-1)
	__quick_sort(arr, gt, r)


def quick_sort_v3(arr):
	n = len(arr)
	__quick_sort(arr, 0, n-1)