算法之排序

算法的学习总是断断续续的，总算看完了排序算法这一章节的内容，排序思想大概都已经能理解了，奈何编程水平恐怕不是很高，部分算法仍旧不能自己独立的去实现～怕是要继续增强自己的编程能力了～
此篇博文主要是记录与排序算法相关的知识点，如果在某些地方表述不正确的，还希望大家能够指出，共同进步～

基于比较思想的排序算法

首先为了减少代码的重复性，抽离出实现代码中经常使用到的交换函数：

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

冒泡排序

public int[] bubbleSort(int[] A, int n) { //n表示数组长度
    // write code here
    for(int i = n - 1; i >= 0; i--){
        for(int j = 0; j < i; j++){
            if(A[j] > A[j + 1]){
                swap(A, j, j + 1);
            }
        }
    }
    return A;
}

主要思想：使用两层嵌套循环比较，内层循环比较相邻的元素，如果第一个比第二个大，则交换两个元素。一次内循环比较结束后，最大的元素将会被交换到n-1的位置上，缩小范围继续执行外循环，依次会将剩下元素中相对最大的元素置换到n-2、n-3 … 1的位置上，数组排序完成。
冒泡排序因为使用了两层嵌套循环，所以其时间复杂度为O(N^2)。
举个简单的例子：
首先考察n-1范围

比较相邻两个元素之间的大小，发现6比3大，则交换两个元素


继续比较相邻元素


经过一轮循环比较相邻元素后，最大的元素会被交换到n-1位置上

接着将范围缩小至n-2

重复上述比较过程，数组排序完毕。

选择排序

public int[] selectionSort(int[] A, int n) {
    // write code here
    int index = 0;
    for(int i = 0; i < n - 1; i++){
        index = i;
        for(int j = i + 1; j < n; j++){
            index = A[index] > A[j]? j : index;
        }
        swap(A, i, index);
    }
    return A;
}

主要思想：选择排序使用两层嵌套循环比较，外层循环记录结果元素需要放置的位置，内层循环选择剩下元素中相对最小的元素。经过一次内循环后选择出最小的元素与i为0位置上的元素交换，即作为第一个元素，一次进行下去，剩下元素中相对较小的元素就放在了1,2…n-1位置上，数组排序完成。
选择排序因为使用了两层嵌套循环，所以其时间复杂度也为O(N^2)。
举个简单的🌰：
首先考察0～n-1范围

在0～n-1范围内选出最小的元素，与数组中第一个元素交换


继续考察1～n-1范围，在1～n-1范围内选出最小的元素，与数组中第二个元素交换


重复上述比较过程，数组排序完毕。

插入排序

 public int[] insertionSort(int[] A, int n) {
    // write code here
    int index = 0;
    for(int i = 1; i < n; i++){
        index = i;
        while(index > 0){
            if(A[index] < A[index - 1]){
                swap(A, index, index - 1);
                index--;
            }
            else{
                break;
            }
        }
    }
    return A;
}

主要思想：使用两层嵌套循环比较，将数组中的每一个元素进行向前比较，如果该元素小于前一个元素，则两个元素交换位置index–，继续与前一个元素比较，知道index=0，该元素放在大小合适的位置上。依次循环比较数组中的每一个元素，直至i=n-1，数组排序完成。
举个简单的🌰：
首先考察数组的第二个元素，与第一个元素进行比较，5比6小，则交换两个元素


接着考察数组中的第三个元素，先与第二个元素进行比较，小于则交换两个元素，接着再与第一个元素比较，小于则再交换两个元素。



根据此过程依次考察数组中的所有元素，数组排序完毕。
插入排序时间复杂度为O(N^2)。

归并排序

