关于数据结构和算法:数据结构与算法1排序Sort

六种常见排序算法的复杂度和稳定性：

稳定性指的是对于相等的元素，排序前后可能保障这些元素的绝对秩序不变，如[1-A, 2-B, 3-C, 2-D], 字母仅仅示意一个绝对秩序，稳定性的排序后果为[1-A, 2-B, 3-C, 2-D]，非稳定性的排序后果为 **[1-A, 2-D, 3-C, 2-B]

排序算法	最坏工夫	均匀工夫	稳定性
冒泡排序 (BubbleSort)	O(N2)	O(N2)	稳固
抉择排序 (SelectSort)	O(N2)	O(N2)	不稳固
插入排序 (InsertSort)	O(N2)	O(N2)	稳固
归并排序 (MergeSort)	O(NlogN)	O(NlogN	稳固
疾速排序 (quickSort)	O(N2)	O(NlogN)	不稳固
堆排序 (heapSort)	O(NlogN)	O(NlogN)	不稳固

比较简单的一种排序算法，次要思维为：每次都从 0 地位开始，比拟以后元素和下一个元素的大小，如果逆序则进行替换。每次比对都相当于遍历一次数组的无序局部，并将最大的元素传递到队尾，排序的过程很像冒泡一样。

public class sort_bubbleSort {public static void main(String[] args) {int[] arr = ArrayGenerator.array(20, 20);  // 随机数组生成器
        System.out.println(Arrays.toString(arr));
        bubbleSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void bubbleSort(int[] arr){for(int i = 0; i < arr.length; i++){
            boolean shutdown = true;   // 加状态位提前结束
            for(int j = 0; j < arr.length - i - 1; j++){if(arr[j] > arr[j+1]){
                    shutdown = false;
                    swap(arr, j, j + 1);
                }
            }
            if(shutdown){break;}
        }
    }

    public static void swap(int[] arr, int i, int j){int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

算法思维：每次从以后无序序列中抉择最大值 (最小值) 替换到无序序列的队尾 (队首)。每一次的抉择最大值(最小值) 须要遍历一次无序局部，要做 n - 1 次抉择，因而工夫复杂度相当于 1 - n 之间的间断数相加，天然为 O(N2)。但与冒泡排序相比，在最坏状况，每一次的外循环，抉择排序只会做一次替换和 n 次比拟；而冒泡排序则要做 n 次比拟和 n 次替换，因而工夫复杂度尽管一个等级，抉择排序的理论耗时要小于冒泡排序

因为该算法每次比对都须要遍历到无序局部的开端，当存在多个最大值时，前面的最大值会笼罩后面的(即选最初的最大值进行替换)，因而是不稳固的排序

public class sort_selectSort {public static void main(String[] args) {int[] arr = ArrayGenerator.array(20, 20);
        System.out.println(Arrays.toString(arr));
        selectSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    
    public static void selectSort(int[] arr){for(int i = 0; i < arr.length; i++){
            int minIndex = i;
            for(int j = i; j < arr.length; j++){minIndex = arr[minIndex] > arr[j] ? j : minIndex;
            }
            swap(arr, minIndex, i);
        }
    }
    
    public static void swap(int[] arr, int i, int j){int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

算法思维：将数组分为有序局部 (右边) 和无序局部 (左边)，对于左边无序局部的元素，将其与有序局部进行顺次比拟，直到找到本人应该插入的地位进行插入。
插入排序每一次外循环最坏状况要进行的替换次数会大于抉择排序，但在最好状况下，插入排序能实现 O(N)的工夫复杂度，因而均匀来看，插入排序的性能是要优于抉择排序的

public class sort_InsertSort {public static void main(String[] args) {int[] arr = ArrayGenerator.array(20, 20);
        System.out.println(Arrays.toString(arr));
        insertSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    
    public static void insertSort(int[] arr){for(int i = 1; i < arr.length; i++){for (int j = i - 1; j >= 0 && arr[j + 1] < arr[j]; j--) {swap(arr, j, j + 1);
            }
            
    public static void swap(int[] arr, int i, int j){int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

PLUS：下面 3 中算法比拟根底，都是繁多的替换排序思维，比拟 low，不会波及到与其余算法思维的联合。而上面三种算法，每种算法都是替换排序算法与其余算法思维或数据结构的联合，因而可能衍生出许多变种问题！

引入算法思维：二分思维
思路：将数组一直进行二分，直到不可分(单元素)，宰割的工夫复杂度为 O(logN)，对离开的左右局部进行归并(merge)。因为宰割的最小局部为单元素，而单元素天然有序，因而问题就成为了对两个有序序列的合并问题，合并过程的复杂度为 O(N)。因而总复杂度就进化为 O(NlogN)

归并排序升高排序工夫复杂度须要付出空间复杂度的代价，在合并过程中，必须申请额定的数组空间。

public class sort_mergeSort {public static void main(String[] args) {int[] arr = ArrayGenerator.array(20, 20);
        System.out.println(Arrays.toString(arr));
        mergeSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
    
    public static void mergeSort(int[] arr, int L, int R){if(L >= R){return;}
        int mid = L + (R - L) / 2;
        mergeSort(arr, L, mid);
        mergeSort(arr, mid + 1, R);
        merge(arr, L, mid, R);
    }
    
    public static void merge(int[] arr, int L, int mid, int R){
        int l = L;
        int r = mid + 1;
        int[] tmp = new int[R - L + 1];
        int i = 0;

        while(l <= mid && r <= R){tmp[i++] = arr[l] > arr[r] ? arr[r++] : arr[l++];
            // 这里能够加一些业务逻辑
        }

        while(l <= mid){tmp[i++] = arr[l++];
        }
        while(r <= R){tmp[i++] = arr[r++];
        }

        for(int k = 0; k <= R - L; k++){arr[L + k] = tmp[k];
        }
    }
    
    public static void swap(int[] arr, int i, int j){int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

归并排序会衍生出一些算法问题。因为归并排序时稳固的，且工夫复杂度降到了 O(NlogN), 因而一些 须要进行对数组进行双层循环且对元素的秩序性要求严格的问题都能够应用归并排序进行优化
衍生问题：无序数组的逆序对数量

引入的算法思维：分组思维 + 二分思维
分组思维就是对一个数组按 target 进行分组，数组中大于 target 的值放在右边，小于 target 的数放在左边。
疾速排序的流程就是不停地对数组进行分组，第一次分组后，对大于 target 局部和小于 target 的局部持续进行分组，直到数组齐全有序

public class sort_quickSort {public static void main(String[] args) {int[] arr = ArrayGenerator.array(20, 20);
        System.out.println(Arrays.toString(arr));
        quickSort(arr, 0, arr.length - 1, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
    
    public static void quickSort(int[] arr, int L, int R, int x) {if( L >= R){return;}
        int[] info = partition(arr, L, R, x);
        quickSort(arr, L, info[0], info[0]);
        quickSort(arr, info[1], R, R);
    }
    
    public static int[] partition(int[] arr, int L, int R, int x){
        // 返回分组后左局部的尾索引和右局部的头索引
        int l = L - 1, r = R + 1;
        int i = L;
        while(i < r){if(arr[i] < arr[x]){swap(arr, i++, ++l);
            }else if(arr[i] > arr[x]){swap(arr, i, --r);
            }else{i++;}
        }
        return new int[]{l,r};
    }
    
    public static void swap(int[] arr, int i, int j){int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

衍生问题：荷兰国旗问题(本质上就是 partition 过程)、随机快排(随机抉择 target)

引入数据结构：堆 (最大堆)
堆本质上是 齐全二叉树 的一种构造，有最大堆和最小堆，以最大堆为例，最大堆的特点就是根节点的值肯定大于左孩子和右孩子，因而一个 最大堆构造中，节点的最大值就是根节点的值
堆排序本质上就是抉择排序的思维，不同的是，抉择的过程应用堆这个数据结构来进行优化 。一个节点为 N 的堆插入一个新节点，保护的工夫复杂度只须要 O(logN), 而对于一个有 N 个元素的有序数组，插入一个新元素，将要破费 O(N) 的工夫

堆排序流程：

首先所有元素入堆(最大堆)，堆的根节点就是数组的最大值
将堆的顶点和数组的开端元素进行替换，并从新保护堆
因为数组开端已有序，因而堆的规模 – 1
反复上述过程，直到堆的规模为 1

PLUS：堆作为一种齐全二叉树，满足以下个性：

索引为 i 的节点其如果有左孩子，则左孩子索引为 2 * i + 1
索引为 i 的节点其如果有右孩子，则右孩子索引为 2 * i + 2

public class sort_heapSort {public static void main(String[] args) {int[] arr = ArrayGenerator.array(20, 20);
        System.out.println(Arrays.toString(arr));
        heapSort(arr, arr.length);
        System.out.println(Arrays.toString(arr));
    }

    public static void heapSort(int[] arr, int heapSize){for(int i = 0; i < heapSize; i++){buildHeap(arr, i);
        }
        while(heapSize > 0){swap(arr, 0, --heapSize);
            reHeap(arr, 0, heapSize);
        }
    }

    public static void buildHeap(int[] arr, int index){  
        // 每次退出一个节点到开端
        while(arr[index] > arr[(index - 1) / 2]){swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    public static void reHeap(int[] arr, int index, int heapSize){   // 当顶点变动时，从新保护堆
        int L ;
        while((L = index * 2 + 1) < heapSize ){int maxIndex = L + 1 < heapSize && arr[L + 1] > arr[L] ? L + 1 : L;
            if(arr[maxIndex] > arr[index]){swap(arr, index, maxIndex);
                index = maxIndex;
            }else{break;}

        }
    }

    public static void swap(int[] arr, int i, int j){int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

衍生问题：本质上应该反过来说，堆排序仅仅是堆构造的一个衍生利用而已，堆构造常常利用于保护一个动静序列的最大值和最小值 ，因为无论是插入还是取出，堆构造的 reHeap 过程都是 O(logN)
常见须要用到堆的问题：合并 K 个有序数组或者链表、一些贪婪问题、须要保护动静序列的最大最小值问题

关于数据结构和算法:数据结构与算法1排序Sort

1. 总览

2. 冒泡排序 BubbleSort

3. 抉择排序 SelectSort

4. 插入排序 InsertSort

5. 归并排序 MergeSort

6. 疾速排序 QuickSort

7. 堆排序 HeapSort

Just My Socks（注册教程内含优惠码）

关于数据结构和算法:数据结构与算法1排序Sort

1. 总览

2. 冒泡排序 BubbleSort

3. 抉择排序 SelectSort

4. 插入排序 InsertSort

5. 归并排序 MergeSort

6. 疾速排序 QuickSort

7. 堆排序 HeapSort

Just My Socks（注册教程 内含优惠码）

Just My Socks（注册教程内含优惠码）