排序算法总结

排序算法比较

https://www.cnblogs.com/bjwu/articles/10006419.html

冒泡排序

/**冒泡排序
     * 第一次比较0~N-1位 将最大值沉底
     * 第二次比较0~N-2位 将最大值沉底
     * ......
     * 第N-1次比较0~1位 将最大值沉底（在0~1中沉底）
     * 时间复杂度：O(n^2)
     */
    public static void sort(int[] nums){
        if(nums == null || nums.length < 2){
            return;
        }
        for(int end = nums.length-1; end > 0; end--){
            for(int j = 0; j < end; j++){
                if(nums[j] > nums[j+1]){
                    swap(nums,j,j+1);
                }
            }
        }

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

插入排序

/** 插入排序
     *  0~end-1 位置的数都有序
     *  每次考察end位置的数应该插在哪里
     *  如果前面的数比end位置数大则交换
     *
     *  插入选择时间复杂度和数据样本无关
     *  插入排序 有序 O(n) 逆序O(n^2)
     *  时间复杂度按最差的算
     *  所以插入排序的时间复杂度是O(n^2)
     */
    public static void sort(int[] nums){
        for(int end = 1; end < nums.length; end++){
            for(int i = end-1; i >= 0; i--){//与前面有序部分比较是否能够交换
                if(nums[i] > nums[i+1]){
                    swap(nums,i,i+1);
                }
            }
        }
    }

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

选择排序

/**选择排序
     * 第一次比较 0~N-1 找到最小值的位置和0交换
     * 第二次比较 1~N-2 找到最小值的位置和1交换
     * ......
     * 第N-1次比较 N-2~N 找到最小值的位置和N-2交换
     * 时间复杂度：O(N^2)
     */
    public static void sort(int[] nums){
        if(nums == null || nums.length < 2){
            return;
        }
        for(int start = 0; start < nums.length; start++){
            int minIndex = start;
            for(int i = start; i < nums.length; i++){
                minIndex = nums[i] < nums[minIndex]? i:minIndex;
            }
            swap(nums, minIndex, start);
        }

    }

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

快排

public static void quickSort(int [] nums, int left, int right){
        if (nums == null || nums.length < 2) {
            return;
        }
        if(left < right){
            //随机选一个位置和最后一个数字交换
            swap(nums, left+(int)Math.random()*(right-left+1), right);
            int[] p = partition(nums, left, right);//等于区域的左边界和右边界
            quickSort(nums, left, p[0]-1); // 小于区域递归
            quickSort(nums, p[1]+1, right); // 大于区域递归
        }
    }

    public static int[] partition(int[] nums, int left, int right){
        int smaller = left - 1; // 小于区域的右边界
        int bigger = right; // 大于区域的左边界
        while(left < bigger){
            int target = nums[right];
            if(nums[left] > target){
                swap(nums,left,bigger-1);
                bigger--;
            }else if(nums[left] < target){
                swap(nums,left,smaller+1);
                smaller++;
                left++;
            }else {
                left++;
            }
        }
        swap(nums, bigger, right);
        return new int[]{smaller+1,bigger};
    }
    public static void swap(int[] nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

归并排序

/**归并排序
     * 左边排序 右边排序
     * 外排整体排序 辅助数组
     * 左边有序数组和右边有序数组谁小谁加入辅助数组
     * T(N) = 2T(N/2) + O(N)
     * log2(2) = 1 = d -->
     * 时间复杂度为 O(N*logN)
     */
    public static void mergeSort(int[] nums){
        if(nums ==null || nums.length < 2){
            return;
        }
        sortProcess(nums, 0, nums.length-1);
    }
    public static void sortProcess(int[] nums, int left, int right){
        if(left == right){//结束递归条件 这个范围只有一个数
            return;
        }
        int mid = left + (right - left)/2;
        sortProcess(nums,left,mid);//左边有序 T(N/2)
        sortProcess(nums,mid+1,right);//右边有序 T(N/2)
        merge(nums, left, mid, right);//外排序 O(N)
    }

    public static void merge(int[] nums, int left, int mid, int right){
        int[] help = new int[right-left+1];//left到right有多少个数
        int i = 0;//指向help
        int p1 = left;//指向左侧数组第一个数
        int p2 = mid+1;//指向右侧数组第一个数

        while(p1 <= mid && p2 <= right){//有一个数组读完了就退出循环
            //哪边小哪边的p指向的元素加入help 加入之后移动p指针
            help[i++] = nums[p1] < nums[p2] ? nums[p1++] : nums[p2++];
        }
        //只有一个越界 把剩余的数组一次性添加进help
        while(p2 <= right){
            help[i++] = nums[p2++];
        }
        while(p1 <= mid){
            help[i++] = nums[p1++];
        }
        //将help中的依次覆盖nums
        for(int j = 0; j < help.length; j++){
            nums[left+j] = help[j];
        }
    }

逆序和  & 最小和都可以用归并排序的思路来解

逆序对

/**
 * 逆序对和最小和求解思路的区别
 *
 * 【最小和】是优先找小值
 * [1,1,2] [2,3,4]
 * 优先在左侧数组找到小值后  右边剩下的就都比该值要大了 从左向右遍历
 * 例如：对于左边第一个元素1 右边第一个元素2及2之后的所有元素都对1有一个小和
 * smallsum += 1 * (right-p2+1)
 * 即 如果左小于右 累加
 *
 * 【逆序对】要求是左侧元素大于右侧
 * 优先在左侧找大值 对于升序排序 大值在最右边 应该从右向左遍历
 * [1,1,5] [1,3,4]
 * 例如：对于左边最后一个元素5 大于右边最后一个元素4 则5可以和4及4之前的所有元素形成一个逆序对
 * [5,1][5,3][5,4]
 * count += right-(mid+1)+1  5 - 3 + 1 = 3 个
 * 即 如果左大于右 累加
 */
public class ReversePair {
    private static int count;
    private static List<int[]> list = new ArrayList<>();
    public static void mergeSort(int[] nums){
        if(nums ==null || nums.length < 2){
            return;
        }
        sortProcess(nums, 0, nums.length-1);
    }
    public static void sortProcess(int[] nums, int left, int right){
        if(left == right){//结束递归条件 这个范围只有一个数
            return;
        }
        int mid = left + (right - left)/2;
        sortProcess(nums,left,mid);//左边有序 T(N/2)
        sortProcess(nums,mid+1,right);//右边有序 T(N/2)
        merge(nums, left, mid, right);//外排序 O(N)
    }

    public static void merge(int[] nums, int left, int mid, int right){
        int[] helper = new int[right -left + 1];
        int p = right - left;
        int rightBegin = mid + 1;
        while(left <= mid && rightBegin <= right){
            if(nums[mid] > nums[right]){
                count += (right - rightBegin)+1;
                for(int k = right; k >= rightBegin; k--){
                    list.add(new int[] {nums[mid],nums[k]});
                }
                helper[p--] = nums[mid--];
            }else{
                helper[p--] = nums[right--];
            }
        }
        while(left <= mid){
            helper[p--] = nums[mid--];
        }
        while(right >= rightBegin){
            helper[p--] = nums[right--];
        }
        for(int help:helper){
            nums[left++] = help;
        }
    }

    public static void main(String[] args) {
        int[] nums = {3,5,4,2,1};
        mergeSort(nums);
        System.out.println(Arrays.toString(nums));
        System.out.println(count);
        for(int[] pair: list){
            System.out.println(Arrays.toString(pair));
        }
    }
}

最小和

public class SmallSum {
    public static int smallSum(int[] arr){
        if(arr == null|| arr.length < 2){
            return 0;
        }
        return mergeSort(arr,0,arr.length-1);
    }

    /**
     * 计算left ~ right范围内有多少小和
     */
    public static int mergeSort(int[] arr, int left, int right){
        if(left == right){
            return 0;
        }
        int mid = left + ((right - left) >> 1); //右移1位 等于 除以2
        //mid = left + (right - left)/2; 防止溢出
        return mergeSort(arr, left, mid)+//左边排序产生的小和
                mergeSort(arr, mid+1, right)+//右边排序产生的小和
                merge(arr, left, mid, right);//最后合并产生的小和
    }

    public static int merge(int[] arr, int left, int mid, int right){
        int[] help = new int[right-left+1];//准备一个临时数组
        // 长度和传进来的arr一样 是原arr的一部分 用left和right划分出来的一部分
        int i = 0;
        int p1= left;
        int p2 = mid+1;
        int res = 0;//计算小和
        while(p1 <= mid && p2 <= right){
            //关键在这里：
            // 每一次比较可以知道比当前值更大的值有几个，这个较小的当前值就需要累加多少次。
            //如果左边小于右边，那就有(r - p2 + 1)个arr[p1]元素的和是最小和，进行累加。
            //p2后面的个数 * p1指向的数
            res += arr[p1] < arr[p2] ? (right - p2 + 1) * arr[p1] : 0;
            help[i++] = arr[p1] > arr[p2] ? arr[p2++] : arr[p1++];
        }
        while(p1 <= mid){
            help[i++] = arr[p1++];
        }
        while (p2 <= right){
            help[i++] = arr[p2++];
        }
        for(i = 0; i < help.length; i++){
            arr[left+i] = help[i];
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {1,3,4,2,5};
        int i = smallSum(nums);
        System.out.println(i);
    }
}

堆排序

/**
 * HeapSort展示了heapinsert和heapify的两个过程
 * 时间复杂度是O(NlogN)
 * 实际上可以只用heapify
 * 用heapify代替heapinsert从后向前heapify
 * 原来的heapinsert是O(NlogN) heapify时间复杂度是O(N) 可以稍微快一点
 * 但最后的时间复杂度还是O(NlogN) 因为后面的操作还是O(NlogN)
 */
public class HeapSort {
    //堆化【调整堆】 某个数在index值 能否往下移动
    public static void heapify(int[] nums, int index, int heapSize){
        //index是初始的父节点
        int left = index * 2 + 1; //左孩子
        while(left < heapSize){//下方还有孩子时 没有越界
            int largest = left;
            if(left + 1 < heapSize) {//右孩子存在 没有越界
                //左右两孩子PK
                largest = nums[left]>nums[left+1]?left:left+1;
            }
            //较大孩子和父亲PK
            largest = nums[index]>nums[largest]?index:largest;
            //父亲最大不交换
            if(largest == index){
                break;
            }
            //父亲和较大孩子交换
            swap(nums, largest, index);
            //下一个比较的数 新父亲
            index = largest;
            //交换后的新的左孩子
            left = index * 2 + 1;
        }
    }

    /**
     * 无序数组 相当于依次插入大根堆 heapinsert
     * 得到大根堆后
     * 每次让数组第一个元素（最大值）和最后一个元素交换
     * 交换后heapsize--，调整堆heapify为大根堆
     * 最后heapsize == 0 数组有序
     */
    public static void heapSort(int[] nums){
        if(nums == null || nums.length < 2){
            return;
        }
        for (int i = nums.length-1; i >= 0; i--) {
            heapify(nums,i,nums.length);
        }
        int heapSize = nums.length;
        swap(nums,0,--heapSize);//先交换
        while(heapSize > 0){
            heapify(nums,0,heapSize);//再堆化
            swap(nums,0,--heapSize);//继续交换
        }
    }

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

    public static void main(String[] args) {
        int[] nums = {2,3,1,4,4,3,3,4,5,1};
        heapSort(nums);
        System.out.println(Arrays.toString(nums));
    }
}

适用于求基本有序的数列

* 已知一个几乎有序的数组，几乎有序是指，
 * 如果把数组排好顺序的话，每个元素移动的距离可以不超过K
 * 可以用堆排序来解决这个问题
 *
 * 思路：
 * 1.建立有K个元素的小顶堆，然后取出顶上元素
 * 2.堆顶用没有建堆的下一元素替代，重新建堆
 * 3.反复调用，完成排序，此算法因为每个元素移动都在k以内，所以时间复杂度为O(NlogK)
 */
public class KHeapSort {

    public static void kHeapSort(int[] nums, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        int index= 0;
        //k个值加入堆
        for(; index <= Math.min(k, nums.length); index++){
            heap.add(nums[index]);
        }
        int i = 0;
        //从index的下一个位置开始遍历 也就是k+1
        for(; index < nums.length; i++,index++){
            heap.add(nums[index]);//加一个 heapsize+1
            nums[i] = heap.poll();//弹一个 heapsize-1
        }
        while (!heap.isEmpty()){
            nums[i++] = heap.poll();
        }

    }

    public static void main(String[] args) {
        int [] nums ={3,2,7,1,8,6,4,5,12,10,15,9,13,14,11,20,16,17,18,19};
        kHeapSort(nums,7);
        System.out.println(Arrays.toString(nums));
    }
}

基数排序

public class RadixSort {
    /**
     * 统计最大值有多少位
     */
    public static int maxbits(int[] nums){
        int max = nums[0];
        for(int i = 0; i < nums.length; i++){
            max = Math.max(nums[i], max);
        }
        int count = 0;
        while(max > 0){
            max /= 10;
            count++;
        }
        return count;
    }
    /**
     * 获取倒数第i位的数字 i=1 取出个位
     */
    public static int getDigit(int num,int i){
        while(i > 1){
            num /= 10;
            i--;
        }
        return num%10;
    }

    /**
     * 基数排序
     */
    public static void radixSort(int[] arr){
        int digit = maxbits(arr);
        //基数 10
        final int radix = 10;
        //给每个数准备一个桶
        int[] buckets = new int[arr.length];
        //有多少位 就要出桶进桶几次
        for(int d = 1; d <= digit; d++){
            //计数器 等于count的有几个
            int[] count = new int[radix];
            for(int i = 0; i < arr.length; i++){
                int j = getDigit(arr[i],d);
                count[j]++;
            }
            //将count变为前缀和 小于等于count的有几个
            for(int i = 1; i < radix; i++){
                count[i] += count[i-1];
            }
            System.out.println(Arrays.toString(count));

            //数组从右向左遍历 入桶
            for(int i = arr.length-1; i >=0; i--){
                int j = getDigit(arr[i],d);
                buckets[count[j]-1] = arr[i];
                count[j]--;
            }

            //当前位数出桶
            for(int i = 0; i < arr.length; i++) {
                arr[i] = buckets[i];
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = {123,423,19,32,321,1200};
        radixSort(nums);
        System.out.println(Arrays.toString(nums));
    }
}