排序算法-递归排序

2018-03-21

一、分而治之思想

1.具体思想

分解步骤：将问题划分为一些子问题，子问题的形式与原问题一样，只是规模更小
解决步骤：递归地求解出子问题。如果子问题的规模足够小，则停止递归，直接求解
合并步骤：将子问题的解组合成原问题的解。

2.递归排序

递归排序其实就是分而治之思想的一种表现

分解：分解待排序的n个元素的序列成各具n/2个元素的两个子序列
解决：使用归并排序递归地排序两个子序列
合并：合并两个以排序的子序列以产生以排序的答案
当待排序的序列长度为1时，递归“开始回升”，在这种情况下不要做任何工作，因为长度为1的每个序列都已排好序

二、java实现

1、代码实现

package com.wangqd.sort;

public class RecursionSortTest {

    public static void main(String[] args) {
        int[] arr = {2,3,6,3,4,7,1,8,2,5};

        mergeSort(arr,0,arr.length-1);

        for (int i : arr) {
            System.out.println(arr[i]);
        }
    }

    public static void mergeSort(int[] arr, int low, int high) {
        //使用递归的方式进行归并排序，所需要的空间复杂度是O（N+logN）
        int mid = (low + high) / 2;
        if (low < high) {
            //递归地对左右两边进行排序
            mergeSort(arr, low, mid);
            mergeSort(arr, mid + 1, high);
            //合并
            merge(arr, low, mid, high);
        }
    }

    //merge函数实际上是将两个有序数组合并成一个有序数组
    //因为数组有序，合并很简单，只要维护几个指针就可以了
    private static void merge(int[] arr, int low, int mid, int high) {
        //temp数组用于暂存合并的结果
        int[] temp = new int[high - low + 1];
        //左半边的指针
        int i = low;
        //右半边的指针
        int j = mid + 1;
        //合并后数组的指针
        int k = 0;

        //将记录由小到大地放进temp数组
        for (; i <= mid && j <= high; k++) {
            if (arr[i] < arr[j])
                temp[k] = arr[i++];
            else
                temp[k] = arr[j++];
        }

        //接下来两个while循环是为了将剩余的（比另一边多出来的个数）放到temp数组中
        while (i <= mid)
            temp[k++] = arr[i++];

        while (j <= high)
            temp[k++] = arr[j++];

        //将temp数组中的元素写入到待排数组中
        for (int l = 0; l < temp.length; l++)
            arr[low + l] = temp[l];
    }
}

2、时间复杂度

时间复杂度为nlgn