十大排序算法

package sort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class AlgorithmOfSort {

    /**
     * 冒泡排序
     * 在排序过程中对元素两两比较，越小的元素会通过交换不断的排到数组的最前面
     * O(n^2)  稳定
     * @param array
     * @return
     */
    public  int[] bubbleSort(int[] array){
        if(array.length==0){
            return new int[]{};
        }
        //总共需要排序array.length-1次
        for(int i=0;i<array.length;i++){
            //这个排序的方法就是不断的将较小的数字不断的向前排放，第i次排序会将第i小的数字放在最前面
            for(int j=array.length-1;j>i;j--){
                if(array[j]<array[j-1]){
                    int temp = array[j-1];
                    array[j-1] = array[j];
                    array[j] = temp;
                }
            }
        }
        return array;
    }

    /**
     * 简单选择排序
     * 在每一次遍历时，找到当前为遍历数组中的最小的值，记录其下标，然后，将这个最小的值和当前的array[i]交换，
     * 下一次遍历时就可以从i+1开始，0-i数组的部分就是已经排序完成的内容了
     * O(n^2)  不稳定
     * @param array
     * @return
     */
    public int[] selectionSort(int[] array){
        if(array.length==0){
            return new int[]{};
        }
        //总共需要找到array.length-1个最小值，不断的排序在最前列
        for(int i=0;i<array.length;i++){
            int minIndex = i;
            for(int j=i+1;j<array.length;j++){
                if(array[j]<array[minIndex]){
                    minIndex = j;
                }
            }
            if(minIndex!=i){
                int temp = array[minIndex];
                array[minIndex] = array[i];
                array[i] = temp;
            }
        }
        return array;
    }

    /**
     * 直接插入排序
     * array[0]为最初的有序序列，不断的将后面的每一个元素加入原先的有序队列中，然后形成一个新的有序队列
     * O(n^2)  稳定
     * @param array
     * @return
     */
    public int[] insertSort(int[] array){
        if(array.length==0){
            return new int[]{};
        }
        for(int i=0;i<array.length-1;i++){
            //current保存这次排序中需要往有序队列中插入的元素，所有后续移动的不用担心这个值会丢失
            int current = array[i+1];
            int index = i;
            while(index>=0&&current<array[index]){
                //不断的把有序序列中比当前current大的数字向后逐个移动
                array[index+1] = array[index];
                index--;
            }
            //因为在不满足while条件的时候，index会多减一次，多以这里需要+1
            array[index+1] = current;
        }
        return array;
    }

    /**
     * 希尔排序
     * 又称缩小增量排序，会优先比较距离较远的元素，会按照增量分组，
     * 然后对每一组使用插入排序，当增量减为1，整个文件恰好被分为一组
     *             8  9  1  7  2  3  5  4  6  0
     * gap = length/2 = 5;
     *             8  9  1  7  2  3  5  4  6  0
     * 分组结果为：(1)(2)(3)(4)(5)(1)(2)(3)(4)(5)
     * 排序结果为： 3  5  1  6  0  8  9  4  7  2
     *           (1)(2)(3)(4)(5)(1)(2)(3)(4)(5)
     * gap = gap/2 = 2;
     *            3  5  1  6  0  8  9  4  7  2
     * 分组结果为：(1)(2)(1)(2)(1)(2)(1)(2)(1)(2)
     * 排序结果为：0  2  1  4  3  5  7  6  9  8
     * gap = gap/2 = 1;
     * 排序结果为：0  1  2  3  4  5  6  7  8  9
     * O(n^1.3)  最坏O(n^2)  不稳定
     * @param array
     * @return
     */
    public int[] shellSort(int[] array){
        if(array.length==0){
            return new int[]{};
        }
        //这是一个比较常见的增量，但是并非最优
        int gap = array.length/2;
        while(gap>0){
            for(int i = gap;i<array.length-gap;i++){
                int index = i-gap;
                int current = array[i];
                //进行直接插入排序，将普通的直接插入排序中的1变为gap即可
                while(index>=0&&current<array[index]){
                    array[index+gap] = array[index];
                    index-=gap;
                }
                array[index+gap] = current;
            }
            gap/=2;
        }
        return array;
    }

    /**
     * 归并排序
     * 将已有的有序序列不断合并，最终得到一个完全的有序序列
     * O(nlog2n)  稳定
     * @param array
     * @return
     */
    public int[] mergeSort(int[] array){
        if(array.length==0){
            return new int[]{};
        }
        if(array.length<2){
            return array;
        }
        int mid = array.length/2;
        //不断的将长序列分割为左右序列，然后使最小的左右序列分别有序，然后在向上合并
        int[] left = Arrays.copyOfRange(array,0,mid);
        int[] right = Arrays.copyOfRange(array,mid,array.length);
        return merge(mergeSort(left),mergeSort(right));
    }
    public int[] merge(int[] left, int[] right){
        int[] res = new int[left.length+right.length];
        for(int index=0, i=0, j=0;index<res.length;){
            if(i>=left.length){
                res[index++] = right[j++];
            }else if(j>=right.length){
                res[index++] = left[i++];
            }else if(left[i]<right[j]){
                res[index++] = left[i++];
            }else{
                res[index++] = right[j++];
            }
        }
        return res;
    }

    /**
     * 快速排序
     * 在待排序序列中选择一个分隔元素(关键字)，将待排序序列中所有小于等于关键字的元素移动到关键字的左边，
     * 其余的移动到关键字的右边，然后将左右两个部分当做两个新的待排序序列，重复上述步骤
     * O(nlong2n)  最坏O(n^2)  不稳定
     * @param array
     * @return
     */
    public void quickSort(int[] array, int low, int high){
        if(array.length==0){
            return;
        }
        if(low<high){
            int privotpos = partition(array,low,high);
            quickSort(array,low,privotpos-1);
            quickSort(array,privotpos+1,high);
        }
    }

    /**
     * 序列划分
     * 设待排序序列包含元素array[low] array[low+1] ... array[high]
     * 选择array[low]作为关键字，设置两个游动下标i = low ,j = high+1
     * 同过i的下标找到一个大于关键字的元素，通过j的下标找到一个小于关键字的元素
     * 如果i>=j 交换array[low] array[j]  否则交换array[i] array[j]
     * @param array
     * @return
     */
    public int partition(int[] array, int low, int high){
        int i = low, j = high+1;
        do{
            do{
                i++;
            }while(i<=high&&array[i]<array[low]);
            do{
                j--;
            }while(array[j]>array[low]);
            if(i<j){
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }while(i<j);
        int temp = array[j];
        array[j]= array[low];
        array[low] = temp;
        //这个j就是分隔元素的下标
        return j;
    }

    /**
     * 堆排序
     * 将一个无序的序列构建成一个堆，然后构建成大顶堆
     * 将堆顶元素与末尾元素交换，将最大元素放到数组的末端
     * 重新调整结构，使其满足堆的定义，然后继续交换堆顶元素和末尾元素
     * 最终得到的就是一个升序的序列
     * O(nlog2n)  不稳定
     * @param array
     * @return
     */
    public void heapSort(int[] array){
        //构建大顶堆
        //这里构建大堆顶是从最后一个非叶子节点开始的
        for(int i = array.length/2-1;i>=0;i--){
            adjustHeap(array,i,array.length);
        }
        for(int i = array.length-1;i>0;i--){
            int temp = array[0];
            array[0] = array[i];
            array[i] = temp;
            adjustHeap(array,0,i);
        }
    }
    void adjustHeap(int[] array, int i, int length){
        int temp = array[i];
        //从i节点的左孩子开始，下一个就是下一层了，所以这里k*2+1
        for(int k = i*2+1;k<length;k = k*2+1){
            //如果i节点的左子节点小于右子结点， 那么就让k指向右子结点
            if(k+1<length&&array[k]<array[k+1]){
                k++;
            }
            //如果子节点的值大于父节点的值，那么就把这个较大的值赋给父节点
            if(array[k]>temp){
                array[i] = array[k];
                i = k;
            }else{
                //如果当前节点（也就是父节点）的值没有变化，也就是没有被他的子节点取代，又因为这个调整是从传入的节点向下处理，
                // 所以只有当这个节点的值发生了变化，也就是说一个更大的值被放在了更高的层次，这是才有必要往下面继续
                break;
            }
        }
        array[i] = temp;
    }

    /**
     * 计数排序
     * 确定数组中的最大值和最小值，然后开辟一个新的数组，大小为最大值和最小值的差值+1，
     * 用来记录数组中每一个数字出现的次数，这时在记录的时候，因为count数组经过空间优化，
     * 所以原数组中的值在作为count数组的下标时应该在减去最小值
     * 但是当数组的最大值和最小值差值过大时，不建议使用计数排序，会浪费过多的空间
     * O(n+k)  稳定
     * @param array
     * @return
     */
    public int[] countingSort(int[] array){
        if(array.length==0){
            return new int[]{};
        }
        int max = array[0], min = array[0];
        for(int i=1;i<array.length;i++){
            max = Math.max(max,array[i]);
            min = Math.min(min,array[i]);
        }
        //这个数组用来保存原数组中每一个元素出现的次数
        int[] count = new int[max-min+1];
        for(int n:array){
            //因为对count数组做出优化，优化了空间，所以这里array[i]对应的下标应该是array[i]-min，这样每一个值才能被转换为count数组的下标
            count[n-min]++;
        }
        int index = 0, i = 0;
        while(index<array.length){
            if(count[i]!=0){
                //实际应该写在array（也就是排序后的数组）中的数字应该是count当前的下标+最小值
                array[index++] = min+i;
                count[i]--;
            }else{
                i++;
            }
        }
        return array;
    }

    /**
     * 桶排序
     * 也就是计数排序的拓展版本，每个桶都表示着一个范围而非计数排序中的一个定值
     * 桶排序是常见排序算法中最快的，大多数情况下比快速排序和归并排序还要快
     * 桶排序非常的消耗空间，是典型的以空间换时间（可以说是最耗费内存的排序算法）
     * 桶排序需要尽量保证元素分散均匀，否则当所有数据集中在同一个桶中时，桶排序失效。
     * O(n+k)  最坏O(n^2)  稳定
     * @param array
     */
    public void bucketSort(int[] array){
        if(array.length==0){
            return;
        }
        int max = array[0], min = array[0];
        for(int i=1;i<array.length;i++){
            max = Math.max(max,array[i]);
            min = Math.min(min,array[i]);
        }
        int bucketNum = (max-min)/array.length+1;
        ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
        for(int i=0;i<bucketNum;i++){
            bucketArr.add(new ArrayList<Integer>());
        }
        for(int n:array){
            bucketArr.get((n-min)/array.length).add(n);
        }
        for(int i=0;i<bucketNum;i++){
            Collections.sort(bucketArr.get(i));
        }
        int index = 0;
        for(ArrayList<Integer> list:bucketArr){
            for(int n:list){
                array[index++] = n;
            }
        }
    }

    /**
     * 基数排序
     * 基数排序就是先找到最大值，确定数组中最大值的位数，然后把所有的数字都补齐为相同的位数，
     * 然后先按照最低位排序，然后按照次低位，等最高位排完序之后，数组自然变得有序了
     *         {21,56,88,195,354,1,35,12,6,7}
     * 按照个位：21,1,12,354,195,35,56,6,7,88
     * 按照十位：1,6,7,12,21,35,354,56,88,195
     * 按照百位：1,6,7,12,21,35,56,88,195,354
     * O(n*k)  稳定
     * @param array
     */
    public void radixSort(int[] array){
        if(array.length==0){
            return;
        }
        int max = array[0];
        for(int i=1;i<array.length;i++){
            max = Math.max(max,array[i]);
        }
        //从个位开始不断的排序
        for(int exp = 1;max/exp>0;exp*=10){
            //这里十个bucket用来记录对应数字的对应位的数字为0~9的出现的次数
            int[] bucket = new int[10];
            int[] temp = new int[array.length];
            //记录了每个桶中的数据数量
            for(int n:array){
                bucket[(n/exp)%10]++;
            }
            for(int i=1;i<10;i++){
                //可以由此确定放置数据的位置
                bucket[i] += bucket[i-1];
            }
            for(int i=array.length-1;i>=0;i--){
                //array[i]/exp%10 获得了 当前数字按照个位十位百位排序的顺序 所对应位的数字
                //bucket现在就类似一个前缀和数组一样，存放着对应位数字应该放置的位置，因为bucket之前统计的是出现的次数，所以存放的实际位置就应该是bucket[array[i]/exp%10]-1
                temp[bucket[(array[i]/exp)%10]-1] = array[i];
                bucket[array[i]/exp%10]--;
            }
            //将数据在放回到array中
            for(int i=0;i<array.length;i++){
                array[i] = temp[i];
            }
        }
    }
}