public int[] mergeSort(int[] A, int n) {
    // write code here
    if (A == null || n < 2) {
        return null;
    }
    process(A, 0, n - 1);
    
    return A;
}
public static void process(int[] arr, int left, int right) {
    if (left == right) {
        return;
    }
    int mid = (left + right) / 2;
    process(arr, left, mid);
    process(arr, mid + 1, right);
    merge(arr, left, mid, right);
}
public static void merge(int[] arr, int left, int mid, int right) {
    int[] help = new int[right - left + 1];
    int l = left;
    int r = mid + 1;
    int index = 0;
    while (l <= mid && r <= right) {
        if (arr[l] <= arr[r]) {
            help[index++] = arr[l++];
        } else {
            help[index++] = arr[r++];
        }
    }
    while (l <= mid) {
        help[index++] = arr[l++];
    }
    while (r <= right) {
        help[index++] = arr[r++];
    }
    for (int i = 0; i < help.length; i++) {
        arr[left + i] = help[i];
    }
}

主要思想：首先将数组划分为单位长度为1的有序区间，然后把相邻的长度为1的有序区间进行合并，得到最大长度为2的有序区间，接下来再把相邻长度的有序区间合并得到长度为4的有序区间，依次这样进行下去，直到让数组中所有的数合并为一个有序区间，数组排序完毕，过程结束。
归并排序的过程：




根据此过程直到让数组中所有的数合并为一个有序区间，数组排序完毕。
归并排序时间复杂度为O(NlogN)。

快速排序

public int[] quickSort(int[] arr, int n) {
    // write code here
    if (arr == null || n < 2) {
        return null;
    }
    process(arr, 0, n - 1);
    return arr;
}
public static void process(int[] arr, int left, int right){
    if(left < right){
        int random = left + (int) (Math.random() * (right - left + 1));
        swap(arr, random, right);
        int mid = partition(arr, left, right);
        process(arr, left, mid - 1);
        process(arr, mid + 1, right);
    }
}
public static int partition(int[] arr, int left, int right){
    int pivot = left - 1;
    int index = left;
    while (index <= right) {
        if (arr[index] <= arr[right]) {
            swap(arr, ++pivot, index);
        }
        index++;
    }
    return pivot;
}

主要思想：随机选中一个划分值，将小于等于划分值的元素放在元素的左边，大于划分值的元素放在元素的右边，再对左右两部分分别递归地调用快速排序的过程，数组排序完毕，过程结束。
快速排序的过程：



一次划分过程，即选择一个划分值之后小于等于划分值的数是如何放在元素的左边，大于划分值的数如何放在元素的右边：
首先令划分值放在数组最后的位置，然后我们设置一个小于等于的区间，区间的初始长度为0，放在整个数组的左边

接下来从左到右遍历数组中的元素，如果当前元素大于划分值，则继续遍历下一个值

如果当前元素小于等于划分值，则把当前数与小于等于区间的下一个数进行交换，然后令小于等于区间右扩一个长度



在遍历完所有元素，直到最后的元素时，将最后的元素即划分值与小于等于区间的下一个数进行交换，这样就完成了一次完整的划分过程。

快速排序时间复杂度为O(NlogN)。

堆排序

public int[] heapSort(int[] arr, int n) {
        // write code here
        for (int i = 0; i < n; i++) {  
        createMaxdHeap(arr, n - 1 - i);  
        swap(arr, 0, n - 1 - i);    
        }  
        return arr;
    }
public static void createMaxdHeap(int[] data, int lastIndex) {  
    for (int i = (lastIndex - 1) / 2; i >= 0; i--) {  
        // 保存当前正在判断的节点  
        int k = i;  
        // 若当前节点的子节点存在  
        while (2 * k + 1 <= lastIndex) {  
            // biggerIndex总是记录较大节点的值,先赋值为当前判断节点的左子节点  
            int biggerIndex = 2 * k + 1;  
            if (biggerIndex < lastIndex) {  
                // 若右子节点存在，否则此时biggerIndex应该等于 lastIndex  
                if (data[biggerIndex] < data[biggerIndex + 1]) {  
                    // 若右子节点值比左子节点值大，则biggerIndex记录的是右子节点的值  
                    biggerIndex++;  
                }  
            }  
            if (data[k] < data[biggerIndex]) {  
                // 若当前节点值比子节点最大值小，则交换2者得值，交换后将biggerIndex值赋值给k  
                swap(data, k, biggerIndex);  
                k = biggerIndex;  
            } else {  
                break;  
            }  
        }  
    }  
}

