美文网首页
算法课 实验 3

算法课 实验 3

作者: KEEEPer | 来源:发表于2017-10-10 17:48 被阅读8次

    实验报告


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

    相关文章

      网友评论

          本文标题:算法课 实验 3

          本文链接:https://www.haomeiwen.com/subject/pdfbyxtx.html