Java 排序

排序

1. 稳定的排序：排序之前和排序之后它们俩的相对顺序没有发生变化
2. 内部排序：在内存上的排序
3. 外部排序：需要借助磁盘等外部空间进行的排序

插入排序

1. 思想：假设这组数据的第一个元素是有序的，从第二个元素和前面的元素进行比较，找到合适的位置进行插入

// 插入排序
    public static void insertSort(int[] array){
        for(int i = 1;i < array.length;i++){
            int j = i - 1;
            int tmp = array[i];
            for(;j >= 0;j--){
                if(array[j] > tmp){
                    array[j+1] = array[j];
                }else{
                    break;
                }
            }

            array[j + 1] = tmp;
        }
    }

分析

1. 时间复杂度：O(N^2)
   最坏情况：O(N^2)
   最好情况：有序的数组，O(N)
   数据越有序，排序越快
   适用于待排序数组基本上趋于有序了，时间复杂度趋于O(N)
2. 空间复杂度：O(1)
3. 稳定性：是一个稳定的排序
   例子：5 5 7
   稳定的排序可以改成不稳定的排序，但是不稳定的排序不能改成稳定的排序

希尔排序

1. 对直接插入排序进行了优化，如果是 5 4 3 2 1 会退化为O(N^2)
2. 分组：分完组后，每组都采用直接插入排序
3. 中间隔一些元素进行分组的好处：比较大的元素都往后走了，比较小的元素都往前走了
4. 缩小增量到最后会把整体看成是一组，5 3 1 组，前面的5 3 都是预排序，真正的排序是最后的一组
5. 缩小增量的目的：为了让排序更接近O(N)，为了让排序更快

// 希尔排序
    public static void shellSort(int[] array){
        int gap = array.length;
        while(gap > 1){
            gap /= 2;
            shell(array,gap);
        }
    }

    // 对每组进行插入排序
    public static void shell(int[] array,int gap){
        for(int i = gap;i < array.length;i++){
            int j = i - gap;
            int tmp = array[i];
            for(;j >= 0;j -= gap){
                if(array[j] > tmp){
                    array[j+gap] = array[j];
                }else{
                    break;
                }
            }

            array[j + gap] = tmp;
        }
    }

分析

1. 时间复杂度：O(N^1.3 - N ^ 1.5)，时间复杂度不好计算
2. 空间复杂度：O(1)
3. 稳定性：不稳定的排序

检测排序速度：

public static void testInsert(int[] array){
        long startTime = System.currentTimeMillis();
        int[] tmp = Arrays.copyOf(array,array.length);
        Sort.insertSort(tmp);

        long endTime = System.currentTimeMillis();
        System.out.println(" " + (endTime - startTime));
    }

    public static void testShell(int[] array){
        long startTime = System.currentTimeMillis();
        int[] tmp = Arrays.copyOf(array,array.length);
        Sort.shellSort(tmp);

        long endTime = System.currentTimeMillis();
        System.out.println(" " + (endTime - startTime));
    }

    // 逆序初始化
    public static void initOrder(int[] array){
        for(int i = 0;i < array.length;i++){
            array[i] = array.length - i;
        }
    }
    public static void main(String[] args) {
        int[] arr = new int[10000];
        initOrder(arr);
        testInsert(arr);
        testShell(arr);
    }

选择排序