主要思想：首先将数组中的n个数建成一个大小为n的大根堆，堆顶是整个数组中的最大值，将堆顶元素与堆的最后一个元素交换位置，然后将最大值脱离出堆的整个结构，放在数组最后的位置，接下来将n-1大小的堆进行大根堆的调整，调整出n-1大根堆的最大值放在堆顶，再把堆顶位置的值与整个堆的最后元素交换，将最大值脱离出堆的整个结构，放在数组相对最后的位置。依次重复步骤，直到堆的大小减为1为止，整个数组就变为有序数组，过程结束。
堆排序的过程：




堆排序时间复杂度为O(NlogN)。

希尔排序

public int[] shellSort(int[] arr, int n) {
    // write code here
    if(arr == null || n < 2){
        return null;
    }
    int feet = n / 2;
    int index = 0;
    while(feet > 0){
        for(int i = feet; i < n; i++){
            index = i;
            while(index >= feet){
                if(arr[index - feet] > arr[index]){
                    swap(arr, index - feet, index);
                    index -= feet;
                }
                else{
                    break;
                }
            }
        }
        feet /= 2;
    }
    return arr;
}

主要思想：希尔排序是插入排序的一个改良算法，插入排序步长为1，希尔排序步长可调整。
举个🌰来说明：
初始步长为3时，数组前3个数6 5 3是不需要考虑的

从1开始，1向前跳3位来到了6的数上，1和6进行比较发现1比6小，则两个元素交换位置

接下来1就来到了位置0，往前跳3位，则已经越界，所以交换的过程停止，然后继续考察下一位数，直到数组末尾，步长为3的插入排序结束

调整步长继续进行插入排序的过程，希尔排序最终都会以步长为1的情况结束

希尔排序的关键是步长的选择，时间复杂度为O(NlogN)。

基于桶排序的排序算法

计数排序

 public int[] countingSort(int[] arr, int n){
    if (arr == null || n < 2) {
        return null;
    }
    int min = arr[0];
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        min = Math.min(arr[i], min);
        max = Math.max(arr[i], max);
    }
    int[] countArr = new int[max - min + 1];
    for (int i = 0; i < n; i++) {
        countArr[arr[i] - min]++;
    }
    int index = 0;
    for (int i = 0; i < countArr.length; i++) {
        while (countArr[i]-- > 0) {
            arr[index++] = i + min;
        }
    }
    return arr;//将排序好的数组返回，完成排序  
}

主要思想：根据数组中的元素建桶，将数组中的元素依次放入对应的桶中，当所有元素进入桶之后，从最小的桶依次倒出桶中的元素，直到最大的桶号为止，此时，元素被倒出的顺序就是数组排序之后的顺序。上例实现中为了节省内存的开销，记录了数组元素中的最大值以及最小值，并以此来建立最大桶以及最小桶，要注意的是，要考虑存在相等元素的情况，因此要记录每个桶中的元素个数。
举个简单的🌰：
对员工身高进行排序，因为成年人的身高在100cm-300cm之间，所以将桶定义为100-300


将员工身高放入相应的桶号中

从100开始倒出元素，数组排序完毕。

计数排序的时间复杂度为O(N)。

基数排序

public int[] radixSort(int[] array, int n){
    if (array == null || n < 2) {
        return null;
    }
    int d = 10000;   
    int m = 1;//代表位数对应的数：1,10,100...
    int k = 0;//保存每一位排序后的结果用于下一位的排序输入n
    int[][] bucket = new int[10][n];//排序桶用于保存每次排序后的结果，这一位上排序结果相同的数字放在同一个桶里
    int[] order = new int[n];//用于保存每个桶里有多少个数字
    while(m < d)
    {
        for(int num : array) //将数组array里的每个数字放在相应的桶里
        {
            int digit = (num / m) % 10;
            bucket[digit][order[digit]++] = num;
        }
        for(int i = 0; i < n; i++)//将前一个循环生成的桶里的数据覆盖到原数组中用于保存这一位的排序结果
        {
            if(order[i] > 0)//这个桶里有数据，从上到下遍历这个桶并将数据保存到原数组中
            {
                for(int j = 0;j < order[i]; j++)
                {
                    array[k++] = bucket[i][j];
                }
            }
            order[i] = 0;//将桶里计数器置0，用于下一次位排序
        }
        m *= 10;
        k = 0;//将k置0，用于下一轮保存位排序结果
    }
    return array;
}

