实验报告

---

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);
            }
        }
    }