排序算法

快速排序

步骤

1. 从列表选出一个基准值 pivot
2. 重新排列数组，所有比基准值小的放在基准值左边，所有比基准值大的放在基准值右边。
3. 递归把基准值左右两边的数列排序。

时间复杂度O(nlogn)

最坏的情况：序列已经是升序排序，需要比较n(n-1)/2次，为O(n^2)

最好的情况：每次划分都是正好两半 T(n) <= 2T(n/2)+O(n) —> T(n) = O(nlogn)

空间复杂度O(nlogn)：由于是递归调用，空间复杂度为O(nlogn)

快速排序是不稳定的，时间复杂度O(nlogn)，不稳定发生在中枢元素和a[j]，中枢元素左边的元素可能和右边的元素相等，当中枢元素和其交换时，破坏了稳定性

public static void quickSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int pivot = partition(arr, left, right);
        quickSort(arr, left, pivot - 1);
        quickSort(arr, pivot + 1, right);
    }

    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[low];
        while (low < high) {
            while (low < high && arr[high] >= pivot)
                high--;
            arr[low] = arr[high];
            while (low < high && arr[low] <= pivot)
                low++;
            arr[high] = arr[low];
        }
        arr[low] = pivot;
        return low;
    }

冒泡排序

相邻两个元素进行交换，把大的元素浮到最上面

时间复杂度O(n^2)：最外层for执行n次，内层循环j从0～i-1，i从n-1～1，复杂度为n*(n-1)/2，

空间复杂度O(1)：只需要一个temp位置交换

稳定：比较两个相邻元素并进行交换，如果相等，则不会交换，稳定性没有被破坏。

