算法篇01、排序算法

排序算法应该是最经典的算法问题，种类繁多，本篇我们就整理一下最经典的几类算法；

本篇我们主要分析选择排序、插入排序、归并排序、快速排序四类经典的排序算法，我们默认实现从小到大的排序规则；

1、选择排序

选择排序代码如下所示，选择排序就是一个双重for循环，minIndex是最小元素的索引，外层循环每次都找到剩余元素中最小元素的位置索引，然后将i跟minIndex位置的元素互换位置，继续进行下一次循环；

内层循环是从当前元素往后查找，如果后边有元素的值小于minIndex索引的值，就将minIndex更新为此元素的索引；

因为是一个嵌套的双层for循环，所以时间复杂度为O(n^2)级别的，n表示元素个数；

//选择排序
public static void selectionSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int minIndex = i;
        //从i往后遍历，找到最小值，替换minIndex
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        swap(arr, i, minIndex);
    }
}

//交换数组arr中a和b位置的元素
private static void swap(int[] arr, int a, int b) {
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}
复制代码

2、插入排序

插入排序的代码如下所示，插入排序也是嵌套的双层for循环，因此时间复杂度也是O(n^2)级别的；

内层for循环表示如果当前比较的元素比上一个元素还小，就跟上一个元素交换位置，交换完再循环跟上一个元素比较；

外层for循环表示当前比较的元素，因此是从第二元素开始比较的；

//插入排序
public static void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
    	//从i开始往前比较，如果比前一个元素还小，就跟前一个元素交换位置
        for (int j = i - 1; j >= 0; j--) {
            if (arr[j] > arr[i]) {
                swap(arr, i, j);
                i--;
            }
        }
    }
}
复制代码

3、归并排序

归并排序的代码如下所示，归并排序的思想是每次将数组分为两半，对每一半分别进行归并排序，最后进行一个merge融合过程；因此这种一分为二的归并排序时间复杂度是O(nlogn)级别的；

其实主要的过程就是merge过程，首先新建辅助数组，然后将原数组的值拷贝到辅助数组，因为是对两边进行merge融合，并且两边都是排好序的子数组，所以每次都是取两边第一个元素进行比较，将元素值小的更新到合适位置，然后将索引加一，继续进行下一次比较，如果一边已经到头了，说明另一边剩下的元素可以直接依次放到后边了；

因为每次比较需要比较原数组的值，更新也要在原数组上更新，所以需要一个辅助数组，把原数组的值拷贝到辅助数组，此时就可以在辅助数组上比较，在原数组上更新即可；这是一种空间换时间的思想；

//归并排序
public static void mergeSort(int[] arr) {
    mergeSort(arr, 0, arr.length - 1);
}

//对arr数组[l...r]进行排序，递归函数
private static void mergeSort(int[] arr, int l, int r) {
    if (l >= r) {
        return;
    }

    //求出l、r的中点，并分别对两边进行归并排序；
    int mid = l + (r - l) / 2;
    mergeSort(arr, l, mid);
    mergeSort(arr, mid + 1, r);
    merge(arr, l, mid, r);
}

//merge融合过程，将[l...mid]和[mid+1...r]两部分融合
private static void merge(int[] arr, int l, int mid, int r) {
	//辅助函数
    int[] aux = new int[r - l + 1];
    for (int i = l; i <= r; i++) {
        aux[i - l] = arr[i];
    }
    int i = l;
    int j = mid + 1;
    for (int k = l; k <= r; k++) {
        if (i > mid) {
            arr[k] = aux[j - l];
            j++;
        } else if (j > r) {
            arr[k] = aux[i - l];
            i++;
        } else if (aux[i - l] < aux[j - l]) {
            arr[k] = aux[i - l];
            i++;
        } else {
            arr[k] = aux[j - l];
            j++;
        }
    }
}
复制代码

4、快速排序

快速排序的代码如下所示，快速排序的时间复杂度也是O(nlogn)级别的；

快速排序的思想是这样的，首先将原数组执行partition过程分为两个子数组，然后再对两个子数组执行快速排序，也是一个递归算法；

partition是这样一个过程，首先找到数组头，然后对依次遍历数组头后边的元素，比数组头小的元素放在左边，比数组头大的元素放在右边，遍历完之后将数组头与中间的分界点交换位置，即可分成两个子数组；递归函数会再对子数组重复执行上述过程；

//快速排序
public static void quickSort(int[] arr) {
    quickSort(arr, 0, arr.length - 1);
}

//对arr[l...r]部分进行快速排序
private static void quickSort(int[] arr, int l, int r) {
    if (l >= r) {
        return;
    }

    int p = partition(arr, l, r);
    quickSort(arr, l, p - 1);
    quickSort(arr, p + 1, r);
}

//对arr[l...r]进行partition过程
//返回的p满足arr[l...p-1] < arr[p], arr[p+1...r] > arr[p]
private static int partition(int[] arr, int l, int r) {
    int aux = arr[l];
    //arr[l+1...j]<aux arr[j+1...i-1]>aux
    int j = l;
    for (int i = l + 1; i <= r; i++) {
        if (arr[i] < aux) {
            swap(arr, j + 1, i);
            j++;
        }
    }
    swap(arr, l, j);
    return j;
}
复制代码