快速排序 分区函数

适合我的快排分区函数：

def patition2(arr, l, r):
    pivot = arr[l]
    index = l+1
    for i in range(l+1, r+1):
        if arr[i] < pivot:
            arr[i], arr[index] = arr[index], arr[i]
            index += 1
    arr[l], arr[index-1] = arr[index-1], arr[l]
    return index-1

注意要点：

1、返回index-1，非常关键！！！因为 assert arr[index-1] < pivot and arr[index]>=pivot

2、注意判定条件是 <，当然 <= 也是可以的！！！

3、注意index起始位置是L+1

4、循环的起始位置也是L+1

网上的其他写法：

// C++
void Swap(int &first_number, int &second_number) {
    int temp        = first_number;
    first_number    = second_number;
    second_number   = temp;
}

int Partition(int array[], int start, int end, int pivot_index) {
    int pivot       = array[pivot_index];
    int store_index = start;

    Swap(array[pivot_index], array[end]);
    for (int iLoop = start; iLoop < end; iLoop++) {
        if (array[iLoop] < pivot) {
            Swap(array[iLoop], array[store_index]);
            store_index++;
        }
    }
    Swap(array[store_index], array[end]);

    return store_index;
}

template<class T>
int Partition(T a[], int start, int end, int pivotIndex){
    T pivot = a[pivotIndex];
    Swap(a[pivotIndex], a[end]);
    int storeIndex = start;
    for(int i = start; i < end; ++i) {
        if(a[i] < pivot) {
            Swap(a[i], a[storeIndex]);
            ++storeIndex;
        }
    }
    swap(a[storeIndex], a[end]);
    return storeIndex;
}

分区的思想，还可以用在解决计算中值和选择问题上。

//中值问题
	public static int getMedian(int[] array){
		return getKth(array,array.length/2);
	}
	//选择问题
	public static int getKth(int[] array,int k){
		int low =0,high = array.length -1;
		int s = 0;
		do{
			s = partition(array,low,high);
			if(s>k) high = s-1;
			else low = s+1;
		}while(s != k);
		return array[s];
	}