举个简单的🌰来说明基数排序的主要思想：

准备0-9号桶

接下来根据每一个元素个位上的数字，将元素放入对应的桶号中

所有元素进桶后再从9号桶至0号桶依次倒出桶内的元素，组成了一个新序列

根据每一个元素十位上的数字，将新序列中元素放入对应的桶号中

所有元素进桶后再从9号桶至0号桶依次倒出桶内的元素，组成了一个新序列

根据每一个元素百位上的数字，将新序列中元素放入对应的桶号中

所有元素进桶后再从9号桶至0号桶依次倒出桶内的元素，组成了一个新序列

依次迭代下去，最后根据最高位数值选择进入对应的桶中，最后一次倒出的序列就是整个数组排序的结果，过程结束。
基数排序的时间复杂度为O(N)

排序算法的比较

稳定性：假定待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序不变，则称这种排序算法是稳定的，否则称为不稳定的。

排序算法典型案例

小范围排序

已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离可以不超过k，并且k相对于数组来说比较小。请选择一个合适的排序算法针对这个数据进行排序。
选择改进后的堆排序算法

public int[] sortElement(int[] A, int n, int k) {
    if (A == null || A.length == 0 || n < k) {
        return A;
    }
    int[] heap = getKHeap(A, k);
    for(int i = k; i < n; i++){
        A[i - k] = heap[0];
        heap[0] = A[i];
        heapify(heap, 0, k);
    }
    for(int i = n - k; i < n; i++){
        A[i] = heap[0];
        heap[0] = heap[k - 1];
        heapify(heap, 0, --k);
    }
    return A;
        
}
    
public int[] getKHeap(int[] A, int k){
    int[] heap = new int[k];
    for(int i = 0; i < k; i++){
        heapInsert(heap, A[i], i);
    }
    return heap;
}
    
    
public void heapInsert(int[]A, int value, int index){
    A[index] = value;
    while(index != 0){
        int parent = (index - 1) / 2;
        if(A[parent] > A[index]){
            swap(A, parent, index);
            index = parent;
        }
        else{
            break;
        }
    }
}
    
public  void heapify(int[] arr, int index, int heapSize) {
    int left = index * 2 + 1;
    int right = index * 2 + 2;
    int smallest = index;
    while (left < heapSize) {
        if (arr[left] < arr[index]) {
            smallest = left;
        }
        if (right < heapSize && arr[right] < arr[smallest]) {
            smallest = right;
        }
        if (smallest != index) {
            swap(arr, smallest, index);
        } else {
            break;
        }
        index = smallest;
        left = index * 2 + 1;
        right = index * 2 + 2;
    }
}

说明：
整个数组的最小值肯定是在0~k-1这个区间内的

将a[0]~a[k-1]建立小根堆，将栈顶元素放在数组的第一个位置上

然后将元素组的下一个元素放入小根堆，并对小根堆进行调整

将栈顶元素放在数组的第二个位置上

依次重复步骤，数组排序完毕。
时间复杂度为O(NlogK)

重复值判断

请设计一个高效算法，判断数组中是否有重复值。必须保证额外空间复杂度为O(1)。
如果没有空间复杂度的限制，用哈希表实现，此题采用先排序后判断的方法，采用非递归的堆排序实现排序。

