快速排序(二)

December 9, 2021

在〈快速排序法(一)〉談到,如果不使用新數列來收集小於 S 與大於 S 的數,那麼就得在原數列上處理數的交換(swap)問題,這時軸的選擇、子數列的區段與交換方式等,會影響排序的速度。

解法思路

快速排序法(一)〉是將最左邊元素設為軸,也可以選定中間的元素作為軸,同時由左而右及由右至左分出子數列:

快速排序法(二)

尚未處理的數列會在中間被逐步消化完畢,原本選定的 S 會被分至子數列之中:

快速排序法(二)

接下來對左邊子數列與右邊子數列進行相同動作,直到排序完成。

演算法名書《Introduction to Algorithms》以最右邊(或最左邊)的數為軸,將數列分為小於 s、大於 s 與未處理的部份:

快速排序法(二)

在排序的過程中,i 與 j 會不斷地往右進行比較與交換,最後數列會變為以下狀態:

快速排序法(二)

然後將 s 置於中間,接下來以相同步驟對左右數列進行排序:

快速排序法(二)

一個實際例子的演算如下所示:

快速排序法(二)

程式實作:數列中間為軸

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 
#define MAX 10 
#define SWAP(x,y) {int t; t = x; x = y; y = t;} 

void quickSort(int[], int, int); 

int main(void) { 
    srand(time(NULL)); 
    
    int number[MAX] = {0};    

    printf("排序前:"); 
    int i;  
    for(i = 0; i < MAX; i++) { 
        number[i] = rand() % 100; 
        printf("%d ", number[i]); 
    } 

    quickSort(number, 0, MAX-1); 

    printf("\n排序後:"); 
    for(i = 0; i < MAX; i++) 
        printf("%d ", number[i]); 
    
    printf("\n"); 

    return 0; 
} 

void quickSort(int number[], int left, int right) { 
    if(left < right) { 
        int s = number[(left+right)/2]; 
        int i = left - 1; 
        int j = right + 1; 

        while(1) { 
            while(number[++i] < s) ;  // 向右找 
            while(number[--j] > s) ;  // 向左找 
            if(i >= j) 
                break; 
            SWAP(number[i], number[j]); 
        } 

        quickSort(number, left, i-1);   // 對左邊進行遞迴 
        quickSort(number, j+1, right);  // 對右邊進行遞迴 
    } 
} 
public class Sort {
    public static void quick(int[] number) {
        sort(number, 0, number.length-1);
    }
    
    private static void sort(int[] number, int left, int right) {
        if(left < right) { 
            int s = number[(left+right)/2]; 
            int i = left - 1; 
            int j = right + 1; 

            while(true) { 
                // 向右找
                while(number[++i] < s) ;
                // 向左找
                while(number[--j] > s) ; 
                if(i >= j) 
                    break; 
                swap(number, i, j); 
            } 

            sort(number, left, i-1);   // 對左邊進行遞迴 
            sort(number, j+1, right);  // 對右邊進行遞迴 
        }
    }
    
    private static void swap(int[] number, int i, int j) {
        int t = number[i]; 
        number[i] = number[j]; 
        number[j] = t;
    }
}
def sort(number):
    realsort(number, 0, len(number) - 1)

def realsort(number, left, right):
    if left < right:
        s = number[(left + right) // 2]
        i = left - 1
        j = right + 1
        while True:
            while True:
                i += 1
                if number[i] >= s:
                    break
            while True:
                j -= 1
                if number[j] <= s:
                    break
            if i >= j:
                break
            number[i], number[j] = number[j], number[i]
        realsort(number, left, i - 1)
        realsort(number, j + 1, right)
object Sort {
    def quick(number: Array[Int]) {
        sort(number, 0, number.length - 1)
    }
    
    private def sort(number: Array[Int], left: Int, right: Int) {
        if(left < right) {
            val s = number((left + right) / 2)
            var i = left - 1
            var j = right + 1
            do {
                do i += 1 while(number(i) < s)
                do j -= 1 while(number(j) > s)
            } while(if(i >= j) false else {swap(number, i, j); true})
            sort(number, left, i - 1)
            sort(number, j + 1, right)
        }
    }
    
    private def swap(number: Array[Int], i: Int, j: Int) {
        val t = number(i)
        number(i) = number(j)
        number(j) = t
    }
}
def sort(number)
    realsort(number, 0, number.length - 1)
end

def realsort(number, left, right)
    if left < right
        s = number[(left + right) / 2]
        i = left - 1
        j = right + 1
        while true
            while true
                i += 1
                if number[i] >= s
                    break
                end
            end
            while true
                j -= 1
                if number[j] <= s
                    break
                end
            end
            if i >= j
                break
            end
            number[i], number[j] = number[j], number[i]
        end
        realsort(number, left, j - 1)
        realsort(number, j + 1, right)
    end
end

程式實作:數列右邊為軸

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 
#define MAX 10 
#define SWAP(x,y) {int t; t = x; x = y; y = t;} 

int partition(int[], int, int); 
void quickSort(int[], int, int); 

int main(void) { 
    srand(time(NULL)); 
    
    int number[MAX] = {0}; 

    printf("排序前:"); 
    int i;
    for(i = 0; i < MAX; i++) { 
        number[i] = rand() % 100; 
        printf("%d ", number[i]); 
    } 

    quickSort(number, 0, MAX-1); 

    printf("\n排序後:"); 
    for(i = 0; i < MAX; i++) 
        printf("%d ", number[i]); 
    
    printf("\n"); 

    return 0; 
} 

int partition(int number[], int left, int right) { 
    int i = left - 1; 
    int j;
    for(j = left; j < right; j++) { 
        if(number[j] <= number[right]) { 
            i++; 
            SWAP(number[i], number[j]); 
        } 
    } 

    SWAP(number[i+1], number[right]); 
    return i+1; 
} 

void quickSort(int number[], int left, int right) { 
    if(left < right) { 
        int q = partition(number, left, right); 
        quickSort(number, left, q-1); 
        quickSort(number, q+1, right); 
    } 
} 
public class Sort {
    public static void quick(int[] number) {
        sort(number, 0, number.length-1);
    }
    
    private static void sort(int[] number, int left, int right) {
        if(left < right) { 
            int q = partition(number, left, right); 
            sort(number, left, q-1); 
            sort(number, q+1, right); 
        } 

    }

    private static int partition(int number[], int left, int right) {  
        int i = left - 1; 
        for(int j = left; j < right; j++) { 
            if(number[j] <= number[right]) { 
                i++; 
                swap(number, i, j); 
            } 
        } 
        swap(number, i+1, right); 
        return i+1; 
    } 

    private static void swap(int[] number, int i, int j) {
        int t = number[i]; 
        number[i] = number[j]; 
        number[j] = t;
    }
}
def sort(lst):
    if len(lst) <= 1:
        return lst
    pivot = lst.pop(0)
    before = [i for i in lst if i < pivot]
    after = [i for i in lst if i >= pivot]
    return sort(before) + [pivot] + sort(after)
object Sort {
    def quick(list: List[Int]): List[Int] = {
       list match {
           case Nil => Nil     
           case x::xs =>        
           val (before,after) = xs partition (_ < x)
           quick(before) ++ (x :: quick(after))
       }
    }
}
class Array
    def comprehend(&block)
        return self if block.nil?
        self.collect(&block).compact
    end
end

def quick(lst)
    case
    when lst.length <= 1
        lst
    when pivot = lst.shift
        before = lst.comprehend { |i| i if i < pivot}
        after = lst.comprehend { |i| i if i >= pivot}
        quick(before) + [pivot] + quick(after)
    end
end