实验报告
1. 归并排序的(非递归)实现
实验讨论以及实验代码
（1）将两个相邻的有序序列归并成一个有序序列，称为“一次归并”。
（2）“一趟归并”，是多次执行“一次归并”的结果。在“一趟归并”中，除最后一个有序序列外，其他有序序列中记录的个数（称为序列长度）相同，用h表示。现在的任务是把若干个相邻的长度为h的有序序列和最后一个长度有可能小于h的有序序列进行两两归并，把结果存放到 temp[1]～ temp[n]中（注意：我们是从下标1开始存放排序序列的）。为此，设参数 i，指向待归并序列的第一个记录，初始时，i = 1，显然归并的步长应是 2h。在归并过程中，有以下三种情况：
<1> 若 i < n - 2h + 1，则表示待归并的两个相邻有序序列的长度均为h，执行“一次归并”，完成后i加2h，准备进行下一次“一次归并”。
<2> 若 i < n - h + 1，则表示仍有两个相邻有序序列，一个长度为h，另一个长度小于h，则执行这两个有序序列的归并，完成后退出“一趟归并‘。
<3> 若 i >= n - h + 1，则表明只剩下一个有序序列，直接将该有序序列送到temp数组的相应位置，完成后退出”一趟排序“。
综上，”一趟归并排序“的算法如下：
void mergePass(int arr[], int n, int h, int temp[]) // 从下标1开始存放待排序序列
{
int i = 1;
while (i < n - 2*h + 1) // 待归并记录至少有两个长度为h的子序列。
{
mergeArray(arr, i, i + h - 1, i + 2*h - 1, temp);
i += 2*h;
}
if (i < n - h + 1) // 此时 n - 2*h + 1 < i < n - h + 1，待归并序列中有一个长度小于h。
mergeArray(arr, i, i + h - 1, n, temp);
else // 此时 i >= n - h + 1，待归并序列中只剩一个子序列。
for (int k = i; k <= n; k++)
temp[k] = arr[k];
}
（3）如何控制“二路归并排序的非递归实现”的结束？开始时，有序序列的长度为1，结束时，有序序列的长度为n，因此，可以用有序序列的长度来控制排序过程的结束。算法如下：
void mergeSort2(int arr[], int n, int temp[]) // 从下标1开始存放待排序序列
{
int h = 1; // 初始时子序列长度为1
while (h < n)
{
mergePass(arr, n, h, temp);
h = 2*h;
}
}
2.快速排序的(非递归)实现
实验讨论及实验代码
首先我们得明白递归函数其实是需要在栈中保护现场的，故我们可以构建一个保护状态的栈。在快排中，状态其实就是排序的排序，其原理是通过分割将待排序列划分为一个个小片段，然后逐一排序好，所以需要保护的状态其实就是待排小片段的边界。明白了这个原则，那么实现起来也甚是容易了。
实验代码：
public static void quickSortIterative(int[] nums){
if(nums == null || nums.length < 2) return;
int left = 0;
int right = nums.length - 1;
Stack<Integer> stack = new Stack<Integer>();
stack.push(left);
stack.push(right);
while(!stack.isEmpty()){
int h = stack.pop();
int l = stack.pop();
int p = partition(nums, l, h);
if(p - l > 1){
stack.push(l);
stack.push(p-1);
}
if(h - p > 1){
stack.push(p+1);
stack.push(h);
}
}
}