public boolean checkDuplicate(int[] a, int n) {
    // write code here
    a = heapSort(a, n);
    for(int i = 0; i < n - 1; i++)
    {
        if(a[i] == a[i + 1])
        {
            return true;
        }
    }
    return false;
}
public int[] heapSort(int[] A, int n) {
        // write code here
        for (int i = 0; i < n; i++) {  
        createMaxdHeap(A, n - 1 - i);  
        swap(A, 0, n - 1 - i);    
        }  
        return A;
    }
    public static void createMaxdHeap(int[] data, int lastIndex) {  
    for (int i = (lastIndex - 1) / 2; i >= 0; i--) {  
        // 保存当前正在判断的节点  
        int k = i;  
        // 若当前节点的子节点存在  
        while (2 * k + 1 <= lastIndex) {  
            // biggerIndex总是记录较大节点的值,先赋值为当前判断节点的左子节点  
            int biggerIndex = 2 * k + 1;  
            if (biggerIndex < lastIndex) {  
                // 若右子节点存在，否则此时biggerIndex应该等于 lastIndex  
                if (data[biggerIndex] < data[biggerIndex + 1]) {  
                    // 若右子节点值比左子节点值大，则biggerIndex记录的是右子节点的值  
                    biggerIndex++;  
                }  
            }  
            if (data[k] < data[biggerIndex]) {  
                // 若当前节点值比子节点最大值小，则交换2者得值，交换后将biggerIndex值赋值给k  
                swap(data, k, biggerIndex);  
                k = biggerIndex;  
            } else {  
                break;  
            }  
        }  
    }  
}

有序数组合并

有两个从小到大排序以后的数组A和B，其中A的末端有足够的缓冲空容纳B。请编写一个方法，将B合并入A并排序。

 public int[] mergeAB(int[] A, int[] B, int n, int m) {
    // write code here
    while(m != 0){
        if(n == 0){
            A[m - 1] = B[m - 1];
            m--;
        }
        else{
            A[m + n - 1] = A[n - 1] > B[m - 1]? A[--n] : B[--m];
        }
    }
    return A;
}

举个🌰来说明：
首先比较数组A和数组B最后的元素

发现6比5大，所以将6拷贝至数组A最后的位置

接着比较数组A倒数第二个元素4和数组B最后一个元素5，发现5比4大，则将5拷贝至数组A倒数第二个位置

依次比较所有的数，直到有序数组B完成拷贝至数组A中为止，那么数组A就是整个合并后的结果。
关键在于从后往前覆盖数组A

三色排序

有一个只由0，1，2三种元素构成的整数数组，请使用交换、原地排序而不是使用计数进行排序。
本题主要过程与快速排序划分过程类似

public int[] sortThreeColor(int[] A, int n) {
    // write code here
    if (A == null || n < 2) {
        return A;
    }
    int left = -1;
    int right = n;
    int index = 0;
    while(index < right){
        if(A[index] == 0){
            swap(A, ++left, index++);
        }
        else if(A[index] == 2){
            swap(A, index, ++right);
        }
        else{
            index++;
        }
    }
    return A;
}

举个🌰：
因为此过程与快速排序划分过程很类似，这里就不做详细说明了

有序矩阵查找

现在有一个行和列都排好序的矩阵，请设计一个高效算法，快速查找矩阵中是否含有值x。

public boolean findX(int[][] mat, int n, int m, int x) {
    int a = 0;
    int b = m - 1;
    while(a < n && b >= 0){
        if (mat[a][b] == x)
        {
            return true ;
        }     
        if (mat[a][b] < x){
            a++ ;
        }     
        if (mat[a][b] > x)
        {
            b--;
        }                
    }
    return false;
}

举个🌰来说明：
从二维数组的右上角开始

如果当前数大于需要找的数，因为整个二维数组中每一列都是有序的，所以当前数下面的所有数都比需要找的数大，此时向左移动

如果当前数小于需要找的数，因为整个二维数组中每一行都是有序的，所以当前数左边的所有数都比需要找的数小，此时向下移动


每一个当前数都根据以上的逻辑进行判断，如果在移动的过程中找到了我们需要找的数，返回true，整个过程结束，如果一直到越界还未找到，则返回false。

最短子数组

