快速排序

• 选择一个元素然后放到合适的位置

public void sort(int[] arr){
    sort(arr,0,arr.length-1);
}

private void sort(int[] arr, int l, int r){
    if(l>=r){
        return;
    }
    int p = partition(arr,l,r);
    sort(arr,l,p-1);
    sort(arr,p+1,r);
}

private int partition(int[] arr,int l,int r){
    int j = l;
    for(int i=l+1;i<=r;i++){
        if(arr[i]<arr[l]){
            j++;
            swap(arr,i,j);
        }
    }
    swap(arr,l,j);
    return j;
}

private void swap(int[] arr,int i,int j){
    int t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
}

• 优化1-添加随机

private void sort(int[] arr, int l, int r,Random rdm){
    if(l>=r){
        return;
    }
    int p = partition(arr,l,r,rdm);
    sort(arr,l,p-1,rdm);
    sort(arr,p+1,rdm);
}

private int partition(int[] arr,int l,int r,Random rdm){
    int p = rdm.nextInt(r-l+1)+l;
    swap(arr,l,p);
    int j = l;
    for(int i=l+1;i<=r;i++){
        if(arr[i]<arr[l]){
            j++;
            swap(arr,i,j);
        }
    }
    swap(arr,l,j);
    return j;
}

• 优化2-双路快排

private int partition(int[] arr,int l,int r,Random rdm){
    int p = rdm.nextInt(r-l+1)+l;
    swap(arr,l,p);
    int i = l+1;
    int j = r;
    while(true){
        while(i<=j&&arr[i]<arr[l]){
            i++;
        }
        while(j>=i&&arr[j]>arr[l]){
            j--;
        }
        if(i>=j){
            break;
        }
        swap(arr,i,j);
        i++;
        j--;
    }
    swap(arr,l,j);
    return j;
}

• 优化3-三路快排

private void sort(int[] arr, int l, int r,Random rdm){
    if(l>=r){
        return;
    }
    int p = l+rdm.nextInt(r-l+1);
    swap(arr,l,p);
    int lt = l;
    int i = l+1;
    int gt = r+1;
    while(i<gt){
        if(arr[i]<arr[l]){
            lt++;
            swap(arr,i,lt);
            i++;
        }else if(arr[i]>arr[l]){
            gt--;
            swap(arr,i,gt);
        }else{
            i++;
        }
    }
    swap(arr,l,lt);
    sort(arr,l,lt-1,rdm);
    sort(arr,gt,r,rdm);
}

应用

• 颜色分类(75)

private void sort(int arr,int l,int r){
    int lt = l-1;
    int i=l;
    int gt = r+1;
    while(i<gt){
        if(arr[i]==0){
            lt++;
            swap(arr,lt,i);
            i++
        }else if(arr[i]==2){
            gt--;
            swap(arr,gt,i);
        }else{
            i++;
        }
    }
}

• 数组中的第K个最大元素(215)

private int sort(int[] arr, int l, int r, Random rdm, int index) {
	if (l >= r) {
		return arr[l];
	}
	int p = l + rdm.nextInt(r - l + 1);
	swap(arr, l, p);
	int lt = l;
	int i = l + 1;
	int gt = r + 1;
	while (i < gt) {
		if (arr[i] > arr[l]) {
			lt++;
			swap(arr, i, lt);
			i++;
		} else if (arr[i] < arr[l]) {
			gt--;
			swap(arr, i, gt);
		} else {
			i++;
		}
	}
	swap(arr, l, lt);
	if (lt <= index && index < i) {
		return arr[index];
	} else if (index < lt) {
		return sort(arr, l, lt - 1, rdm, index);
	} else {
		return sort(arr, gt, r, rdm, index);
	}
}

• 最小的k个数(40)

private int[] sort(int[] arr, int l, int r, Random rdm, int index) {
    if (index == -1) {
        return new int[0];
    }
    if (l >= r) {
        return left(arr, l);
    }
    int p = l + rdm.nextInt(r - l + 1);
    swap(arr, l, p);
    int lt = l;
    int i = l + 1;
    int gt = r + 1;
    while (i < gt) {
        if (arr[i] < arr[l]) {
            lt++;
            swap(arr, i, lt);
            i++;
        } else if (arr[i] > arr[l]) {
            gt--;
            swap(arr, i, gt);
        } else {
            i++;
        }
    }
    swap(arr, l, lt);
    if (lt <= index && index < i) {
        return left(arr, index);
    } else if (index < lt) {
        return sort(arr, l, lt - 1, rdm, index);
    } else {
        return sort(arr, gt, r, rdm, index);
    }
}