栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

排序之——直接插入排序、归并排序(优化)、快速排序(优化)

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

排序之——直接插入排序、归并排序(优化)、快速排序(优化)

排序之——直接插入排序

适用场景——短数组或大部分有序情况,最好情况下可以达到O(N)的复杂度。

时间复杂度:O(N^2)

代码如下:

 public static int[] sortArray(int[] nums) {
        int len = nums.length;
        // 循环不变量:将 nums[i] 插入到区间 [0, i) 使之成为有序数组
        for (int i = 1; i < len; i++) {
            // 先暂存这个元素
            int temp = nums[j];
            int j = i;
            // 注意边界 j > 0
            //将前面大的值往后挪
            while (j > 0 && nums[j - 1] > temp) {
                nums[j] = nums[j - 1];
                j--;
            }
            nums[j] = temp;
        }
        return nums;
    }

排序之——归并排序(有优化)

基本思路:借助额外空间,合并两个有序数组,得到更长的有序数组。

//归并排序
public class Main {
    //当列表长度小于等于7时,定义为短数组,采用插入排序
    private static final int INSERTION_SORT_THRESHOLD = 7;

    public static int[] sortArray(int[] nums) {
        int len = nums.length;
        int[] temp = new int[len];
        mergeSort(nums, 0, len - 1, temp);
        return nums;
    }

    
    private static void mergeSort(int[] nums, int left, int right, int[] temp) {
        // 小区间使用插入排序(优化一)
        if (right - left <= INSERTION_SORT_THRESHOLD) {
            insertionSort(nums, left, right);
            return;
        }

        int mid = (left + right) >> 1;
        //int mid = left + (right - left) / 2;

        mergeSort(nums, left, mid, temp);           //[left,mid]
        mergeSort(nums, mid + 1, right, temp);  //[mid + 1,right]

        // 如果数组的这个子区间本身有序,无需合并(优化二)
        if (nums[mid] <= nums[mid + 1]) {
            return;
        }
        mergeOfTwoSortedArray(nums, left, mid, right, temp);
    }
    
    private static void mergeOfTwoSortedArray(int[] nums, int left, int mid, int right, int[] temp) {
//        Object src : 原数组              ——nums
//        int srcPos : 从元数据的起始位置开始 ——left
//        Object dest : 目标数组            ——temp
//        int destPos : 目标数组的开始起始位置 ——left
//        int length : 要copy的数组的长度     ——right - left + 1
        //复制数组
       System.arraycopy(nums,left,temp,left,right - left + 1);

       int i = left;
       int j = mid + 1;

       for (int k = left;k<=right;k++){
           if (i == mid + 1){//[left,mid]有序数组遍历完
               nums[k] = temp[j];
               j++;
           }
           else if (j == right + 1){//[mid + 1,right]有序数组遍历完
               nums[k] = temp[i];
               i++;
           }
           else if (temp[i] <= temp[j]){//前一个数组索引位置小
               nums[k] = temp[i];
               i++;
           }
           else{
               //temp[i] > temp[j]
               nums[k] = temp[j];
               j++;
           }
       }
    }
    
    private static void insertionSort(int[] arr, int left, int right) {
        for (int i = left + 1; i <= right; i++) {
            int j = i;
            int temp = arr[j];
            while (j > left && arr[j - 1] > temp) {
                arr[j] = arr[j - 1];
                j--;
            }
            arr[j] = temp;
        }
    }
}

排序之——快速排序(已优化)

基本思路:快速排序每一次都排定一个元素(这个元素呆在了它最终应该呆的位置),然后递归地去排它左边的部分和右边的部分,依次进行下去,直到数组有序;

算法思想:分而治之(分治思想),与「归并排序」不同,「快速排序」在「分」这件事情上不像「归并排序」无脑地一分为二,而是采用了 partition 的方法,因此就没有「合」的过程。

实现细节(注意事项):(针对特殊测试用例:顺序数组或者逆序数组)一定要随机化选择切分元素(pivot),否则在输入数组是有序数组或者是逆序数组的时候,快速排序会变得非常慢(等同于冒泡排序或者「选择排序」);

import java.util.Random;
//快速排序
public class Main {
    //当列表长度小于等于7时,定义为短数组,采用插入排序
    private static final int INSERTION_SORT_THRESHOLD = 7;

    private static final Random RANDOM = new Random();


    public static int[] sortArray(int[] nums) {
        int len = nums.length;
        quickSort(nums, 0, len - 1);
        return nums;
    }

    private static void quickSort(int[] nums, int left, int right) {
        // 小区间使用插入排序
        if (right - left <= INSERTION_SORT_THRESHOLD) {
            insertionSort(nums, left, right);
            return;
        }

        int pIndex = partition(nums, left, right);//这个元素呆在了它最终应该呆的位置
        quickSort(nums, left, pIndex - 1); //递归左边部分
        quickSort(nums, pIndex + 1, right);//递归右边部分
    }

    private static int partition(int[] nums, int left, int right) {
        int randomIndex = RANDOM.nextInt(right - left + 1) + left;
        swap(nums, left, randomIndex);

        // 基准值
        int pivot = nums[left];
        int lt = left;

        // 循环不变量:
        // all in [left + 1, lt] < pivot
        // all in [lt + 1, right) >= pivot
        for (int i = left + 1; i <= right; i++) {
            if (nums[i] < pivot) {
                lt++;
                swap(nums, i, lt);
            }
        }
        swap(nums, left, lt);
        return lt;
    }

    //交换函数
    private static void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
    
    private static void insertionSort(int[] nums, int left, int right) {
        for (int i = left + 1; i <= right; i++) {
            int j = i;
            int temp = nums[j];
            while (j > left && nums[j - 1] > temp) {
                nums[j] = nums[j - 1];
                j--;
            }
            nums[j] = temp;
        }
    }
}

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/938896.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号