首页 > 其他分享 >插入排序

插入排序

时间:2022-10-29 14:25:09浏览次数:62  
标签:arr return int 插入排序 length arr2 arr1

package class01;

import java.util.Arrays;

/**
 * 插入排序
 * 概述:先将i指向第二个数(索引为1),将j指向i-1位置,如果j大于等于0,并且arr[j]>arr[j+1],将将arr[j]和arr[j+1]交换。j--。
 */
public class Code03_InsertSort {
    public static void insertSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 1; i < arr.length; i++) {//i直接从索引为1的位置,即第二个数字开始。
            for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
                swap(arr, j, j + 1);
            }
        }
    }

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

    public static void printArr(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    public static int[] generateRandomArr(int maxSize, int maxValue) {
        int[] arr = new int[(int) (Math.random() * maxSize)];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * maxValue);
        }
        return arr;
    }

    public static int[] copyArr(int[] arr1) {
        int[] arr2 = new int[arr1.length];
        for (int i = 0; i < arr1.length; i++) {
            arr2[i] = arr1[i];
        }
        return arr2;
    }

    public static void main(String[] args) {
        int maxSize = 10;
        int maxValue = 100;
        int testTimes = 10;
        boolean flag = true;
        for (int i = 0; i < testTimes; i++) {
            int[] arr1 = generateRandomArr(maxSize, maxValue);
            int[] arr2 = copyArr(arr1);
            int[] arr3 = copyArr(arr1);
            Arrays.sort(arr2);
            insertSort(arr1);
            if (!isEquals(arr1, arr2)) {
                flag = false;
                System.out.println("oops!");
                System.out.println("arr1 = " + Arrays.toString(arr1));//自己实现的冒泡排序。
                System.out.println("arr2 = " + Arrays.toString(arr2));//工具类排好序的。
                System.out.println("arr3 = " + Arrays.toString(arr3));//原数组,还没有排序。
                break;
            }
        }
        System.out.println(flag ? "nice!" : "oops!");
        int[] arr = generateRandomArr(maxSize, maxValue);
        printArr(arr);
        insertSort(arr);
        printArr(arr);
    }

    private static boolean isEquals(int[] arr1, int[] arr2) {
        if (arr1 == null && arr2 != null) {
            return false;
        }
        if (arr2 == null && arr1 != null) {
            return false;
        }
        if (arr1 == null && arr2 == null) {
            return true;
        }
        if (arr1.length != arr2.length) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }
}

 

标签:arr,return,int,插入排序,length,arr2,arr1
From: https://www.cnblogs.com/TheFloorIsNotTooHot/p/16838635.html

相关文章

  • 插入排序
    插入排序一、概念及其介绍插入排序(InsertionSort),一般也被称为直接插入排序。对于少量元素的排序,它是一个有效的算法。插入排序是一种最简单的排序方法,它的基本思想是......
  • java插入排序
    如何才能插入排序描?如何才能插入排序描述思路假定这个数组的序是排好的,然后从头往后,如果有数比当前外层元素的值大,则将这个数的位置往后挪,直到当前外层元素的值大于或等于它......
  • 数据结构【c语言版】八大算法(上)图文详解带你快速掌握——希尔排序,堆排序,插入排序,选择
    数据结构之八大算法详解(1)——希尔排序,堆排序,插入排序,选择排序,冒泡排序!插入排序基本思想把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所......
  • C#:插入排序
    对于给定的一组记录,初始时假设第一个记录自成一个有序序列,其余的记录为无序序列。接着从第二个记录开始,按照记录的大小依次将当前处理的记录插入到其之前的有序序列中,直至......
  • 3、插入排序-Go语言版
    前情提示Go语言学习者,文章若有不妥之处,感谢指正。本文参考:https://www.runoob.com/w3cnote/ten-sorting-algorithm.html为了便于下载和整理,已开源放在:https://github......
  • 插入排序
    插入排序的原理:将指针指向某元素(一般从第二个元素开始),假设该元素的左侧全部有序,将该元素抽取,然后按照从右往左的顺序分别与其左边的元素进行比较,遇到较大的元素便将较大的......
  • JavaScript 实现 -- 插入排序
    前言本文主要记录了JavaScript实现--插入排序,以及原理、时间复杂度、空间复杂度和算法稳定性。插入排序插入排序,一般也被称为直接插入排序。对于少量元素的排序,它是一......
  • 插入排序算法步骤和思路
    算法步骤将待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列。从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置......
  • 003 插入排序
    //插入排序从左扩大范围最小值放在最右边publicstaticvoidinsertionSort(int[]arr){if(arr==null||arr.length<2){return;......
  • 选择排序、冒泡排序、插入排序、快速排序
    排序选择排序以数组a[8]={12,23,8,15,33,24,77,55}为例WHILE(notsortedyet)findsmallestunsorteditemSwapfirstunsorteditemwiththesmallests......