快速排序法（二）

說明

在快速排序法（一）中，每次將最左邊元素設為軸，而之前快速排序法的速度在於軸的選擇，在這裡的實作中，是選定中間的元素值作比較與分割，這可以增加快速排序法效率。

解法

在這邊的實例作中，取中間元素S的值作比較，並同時由左而右及由右至左分出子數列：

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

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

實作：C Java Python Scala Ruby

#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);  // 對右邊進行遞迴 
    } 
}

Java

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

Python

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)

Scala

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
    }
}

Ruby

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