2_6快速排序

C++实现

class QuickSort {
public:
    void swap(int *A, int l, int r)
    {
        int tmp = A[l];
        A[l] = A[r];
        A[r] = tmp;
        return;
    }
    void q_sort(int *A, int left, int right)
    {
        if(right <= left){
            return;
        }else if(left + 1 == right){
            if(A[left] < A[right]){
                return;
            }else{
                swap(A, left, right);
                return;
            }
        }
        int idx = left;
        int idx_right = right;
        int curr = A[left];
        for(int i=left+1; i<=right; i++){
            if(A[idx+1]<curr){
                swap(A, idx, idx+1);
                ++idx;
            }else{
                swap(A, idx_right, idx+1);
                --idx_right;
            }
        }
        A[idx] = curr;
        q_sort(A, left, idx-1);
        q_sort(A, idx+1, right);
        return;
    }
    int* quickSort(int* A, int n) {
        // write code here
        q_sort(A, 0, n-1);
        return A;
    }
};

python 实现

# -*- coding:utf-8 -*-

class QuickSort:
    def quickSort(self, A, n):
        # write code here
        if 1==n:
            return A
        elif 2==n:
            return [min(A), max(A)]

        curr = A[0]
        split_A = [0]*n
        idx_head = 0
        idx_tail = n
        for i in xrange(1,n):
            if curr > A[i]:
                split_A[idx_head] = A[i]
                idx_head += 1
            else:
                split_A[idx_tail-1] = A[i]
                idx_tail -= 1
        split_A[idx_head] = curr
        if split_A[:idx_head]:
            A_left = self.quickSort(split_A[:idx_head], idx_head)
        else: A_left = []
        if split_A[idx_tail:]:
            A_right = self.quickSort(split_A[idx_tail:],len(split_A[idx_tail:]))
        else: A_right = []
        return A_left + [curr] + A_right