MergeSort归并排序


合并


合并细节


  1. 不断地将当前序列平均分割成2个子序列, 直到不能再分割（序列中只剩 1个元素）。

  2. 不断地将2个子序列合并成一个有序序列,直到最终只剩下1个子序列。

示例代码

  • 编写Sort类
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
package com.lagou;

public abstract class Sort<T extends Comparable<T>> {
    protected T[] array;

    public void sort(T[] array) {
        if (array == null || array.length < 2) {
            return;
        }
        this.array = array;
        sort();

        printInfo();
    }

    protected abstract void sort();

    /*
     * 返回值等于0，代表 array[i1] == array[i2]
     * 返回值小于0，代表 array[i1] < array[i2]
     * 返回值大于0，代表 array[i1] > array[i2]
     */
    protected int cmp(int i1, int i2) {
        return array[i1].compareTo(array[i2]);
    }

    protected int cmp(T v1, T v2) {
        return v1.compareTo(v2);
    }

    protected void swap(int i1, int i2) {
        T tmp = array[i1];
        array[i1] = array[i2];
        array[i2] = tmp;
    }

    public void printInfo() {
        System.out.println("==================");
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + "_");
        }
        System.out.println();
        System.out.println("================");
    }
}
  • 编写MergeSort类
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
package com.lagou;

import java.util.Arrays;

public class MergeSort<T extends Comparable<T>> extends Sort<T> {
	private T[] leftArray;

	@Override
	protected void sort() {
		leftArray = (T[]) new Comparable[array.length >> 1]; //除2操作
		sort(0, array.length);
	}

	// T(n) = T(n/2) + T(n/2) + O(n)

	/**
	 * 对 [begin, end) 范围的数据进行归并排序
	 */
	private void sort(int begin, int end) {
		if (end - begin < 2) {
			return;
		}

		int mid = (begin + end) >> 1;
		sort(begin, mid);
		sort(mid, end);
		merge(begin, mid, end);
	}

	/**
	 * 将 [begin, mid) 和 [mid, end) 范围的序列合并成一个有序序列
	 */
	private void merge(int begin, int mid, int end) {
		int li = 0, le = mid - begin;
		int ri = mid, re = end;
		int ai = begin;

		// 备份左边数组
		for (int i = li; i < le; i++) {
			leftArray[i] = array[begin + i];
		}

		// 如果左边还没有结束
		while (li < le) {
			if (ri < re && cmp(array[ri], leftArray[li]) < 0) {
				array[ai++] = array[ri++];
			} else {
				array[ai++] = leftArray[li++];
			}
		}

		System.out.println(Arrays.toString(array));
	}
}
  • 编写SortTest类
1
2
3
4
5
6
7
8
9
10
11
12
package com.lagou;

import org.junit.Test;

public class SortTest {
    @Test
    public void MergeSortTest(){
        Integer[] abcd = new Integer[]{1,14,7,2};
        MergeSort mergeSort = new MergeSort();
        mergeSort.sort(abcd);
    }
}

  • 编译结果

  • 结果分析

1
2
3
4
5
6
7
8
9
sort(0, 2);    	merge(0, 1, 2);     1 14 7 2
sort(2, 4);     merge(2, 3, 4);		1 14 2 7
merge(0, 2, 4);
re=4	le=2
ai=0	ri=2 	li=0	1 14 2 7	  1 14
ai=1	ri=2 	li=1	1 2  2 7	  1 14
ai=2	ri=3 	li=1	1 2  7 7	  1 14
ai=3	ri=4 	li=1	1 2  7 14     1 14
ai=4	ri=4 	li=2

QuickSort快速排序


  1. 从数组中选择一个轴点元素（Pivot element），一般选择0位置元素为轴点元素。

  2. 利用Pivot将数组分割成2个子序列，将小于Pivot的元素放在Pivot前面（左侧），将大于 Pivot的元素放在Pivot后面（右侧），等于Pivot的元素放哪边都可以(暂定放在左边)

  3. 对子数组进行第一步，第二步操作，直到不能再分割(子数组中只有一个元素)。


示例代码

  • 编写QuickSort类
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
package com.lagou;

import java.util.Arrays;

public class QuickSort<T extends Comparable<T>> extends Sort<T> {

    @Override
    public void sort() {

        sort(0,array.length);
    }

    /**
     * 对 [begin, end) 范围的元素进行快速排序
     * @param begin
     * @param end
     */
    public void sort(int begin, int end) {
        if (end - begin < 2) {
            return;
        }

        // 确定轴点位置 O(n)
        int mid = pivotIndex(begin, end);
        // 对子序列进行快速排序
        sort(begin, mid);
        sort(mid + 1, end);
    }

    /**
     * 构造出 [begin, end) 范围的轴点元素
     * @return 轴点元素的最终位置
     */
    public int pivotIndex(int begin, int end) {

        // 备份begin位置的元素
        T pivot = array[begin];
        // end指向最后一个元素
        end--;
        while (begin < end) {
            while (begin < end) {
                if (cmp(pivot, array[end]) < 0) { // 右边元素 > 轴点元素
                    end--;
                } else { // 右边元素 <= 轴点元素
                    array[begin++] = array[end];
                    break;
                }
            }
            while (begin < end) {
                if (cmp(pivot, array[begin]) > 0) { // 左边元素 < 轴点元素
                    begin++;
                } else { // 左边元素 >= 轴点元素
                    array[end--] = array[begin];
                    break;
                }
            }
        }
        // 将轴点元素放入最终的位置
        array[begin] = pivot;

        System.out.println(Arrays.toString(array));
        // 返回轴点元素的位置
        return begin;
    }
}
  • 编写SortTest类,添加以下Test方法
1
2
3
4
5
6
@Test
public void QuickSortTest(){
    Integer[] abcd = new Integer[]{1,14,7,2};
    QuickSort mergeSort = new QuickSort();
    mergeSort.sort(abcd);
}

  • 编译结果

  • 结果分析

1
2
3
4
5
6
7
pivotIndex(0, 4)=0    1   1 14 7 2
sort(0, 0);
sort(1, 4);   pivotIndex(1, 4)=3  14  1 2 7 2  	1 2 7 14		
              sort(1, 3);	    pivotIndex(1, 3)=1   2  1 2 7 14
                                sort(1, 1);
                                sort(2, 3);
              sort(4, 4);