public void bubbleSort(int[] arr) {
        if(arr == null || arr.length == 0)
            return ;
        for(int i=0;i<arr.length-1;i++) {
            for(int j=0;j<arr.length-i-1;j++) {
                if (arr[j]>arr[j+1]) {
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
}

选择排序

一次排序后把最小的元素放在最前面

时间复杂度O(n^2)：比较次数和初始状态无关，为n(n-1)/2，最好，最坏和平均情况均为O(n2)

空间复杂度O(1)：

不稳定，不稳定发生在最小的元素当前元素交换时，如果当前元素在最小元素前面，并且比和当前元素相等时，交换之后稳定性就被破坏

public static void selectSort(int[] arr) {
        if(arr == null || arr.length == 0)
            return ;
        int minIndex = 0;
        for(int i=0;i<arr.length-1;i++) {//比较n-1次
            minIndex = I;
            for (int j = i+1; j < arr.length; j++) {//从i+1开始比较，minIndex默认为I
                if (arr[j]<arr[minIndex]) {
                    minIndex = j;
                }
            }
            if (minIndex!=i) {
                swap(arr, i, minIndex);//minIndex不为i，说明找到更小的，交换
            }
        }
}

插入排序

在一个已经排好序的序列中，为下一个找到一个合适的插入位置

时间复杂度O(n^2)：外层for共执行arr.length-2次，内层循环最少执行1次，最多执行index次，算法复杂度n*(n-1)/2

空间复杂度O(1)：只需要一个位置key用于交换

稳定：插入排序是在已经有序的小序列中进行插入一个元素，即使遇到相等的元素，也是插入在其后面，稳定性没有被破坏

public static void insertSort(int[] arr) {
        if (arr == null || arr.length == 0)
            return;
        for (int i = 1; i < arr.length; i++) {// 假设第一个位置正确，要往后移，必须假设第一个
            int j = I;
            int target = arr[i];// 待插入
            while (j > 0 && target < arr[j - 1]) {// 往后移
                arr[j] = arr[j - 1];
                j--;
            }
            arr[j] = target;
        }
}

希尔排序

思想：分组插入排序，将整个待排序序列分割成若干个子序列，并分别进行插入排序，然后再缩小增量继续排序，当增量足够小时，再对全体元素进行直接插入排序。

时间复杂度O(nlogn)：

时间复杂度依赖于增量序列

最好的情况：序列是升序序列，需要比较n次，后移赋值操作为0次，O(n)

最坏的情况：序列的降序序列，O(nlogn)

空间复杂度O(1)：只需要一个位置置换

public static void shellSort(int[] arr) {
        int i, j, gap;
        for (gap = arr.length / 2; gap > 0; gap /= 2) {
            for (i = gap; i < arr.length; i++) {
                for (j = i - gap; j >= 0 && arr[j] > arr[j + gap]; j -= gap)
                    swap(arr, j, j + gap);
            }
        }
    }

归并排序

合并两个有序的子数组

思想：递归分治+归并

把待排序列看成两个有序序列，然后合并两个子序列。倒着看，两两合并，四四合并。。。最终形成有序序列。

时间复杂度O(nlogn)：归并排序是一种非“就地”排序，需要和待排序序列一样多的辅助空间，故归并排序的缺点是所需额外空间多，对长度为n的数组，需要进行logn趟二路归并，每趟归并的时间为O(n)，故其时间复杂度无论在最好还是最坏情况下都是O(nlogn)

空间复杂度O(n)：排序时需要和待排序序列一样的空间，空间复杂度为O(n)

稳定：归并排序是把序列递归的分成短序列，递归出口是只有一个元素或者2个元素短有序序列，然后把各个有序序列合并成有序的长序列，不断合并知道原序列全部排好序。在短序列中，即使两个元素相等也不会交换，因此稳定性没有被破坏。

使用场合

public static void mergeArray(int[] arr, int left, int mid, int right) {
        if (arr == null || arr.length == 0)
            return;
        int[] temp = new int[right-left+1];
        int i = left, j = mid + 1;
        int k = 0;
        // 二路归并
        while (i < mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        // 处理子数组中剩余元素
        while (i <= mid) {
            temp[k++] = arr[i++];
        }
        while (j <= right) {
            temp[k++] = arr[j++];
        }
        // 从临时数组中拷贝到目标数组
        for (i = 0; i < temp.length; i++) {
            arr[left + i] = temp[I];
        }
    }

    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            // 归并排序使得左边序列有序
            mergeSort(arr, left, mid);
            // 归并排序使得右边序列有序
            mergeSort(arr, mid + 1, right);
            // 合并两个有序序列
            mergeArray(arr, left, mid, right);
        }
    }

堆排序

时间复杂度O(nlogn)：最好，最坏，平均均为O(nlogn)

空间复杂度O(1)

思想：

堆（二叉堆）：一棵完全二叉树

1. 最大堆调整：将堆末端子节点作调整，使得子节点永远小于父节点
2. 创建最大堆：将堆所有数据重新排序，使其成为最大堆
3. 堆排序：移除位于第一个数据的根节点，并作最大堆调整堆递归运算，将最大的元素从堆中分离

parent(i) = floor((i-1)/2)，i的父节点下标

left(i) = 2i+1，i的左子节点下标

right(i) = 2(i+1)，i的右子节点下标

不稳定：堆和其子节点（堆，左节点，右节点）交换不会破坏稳定性，堆顶元素移除时，父节点和某个元素交换，刚好该元素后面有相同的元素，就会破坏稳定性。

    public static void heapSort(int[] arr) {
        int len = arr.length - 1;
        int beginIndex = (len - 1) / 2;// 第一个非叶子节点
        // 将数组堆化
        for (int i = beginIndex; i >= 0; i--) {
            maxHeapify(arr, i, len);
        }
        // 对堆化数组排序，每次都移出最顶层节点arr[0]，与尾部节点位置调换，同时遍历长度-1，
        // 然后从新调整被换到根节点末尾都元素，使其符合堆堆特性，直至未排序堆堆长度未0
        for (int j = len; j >= 0; j--) {
            swap(arr, 0, j);
            maxHeapify(arr, 0, j - 1);
        }
    }

    private static void maxHeapify(int[] arr, int index, int len) {
        int li = (index * 2) + 1;// 左子节点索引
        int ri = 2 * (index + 1);// 右子节点索引
        int cMax = li;// 子节点值最大索引，默认左子节点
        if (li > len)
            return;// 左子节点索引超出计算范围，直接返回
        if (ri <= len && arr[ri] > arr[li])
            cMax = ri;// 先判断左右子节点哪个大
        if (arr[cMax] > arr[index]) {
            swap(arr, cMax, index);// 如果父节点被子节点调换
            maxHeapify(arr, cMax, len);// 则需要继续判断换下后堆父节点是否符合堆堆性质
        }
    }

算法时空复杂度对比

不稳定排序：选择排序，快速排序，希尔排序，堆排序

稳定排序：冒泡排序，插入排序，归并排序，基数排序