基本思想:采用分治的思想,对数组进行排序,每次排序都使得操作的数组部分分成以某个元素为分界值的两部分,一部分小于分界值,另一部分大于分界值。分界值一般称为“轴”。一般是以第一个元素为轴,将数组分成左右两部分,然后对左右两部分递归操作,直至完成排序。

C#算法实现:

    public void quickSort(int[] arr, int left, int right){
        if(left < right){
            int pos = partition(arr, left, right);
            quickSort(arr, left, pos - 1);
            quickSort(arr, pos + 1, right);
        }
    }
    public int partition(int[] arr, int left, int right){
        int base = arr[left];
        while(left < right){
            while(left < right && arr[right] >= base){
                right--;
            }
            arr[left] = arr[right];
            while(left < right && arr[left] <= base){
                left++;
            }
            arr[right] = arr[left];       
        }
        arr[left] = base;
    return left;
    }
}