对于一个数组，请设计一个高效算法计算需要排序的最短子数组的长度。

 public int shortestSubsequence(int[] A, int n) {
    // write code here
    int max = A[0];
    int min = A[n - 1];
    int left = 0;
    int right = 0;
    for(int i = 1; i < n; i++)
    {
        if(A[i] > max)
        {
            max = A[i];
        }
        else if(A[i] < max)
        {
            right = i;
        }
    }
    for(int i = n - 2; i >= 0; i--)
    {
        if(A[i] < min)
        {
            min = A[i];
        }
        else if(A[i] > min)
        {
            left = i;
        }
    }
    
    return ((right-left) == 0) ? 0 : ((right - left) + 1);
}

举个🌰来说明：
首先从左到右遍历整个数组，使用单独的变量来记录遍历过的元素的最大值，我们只关注于一种情况：遍历过部分的最大值大于当前数的情况，这种情况发生的时候，在真实的排序之后，最大值起码会在当前数的位置或者更右的位置。从左到右遍历的过程中，我们只记录发生这种情况的最右位置；

接下来是从右往左遍历整个数组，使用单独的变量来记录遍历过的元素的最小值，我们依然只关注于一种情况：遍历过部分的最小值小于当前数的情况，这种情况发生的时候，在真实的排序之后，最小值起码会在当前数的位置或者更左的位置。从右到左遍历的过程中，我们只记录发生这种情况的最左位置；

最左位置和最右位置中间的范围就是需要排序的最短子数组

相邻两数最大差值

有一个整形数组A，请设计一个复杂度为O(n)的算法，算出排序后相邻两数的最大差值。
来自桶排序思想

public int maxGap(int[] nums, int n) {
    // write code here
    if (nums == null || n < 2) {
        return 0;
    }
n		int min = Integer.MAX_VALUE;
    int max = Integer.MIN_VALUE;
    for (int i = 0; i < n; i++) {
        min = Math.min(min, nums[i]);
        max = Math.max(max, nums[i]);
    }
    if (min == max) {
        return 0;
    }
    boolean[] hasNum = new boolean[len + 1];
    int[] maxs = new int[len + 1];
    int[] mins = new int[len + 1];
    int bid = 0;
    for (int i = 0; i < n; i++) {
        bid = bucket(nums[i], n, min, max); // 算出桶号
        mins[bid] = hasNum[bid] ? Math.min(mins[bid], nums[i]) : nums[i];
        maxs[bid] = hasNum[bid] ? Math.max(maxs[bid], nums[i]) : nums[i];
        hasNum[bid] = true;
    }
    int res = 0;
    int lastMax = 0;
    int i = 0;
    while (i <= n) {
        if (hasNum[i++]) { // 找到第一个不空的桶
            lastMax = maxs[i - 1];
            break;
        }
    }
    for (; i <= n; i++) {
        if (hasNum[i]) {
            res = Math.max(res, mins[i] - lastMax);
            lastMax = maxs[i];
        }
    }
    return res;
}
public int bucket(long num, long len, long min, long max) {
    return (int) ((num - min) * len / (max - min));
}

说明：

• 首先遍历数组，找到数组的最小值和最大值，在最小值和最大值范围上等量地分成n个区间（n为整个数组的长度）
• 每个区间分别对应一个桶，每个数根据自己的对应区间进入相应的桶，将最大值单独放在n+1号桶中，桶的数量一共有n+1个，而数组元素只有n个，所以在中间必然会出现空桶
• 我们可以很容易知道，在同一个桶中相邻元素的差值不会大于桶区间，而来自空桶两侧的相邻数的最大差值肯定大于桶区间，所以我们只需考虑桶间相邻数的差值，也就是后一个桶的最小值减去前一个桶的最大值
• 接下来我们只需要考虑每一个桶中的最小值与上一个非空桶的最大值的差值，并记录下其中的最大差值，也就是整个数组在排序之后相邻两数的最大差值。

总结

排序算法到这里算是告一段落了，最后的排序案例很是经典，我碰到过好几次，排序算法是算法中重要的一部分知识点，希望自己以后能够将所有的排序算法自主编程实现～继续加油～