交换排序——快速排序

on October 9, 2016 under jekyll

2 minute read

算法描述：

基本思想是：在要排序的数据组中选择一个基准值，每趟冲数据序列的两端开始交替进行，将小于基准值的元素交换至序列前端，将大于基准值的元素交换到序列后端。序列被基准值划分为两个序列后，再用相同的方式进行递归调用，知道子序列的长度为1，则完成排序。

稳定性：不稳定。

时间复杂度：

最好情况：每趟排序将序列分为长度相近的两个子序列，比较次数为O（n*log2 n），时间复杂度为O（n*log2 n)。

最坏情况（已排序）：每趟将序列分成长度差异很大的两个子序列，时间复杂度为O（n^2)。

当n较大且数据序列随机排列时，快速排序的效率较高；但是当n很小或基准值选取不合适时，快速排序则很慢。

空间复杂度：快速排序在递归调用过程中，需要使用栈保存参数，栈所占用的空间与递归调用的次数有关，最好的情况下空间复杂度为O（log2 n），最坏情况下O（n）。平均空间复杂度为O（log2 n）。

Java实现：

//交换排序：快速排序
public class M004 {
	public static void main(String[] args) {
		int[] number = { 21, 32, 2, 4, 2, 65, 90, 54 };
		int[] result = quickSort(number, 0, number.length - 1);
		for (int i = 0; i < result.length; i++) {
			System.out.print(result[i] + " ");
		}
	}

	private static int[] quickSort(int[] number, int begin, int end) {
		if (begin < end) {
			int i = begin, j = end;
			int vot = number[i];
			while (i != j) {
				while (i < j && vot <= number[j]) {
					j--;
				}
				if (i < j) {
					number[i++] = number[j];
				}
				while (i < j && vot >= number[i]) {
					i++;
				}
				if (i < j) {
					number[j--] = number[i];
				}

			}
			number[i] = vot;
			quickSort(number, begin, j - 1);
			quickSort(number, i + 1, end);

		}
		return number;
	}
}

学习笔记, 数据结构, Java, 排序

I feedback.
Let me know what you think of this article on twitter @Yanlei_Hello or leave a comment below!