1. 在当前i下标对应的值的后面，找到后面最小的值和i下标对应的值交换
   

	// 交换
    public static void swap(int i, int j, int[] array){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    // 选择排序
    public static void selectSort(int[] array){
        // 在i下标的后面找到比i下标对应的值的最小值,然后交换
        int n = array.length;
        for(int i = 0;i < n;i++){
            int minIndex = i;
            for(int j = i + 1;j < n;j++){
                if(array[j] < array[i]){
                   if(array[j] < array[minIndex]){
                       minIndex = j;
                   }
                }
            }
            swap(i,minIndex,array);
        }
    }

2. 双向选择排序
   时间复杂度还是O(N^2)
   左边找最大的，右边找最小的，和第一个数和最后一个数交换
   
   存在缺陷，maxIndex下标可能是在0下标是最大的，0下标会和最小值小标的值交换，那么0下标就不是最大值下标，应该更新为maxIndex = minIndex

public static void selectSort2(int[] array){
        // 在i下标的后面找到比i下标对应的值的最小值,然后交换
        int left = 0;
        int right = array.length - 1;
        while(left < right){
            int minIndex = left;
            int maxIndex = left;
            for(int i = left + 1;i <= right;i++){
                if(array[i] < array[minIndex]){
                    minIndex = i;
                }
                if(array[i] > array[maxIndex]){
                    maxIndex = i;
                }
            }
            swap(left,minIndex,array);
            // 第一个数是最大的数,防止最小的下标和第一个数换了,最大值就在minIndex的位置了
            if(maxIndex == left){
                maxIndex = minIndex;
            }
            swap(right,maxIndex,array);
            left++;
            right--;
        }
    }

分析

1. 时间复杂度：O(N^2)
2. 空间复杂度：O(1)
3. 稳定性：不稳定的排序

堆排序

// 堆排序
    private static void shifDown(int[] array,int parent,int len){
        int child = 2 * parent + 1;
        while(child < len){
            if(child + 1 < len && array[child] < array[child + 1]){
                child++;
            }

            if(array[child] > array[parent]){
                swap(child,parent,array);
                parent = child;
                child = 2 * parent + 1;
            }else{
                break;
            }
        }
    }

    private static void createHeap(int[] array){
        // 建立大根堆
        for(int parent = (array.length - 1 - 1) / 2;parent >= 0;parent--) {
            shifDown(array, parent, array.length);
        }
    }

    public static void heapSort(int[] array){
        createHeap(array);
        int end = array.length - 1;
        while(end > 0){
            swap(end,0,array);
            shifDown(array,0,end);
            end--;
        }
    }

分析

1. 时间复杂度：O(N * logN)
2. 空间复杂度：O(1)
3. 稳定性：不稳定的排序

冒泡排序

// 冒泡排序
    public static void bubbleSort(int[] array){
        // i是趟数
        for(int i = 0;i < array.length;i++){
            // j是比较的大小的
            boolean flag = true;
            for(int j = 0;j < array.length - i - 1;j++){
                if(array[j] > array[j + 1]){
                    swap(j,j + 1,array);
                    flag = false;
                }
            }
            if(flag) {
                break;
            }
        }
    }

分析

1. 时间复杂度：O(N ^ 2)
2. 空间复杂度：O(1)
3. 稳定性：稳定的排序

快速排序

霍尔法

1. 根据二叉树进行递归划分

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


    private static void quick(int[] array,int start,int end){
        if(start >= end){
            return;
        }

        int prvot = partitionHoare(array,start,end);
        quick(array,start,prvot - 1);
        quick(array,prvot + 1,end);
    }

    private static int partitionHoare(int[] array,int left,int right){
        // 基准元素
        int tmp = array[left];
        // 记录第一个基准下标
        int i = left;
        while(left < right) {
            // 必须先找先右再左
            // 找小
            while (left < right && array[right] >= tmp) {
                right--;
            }
            // 找大
            while (left < right && array[left] <= tmp) {
                left++;
            }
            swap(left, right, array);
        }
        swap(i,left,array);

        return left;
    }

2. 为什么有等于号？
   没有等于号，会死循环，比如两端都是6

4. 为什么先从右边开始，不先从左边开始？
   先走左边的话，先遇到大的停下来，如果相遇的话，那么相遇位置的值就是大于基准元素的，这时候交换的话，6的左边有一个数比6大
   

分析

1. 时间复杂度：
   最好情况下：O(N * logN)
   每层都有N个节点，高度为logN，需要每个节点都遍历到，N * logN次遍历
   最坏情况下：O(N^2)，有序/逆序，单分支的树
2. 空间复杂度：
   最好情况下：O(logN)
   最坏情况下：O(N)，有序/逆序，单分支的树
   递归左边再递归右边，递归右边左边没有释放
3. 稳定性：不稳定的排序

挖坑法找基准

1. 先走右边再走左边，以第一个元素为基准，并且拿出基准元素，基准元素的位置就是坑，如果右边找到比基准小的，把它放入坑中，左边找到比基准元素大的放到坑中，最后两者相遇，把基准元素放入其中

// 挖坑法
    private static int partitionHole(int[] array,int left,int right){
        // 基准元素
        int tmp = array[left];
        while(left < right) {
            // 必须先找先右再左
            // 找小
            while (left < right && array[right] >= tmp) {
                right--;
            }
            array[left] = array[right];
            // 找大
            while (left < right && array[left] <= tmp) {
                left++;
            }
            array[right] = array[left];
        }
        array[left] = tmp;

        return left;
    }

前后指针法

1. 如果cur比基准元素小并且cur下标的值和prev下标的值不相等，

// 前后指针法
    public static int partition(int[] array,int left,int right){
        int prev = left;
        int cur = left + 1;
        while(cur <= right){
            while(array[cur] < array[left] && array[++prev] != array[cur]){
                swap(cur,prev,array);
            }
            cur++;
        }
        swap(prev,left,array);

        return prev;
    }

题目

1. 优先试挖坑法，其次是Hoare，最后是前后指针法

A

快排的优化

1. 均匀的分割数组
2. 让递归的次数变少

三数取中法

1. 三数取中法：left，right，mid三个下标中的中间值和第一个数交换位置，然后右边找比基准元素小的值，左边找比基准元素大的值
2. 规定array[mid] <= array[left] <= array[right]
   

// 三数取中法,求中位数的下标
    private static int middleNum(int[] array,int left,int right){
        int mid = (left + right) / 2;
        if(array[left] < array[right]){
            // 1. x < 3 < 9
            // 2. 3 < 9 < x
            // 3. 3 < x < 9
            if(array[mid] < array[left]){
                return left;
            }
            else if(array[mid] > array[right]){
                return right;
            }
            else{
                return mid;
            }
        }else{
            // 9 > 3 == left > right
            // 1. x > left > right
            if(array[mid] > array[left]){
                return left;
            }else if(array[right] > array[mid]){
                // 2. left > right > x
                return right;
            }else{
                // 3. left > x > right
                return mid;
            }
        }
    }

    private static void quick(int[] array,int start,int end){
        if(start >= end){
            return;
        }

        // 1 2 3 4 5 6 7
        // 中间值的下标和第一个数交换,作为新的基准元素
        int index = middleNum(array,start,end);
        swap(index,start,array);
        // 4 2 3 1 5 6 7
        // 为了让左右分布更均匀,降低树的高度,减少递归的次数

        int prvot = partition(array,start,end);
        quick(array,start,prvot - 1);
        quick(array,prvot + 1,end);
    }

只剩最后几层时，使用插入排序进行优化，降低递归次数，可以使用插入排序是因为前面递归成有序的序列了

public static void insertSort(int[] array,int left,int right){
        for(int i = left + 1;i <= right;i++){
            int j = i - 1;
            int tmp = array[i];
            for(;j >= left;j--){
                if(array[j] > tmp){
                    array[j+1] = array[j];
                }else{
                    break;
                }
            }

            array[j + 1] = tmp;
        }
    }

    private static void quick(int[] array,int start,int end){
        if(start >= end){
            return;
        }

        if(end - start + 1 <= 15){
            // 减少递归的次数
            // 因为最后几层节点数最多,递归次数也多
            insertSort(array,start,end);
            return;
        }

        // 1 2 3 4 5 6 7
        // 中间值的下标和第一个数交换,作为新的基准元素
        int index = middleNum(array,start,end);
        swap(index,start,array);
        // 4 2 3 1 5 6 7
        // 为了让左右分布更均匀,降低树的高度,减少递归的次数

        int prvot = partition(array,start,end);
        quick(array,start,prvot - 1);
        quick(array,prvot + 1,end);
    }

非递归实现快排

1. 找基准里面会进行交换元素，进行排序，外面就进行找到左右下标位置

 // 非递归实现快速排序
    public static void quickSortNor(int[] array){
        int start = 0;
        int end = array.length - 1;
        Stack<Integer> stack = new Stack<>();

        int pivot = partitionHoare(array,start,end);
        if(pivot - 1 > start){
            // 左边有两个元素
            stack.push(start);
            stack.push(pivot - 1);
        }
        else if(pivot + 1 < end){
            // 右边至少有两个元素
            stack.push(pivot + 1);
            stack.push(end);
        }
        // 找基准里面会互换元素进行排序
        while(!stack.empty()){
            end = stack.pop();
            start = stack.pop();

            pivot = partitionHoare(array,start,end);
            if(pivot - 1 > start){
                // 左边有两个元素
                stack.push(start);
                stack.push(pivot - 1);
            }
            else if(pivot + 1 < end){
                // 右边至少有两个元素
                stack.push(pivot + 1);
                stack.push(end);
            }
        }

归并排序

1. 分解：根据mid进行分解

2. 合并：第一个有序段和第二个有序段，比较大小放入一个新的数组中
   

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

    private static void merge(int[] array,int start,int end){
        if(start >= end){
            return;
        }

        int mid = (start + end) / 2;
        // 分解
        merge(array,start,mid);
        merge(array,mid + 1,end);
        // 合并
        mergeHeB(array,start,mid,end);
    }

    private static void mergeHeB(int[] array, int left, int mid, int right) {
        int s1 = left;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = right;

        // 新数组的下标
        int k = 0;
        int[] tmpArray = new int[right - left + 1];

        while(s1 <= e1 && s2 <= e2){
            if(array[s1] < array[s2]){
                tmpArray[k++] = array[s1++];
            }else{
                tmpArray[k++] = array[s2++];
            }
        }

        while(s1 <= e1){
            tmpArray[k++] = array[s1++];
        }

        while(s2 <= e2){
            tmpArray[k++] = array[s2++];
        }

        // left是因为有左边还有右边的数组
        // tmpArray是临时数组,会销毁的,需要拷贝回原来的数组
        for(int i = 0;i < tmpArray.length;i++){
            array[i + left] = tmpArray[i];
        }
    }

分析

1. 时间复杂度：O(N * logN)
2. 空间复杂度：O(N)，因为每次合并数组的时候要开O(N)大小的额外空间
3. 稳定性：稳定的排序

非递归实现归并排序

1. 先一个一个有序，两个两个有序，四个四个有序，八个八个有序…
2. gap = 1
   left = i
   mid = left + gap - 1
   right = mid + gap
   gap *= 2
3. 每组合并完，最终就有序了

// 非递归实现归并排序
    public static void mergeSortNor(int[] array){
        // gap表示每组的数据个数
        int gap = 1;
        while(gap < array.length){

            for(int i = 0;i < array.length;i = i + 2 * gap){
                int left = i;

                // mid和right可能会越界
                // 比如只有5个元素
                // 分解右边一半的时候
                // l = i mid = 5 r = 7
                int mid = left + gap - 1;
                int right = mid + gap;

                if(mid >= array.length){
                    mid = array.length - 1;
                }
                if(right >= array.length){
                    right = array.length - 1;
                }


                mergeHeB(array,left,mid,right);
            }

            gap *= 2;
        }
    }

海量数据的排序

1. 使用归并排序进行外部排序，如果内存中不够空间的话

非比较的排序

计数排序

1. 通过统计每次数字出现的次数，最后按照顺序从小到大输出这些数字
2. 适用的场景：指定范围内的数据

// 计数排序,指定范围内的数据进行排序
// O(Max(N，范围))
    public static void countSort(int[] array){
        int minVal = array[0];
        int maxVal = array[0];
        
        // O(N)
        for(int i = 0;i < array.length;i++){
            if(minVal > array[i]){
                minVal = array[i];
            }
            if(maxVal < array[i]){
                maxVal = array[i];
            }
        }

        int len = maxVal - minVal + 1;
        int[] count = new int[len];
        // O(N)
        for(int i = 0;i < array.length;i++){
            count[array[i] - minVal]++;
        }
                       
        // 写回array数组中
        // O(范围)
        // 因为count数组集中于一个数字,那么也是O(范围)
        // 如果count数组不集中于一个数子,也是N倍的范围
        // 也是O(范围)
        int k = 0;
        for(int i = 0;i < count.length;i++){
            while(count[i] > 0){
                array[k++] = i + minVal;
                count[i]--;
            }
        }
    }

分析

1. 时间复杂度：O(Max(N，范围))
2. 空间复杂度：O(范围)
3. 稳定性：稳定的排序

基数排序

1. 开10个大小的空间，分别依次比较个位大小，十位大小和百位大小，最终达到有序，每个空间都是一个队列

桶排序

1. 先把数字放入一个范围的区间内进行排序，排好序依次拿出来，最终就有序了