当前位置：首页 > article >正文

数据结构：排序—插入排序（一）

article 2025/2/7 21:44:52

一、排序

1、概念

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的，否则称为不稳定的。

我们来看下面这个图想必大家会更加的理解

内部排序：数据元素全部放在内存中的排序。

外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不断的在内外存之间移动数据的排序。

2、常见的排序算法

排序算法共有四大类七种排序算法：

二、插入排序

1、直接插入排序

直接插入排序是一种简单的插入排序法。

基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。

直接插入排序实现：

基本思路：我们先把我们要排序的值放到一个临时变量当中，让这个临时变量的值与他前面已经排好的数值依次进行比较，如果小于前面的值，就让前面的值覆盖他后一位的值，直到走完或者遇到不临时变量的值还小的数停止，并让停止后位置的后一位的值为临时变量的值

public static void insertSort(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            int tmp = arr[i];
            int j = i-1;
            for (; j >= 0; j--) {
                if(arr[j] > tmp){
                    arr[j+1] = arr[j];
                }else{
                    break;
                }
            }
            arr[j+1] = tmp;
        }
    }

2、希尔排序

希尔排序法又称缩小增量法。

基本思想是：先选定一个整数gap，把待排序文件中所有数据分成多个组，所有距离为gap的数据分在同一组内，并对每一组内的数据进行排序。然后，重复上述分组和排序的工作。当gap=1时，所有数据在统一组内排好序。

希尔排序实现：

基本思路：首先不管我们如何进行分组，当我们到最后一组的时候我们依然会进行插入排序，而此时我们在分成每一组的时候，我们都会进行插入排序，当我们变成最后一组数据的时候，我们发现此时的数据已经比较有序列，此时在进行插入排序，我们的排序速度就会更快。

首先我先将他进行分组，组中数据距离为此时所有数据总长的一半，然后我们进行插入排序，在进行直接插入排序时我们的 i 是从 1 下标开始，而此时我们的 i 下标要从gap处开始，j下标就要从i-gap开始，并且每比较依次我们的 j 下标就减去一个gap。当这个组排完序后，我们再以此时gap的一半进行分组不断重复上面的操作，直到gap=1,并排完序后。

public static void  shellSort(int[] arr){
        int gap = arr.length/2;
        while (gap > 0){
            shell(arr,gap);
            gap /=2;
        }
    }

    public static void shell(int[] arr,int gap){
        for (int i = gap; i < arr.length; i++) {
            int tmp = arr[i];
            int j = i-gap;
            for (; j >= 0 ; j-=gap) {
                if(arr[j] > tmp){
                    arr[j+gap] = arr[j];
                }else{
                    break;
                }
            }
            arr[j+gap] = tmp;
        }
    }