排序算法第五篇——快速排序

算法描述：

快速排序（Quicksort）是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分（本例中由partition函数实现），其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

Java源代码：

<span style="font-size: 18px;">package ljp.sort.quick;

public class QuickSortDemo01 {
	private int[] list;

	// 构造函数，初始化数组
	public QuickSortDemo01() {
		list = new int[10];
		for (int i = 0; i < list.length; i++) {
			list[i] = (int) (Math.random() * 1000);
		}
	}

	// 排序函数
	public void sort(int begin, int end) {
		if (begin < end) {
			int p = partition(begin, end);
			sort(begin, p - 1);
			sort(p + 1, end);
		}
	}

	// 分解函数
	public int partition(int m, int n) {
		int temp = list[m];
		int i = m;
		for (int j = m + 1; j <= n; j++) {
			if (list[j] <= temp) {
				i++;
				int t_change = list[i];
				list[i] = list[j];
				list[j] = t_change;
				System.out.println("第" + (i + 1) + "个元素 和 第" + (j + 1)
						+ "个元素 交换");
				display();
			}
		}
		int t_change = list[i];
		list[i] = list[m];
		list[m] = t_change;
		System.out.println("第" + (i + 1) + "个元素 和 第" + (m + 1)
				+ "个元素 交换");
		display();
		return i;
	}

	public void display() {
		for (int i : list) {
			System.out.print(i + " ");
		}
		System.out.println();
	}

	public int getLength() {
		return this.list.length;
	}

	public static void main(String[] args) {
		QuickSortDemo01 quickSortDemo01 = new QuickSortDemo01();
		System.out.println("排序前:");
		quickSortDemo01.display();
		quickSortDemo01.sort(0, quickSortDemo01.getLength() - 1);
	}

}</span>

运行结果：

排序前:
808 914 224 698 308 931 108 697 967 855
第2个元素 和 第3个元素 交换
808 224 914 698 308 931 108 697 967 855
第3个元素 和 第4个元素 交换
808 224 698 914 308 931 108 697 967 855
第4个元素 和 第5个元素 交换
808 224 698 308 914 931 108 697 967 855
第5个元素 和 第7个元素 交换
808 224 698 308 108 931 914 697 967 855
第6个元素 和 第8个元素 交换
808 224 698 308 108 697 914 931 967 855
第6个元素 和 第1个元素 交换
697 224 698 308 108 808 914 931 967 855
第2个元素 和 第2个元素 交换
697 224 698 308 108 808 914 931 967 855
第3个元素 和 第4个元素 交换
697 224 308 698 108 808 914 931 967 855
第4个元素 和 第5个元素 交换
697 224 308 108 698 808 914 931 967 855
第4个元素 和 第1个元素 交换
108 224 308 697 698 808 914 931 967 855
第1个元素 和 第1个元素 交换
108 224 308 697 698 808 914 931 967 855
第2个元素 和 第2个元素 交换
108 224 308 697 698 808 914 931 967 855
第8个元素 和 第10个元素 交换
108 224 308 697 698 808 914 855 967 931
第8个元素 和 第7个元素 交换
108 224 308 697 698 808 855 914 967 931
第10个元素 和 第10个元素 交换
108 224 308 697 698 808 855 914 967 931
第10个元素 和 第9个元素 交换
108 224 308 697 698 808 855 914 931 967