实验1 快速排序

1. 问题描述

实现对数组的普通快速排序与随机快速排序。

2. 实验要求

• 实现上述两个算法。
• 统计算法的运行时间。
• 分析性能差异，作出总结。

3. 算法原理

快速排序使用了分治思想，主要分为下面三个分治过程：

分解：数组A[p…r]被划分为两个子数组A[p…q-1]和A[q+1…r]，使得A[p…q-1]中的 每一个元素都小于等于A[q]，而A[q]也小于等于A[q+1…r]中的每一个元素。

解决：通过递归调用快速排序，对子数组A[p…q-1]和A[q+1…r]进行排序。

合并：因为子数组都是原址排序的，所以不需要合并操作：数组A[p…r]已经有序。

快速排序的最坏情况基于每次划分对主元的选择。基本的快速排序选取第一个元素 作为主元。这样在数组已经有序的情况下，每次划分将得到最坏的结果。 一种比较常见的优化方法是随机化快速排序：

即随机选取一个元素作为主元。在算法实现过程的开始，先要将A[r]与从A[p…r]中 随机选取的一个元素交换。因主元元素是随机选取的，所以对输入数组的划分是比 较均衡的。这种情况下虽然最坏情况仍然是 O( n^2)， 但最坏情况不再依赖于输入 数据，而是由于随机函数取值不佳。实际上，随机化快速排序得到理论最坏情况的 可能性仅为1/(2^n)。 所以随机化快速排序可以对于绝大多数输入数据达到 O(nlogn)的期望时间复杂度。

算法性能测试

为了保证算法的正确性，在每次排序后进行正确性检查:

         public static void  accuracy( int [] array ) {
         	for (int i = 1; i < array.length ; i++ ) {
			  assert(array[i - 1] < array[i]);
			}
		}

先测试算法对相对无序数据的性能，采用随机数产生乱序数组

		int[] array = new int[2500];
		Random rd = new Random();
		for (int i = 0; i < array.length; i++) {
			 array[i] = rd.nextInt(20000);
		}

测试结果如下：