归并排序

发表于 | 更新于 | 分类于 | 阅读次数： | 阅读次数：
本文字数： 2.1k | 阅读时长 ≈ 3 分钟

即 两路合并排序 T=O(nlogn)


　　

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class MergeSortTest {

    /**
     * Merge合并操作，将两个有序序列合并成一个有序序列：
     *         比较两个序列中的最小值，输出其中较小者，然后重复此过程，
     *         直到其中一个序列为空时，如果另一个还有元素未输出，则将剩余元素依次输出即可。
     * 
     * @param l
     * @param left 有序序列1：l[left],...,l[mid]
     * @param mid
     * @param right 有序序列2：l[mid+1],...,l[right]
     */
    public static void Merge(int[] l, int left, int mid, int right){
        int[] temp = new int[right-left+1]; //定义缓存数组
        int i=left, j=mid+1, k=0; //定义3个指针

        while((i<=mid)&&(j<=right))
            if(l[i]<=l[j])    temp[k++] = l[i++];
            else    temp[k++] = l[j++];

        while(i<=mid) temp[k++] = l[i++]; //若前组有剩余
        while(j<=right)    temp[k++] = l[j++]; //若后组有剩余

        for(i=left,k=0; i<=right; i++,k++)
            l[i] = temp[k]; //将合并后的新序列赋给原数组
    }

// 归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//缺省参数：则默认排序所有元素
public static void MergeSort(int[] l){ 
    MergeSort(l, 0, l.length-1);
}
//重载：排序部分范围内的元素
public static void MergeSort(int[] l, int left, int right){ 
    if(left<right){ //若序列长度超过1，则将其分割成两个子序列
        int mid = (left+right)/2; //将待排序的序列一分为二
        MergeSort(l, left, mid); //对左子序列排序
        MergeSort(l, mid+1, right); //对右子序列排序

        //将两个有序子序列合并成一个有序序列
        Merge(l, left, mid, right); 
        /*
         * 其实，只有最后当left==right，即一直向下递归分割，直到子序列长度为1时，
         * 才会开始向上递归返回，执行该代码行，调用Merge合并函数。
         */
    }
}

// 测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 public static void main(String[] args) {
        int[] l = new int[20];
        //循环添加100内的随机数字到集合中
        for(int i=0; i<20; i++){
            Random random = new Random();
            int value = random.nextInt(100);
            l[i] = value;
        }
        System.out.println("排序前：");
        for(int i=0; i<20; i++)
            System.out.print(l[i]+"\0");
        //归并排序
        MergeSort(l);
        System.out.println("\n排序后：");
        for(int i=0; i<20; i++)
            System.out.print(l[i]+"\0");
    }
}

---------------- The End ----------------
0%