快速排序法

  • 确定分界点：一般为数组最左边，最右边或者中间的元素
  • 调整范围：左段的所有数应该都小于分界点的数，右段的数应该都大于分界点的数

设置两个指针，一个指向数组最左边，一个指向数组最右边。左指针向右移动，直到遇到不小于分界点的数，进而右指针向左移动，直到遇到不大于分界点的数，然后将左右指针指向的数进行交换。交换后，左指针继续向右移动，循环上面的过程，直到左右两指针相遇，此时左右两段应该已经被分好。

  • 递归处理左右两段
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static void quickSort(int[] arr, int l, int r) {
	//当左指针大于等于右指针时返回
    if (l >= r) return;	
	//设置分界点，左右指针
	int pos = arr[l], i = l - 1, j = r + 1;
	while (i < j) {
        //判断左段
		while (arr[++i] < pos) {}
        //判断右段
        while (arr[--j] > pos) {}
        //交换左右指针对应的值
        while (i < j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
	}
    //递归处理
	quickSort(arr, l, j);
    quickSort(arr, j+1, r);
}

归并排序法

  • 确定分界点：分界点为数组的中间元素，mid = (l + r)/2
  • 递归排序左右两段
  • 归并 —— 合二为一：将两个排好序的数组合并成一个排好序的数组

新建一个等大的数组，原数组的左段和右段逐一对比，哪个更小就放进新数组，直到左段到分界点或右段到数组末尾，此时将剩下的部分全部放进新数组，此时新数组中的元素应该已经排序好了。最后将新数组的数组传给原数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static void mergeSort (int[] arr,int[] arr2, int l, int r) {
    //当左指针大于右指针的时返回
    if (l >= r) return;
    //设置分界点，为数组的中间
    int mid = (l + r) / 2;
    //递归排序左右两段
    mergeSort(arr, arr2, l, mid);
    mergeSort(arr, arr2, mid + 1, r);
    //设置左右指针，新数组的索引
    int i = l, k = 0, j = mid + 1;
    //将两个排好序的数组合并成一个数组
    while (i <= mid && j <= r) {
        if (arr[i] < arr[j]) arr2[k++] = arr[i++];
        else arr2[k++] = arr[j++];
    }
    //当其中一段放置好时，另一段的剩余部分直接全部放进新数组即可
    while (i <= mid) arr2[k++] = arr[i++];
    while (j <= r) arr2[k++] = arr[j++];
    //将排好序的值传给原数组
    for(i = l, k = 0; i <= r; i++, k++) arr[i] = arr2[k];
}