排序算法之---快速排序

只想看优化后快排代码: 点击跳转

先认识荷兰国旗问题:
划分两层: 小于等于区 和 大于区

public static int partition(int[] arr, int L, int R) {
	if(L > R) {
		return -1;
	}
	if(L == R) {
		return L;
	}
	int lessEqual = L - 1;
	int index = L;
	while(index < R) {
		if(arr[index] <= arr[R]) {
			swap(arr, index, ++lessEqual);
		}
		index++;
	}
	swap(arr, ++lessEqual, R);
	return lessEqual;
}

划分三层: 小于区, 等于区 和 大于区

public static int[] netherlandsFlag(int[] arr, int L, int R) {
	if(L > R) {
		return new int[]{-1, -1};
	}
	if(L == R) {
		return new int[] {L, R};
	}
	int less = L - 1;
	int more = R;
	int index = L;
	while(index < more) {
		if(arr[index] == arr[R]) {
			index++;
		}
		else if(arr[index] < arr[R]) {
			swap(arr, index++, ++less);
		} else {
			swap(arr, index, --more);
		}
	}
	swap(arr, more, R);
	return new int[] {less + 1, more};
}

快排1.0版本

public static void quickSort1(int[] arr) {
	if(arr == null || arr.length < 2) {
		return;
	}
	process1(arr, 0, arr.length - 1);
}

public static void process1(int[] arr, int L, int R) {
	if(L >= R) {
		return;
	}
	int M = partition(arr, L, R);
	process1(arr, L, M - 1);
	process1(arr, M + 1, R);
}

	

快排2.0版本:

public static void process2(int[] arr, int L, int R) {
	if(L >= R) {
		return;
	}
	int[] equalArea = netherlandsFlag(arr, L, R);
	process2(arr, L, equalArea[0] - 1);
	process2(arr, equalArea[1] + 1, R);
}

快排3.0版本:

public static void process3(int[] arr, int L, int R) {
	if(L >= R) {
		return;
	}
	swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
	int[] equalArea = netherlandsFlag(arr, L, R);
	process2(arr, L, equalArea[0] - 1);
	process2(arr, equalArea[1] + 1, R);
}

上面快排方法中的partition和netherlandsFlag方法上面都有

快排的额外空间复杂度: logN
快排3.0时间复杂度: n * logN

最终就背这个就行:

public static void quickSort3(int[] arr) {
	if (arr == null || arr.length < 2) {
		return;
	}
	process3(arr, 0, arr.length - 1);
}

public static void process3(int[] arr, int L, int R) {
	if (L >= R) {
		return;
	}
	swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
	int[] equalArea = netherlandsFlag(arr, L, R);
	process3(arr, L, equalArea[0] - 1);
	process3(arr, equalArea[1] + 1, R);
}

public static int[] netherlandsFlag(int[] arr, int L, int R) {
	if (L > R) {
		return new int[] { -1, -1 };
	}
	if (L == R) {
		return new int[] { L, R };
	}
	int less = L - 1;
	int more = R;
	int index = L;
	while (index < more) {
		if (arr[index] == arr[R]) {
			index++;
		} else if (arr[index] < arr[R]) {
			swap(arr, index++, ++less);
		} else { // >
			swap(arr, index, --more);
		}
	}
	swap(arr, more, R);
	return new int[] { less + 1, more };
}