乐趣区

关于算法-数据结构:算法笔记三插入排序

算法背景

在之前,咱们探讨了冒泡排序,其算法外围,就是:相邻两数顺次比拟 ,让较大的值缓缓 浮出 水面,达到其适合的地位,使数组变得有序。也能够说,冒泡排序就是 顺次从高到低确认元素的地位。在工夫复杂度上为稳固的 O(n²)

抉择排序也是一种稳固的 O(n²)排序办法,其算法的外围,就是:第一次从待排序的数据元素中选出 最小(或最大)的一个元素 ,寄存在序列的起始地位,而后再从 残余的未排序元素中寻找 到最小(大)元素,而后放到已排序的序列的开端

以上两种算法的局限在于,疏忽了原有数组,在某个片段内,是否是有序的,例如 int[] arr = {0,1,2,3,5,4,3}, 在这个进行排序过程中,前 3 项在某个时刻曾经变得有序,无需再进行关注。

上面咱们来看一下 插入排序

插入排序,个别也被称为间接插入排序。对于大量元素的排序,它是一个无效的算法。插入排序是一种最简略的排序办法,它的根本思维是将一个记录插入到曾经排好序的有序表中,从而一个新的、记录数增 1 的有序表。在其实现过程应用双层循环,外层循环对除了第一个元素之外的所有元素,内层循环对以后元素后面有序表进行待插入地位查找,并进行挪动。——百度百科

算法思维

插入排序的工作形式像许多人排序一手扑克牌。开始时,咱们的左手为空并且桌子上的牌面向下。而后,咱们每次从桌子上拿走一张牌并将它插入左手中正确的地位。为了找到一张牌的正确地位,咱们从右到左将它与已在手中的每张牌进行比拟。拿在左手上的牌总是排序好的,原来这些牌是桌子上牌堆中顶部的牌。

插入排序是指在待排序的元素中,假如后面 n -1(其中 n >=2)个数曾经是排好程序的,现将第 n 个数插到后面曾经排好的序列中,而后找到适合本人的地位,使得插入第 n 个数的这个序列也是排好程序的。依照此法对所有元素进行插入,直到整个序列排为有序的过程,称为插入排序。

图解算法

两层循环,咱们首先保障 0 - i 是有序的,而后再拿到数组中的第 i + 1 个元素,从后往前插入到 0 - i 中适合的地位,此时 0 -i+ 1 也有序了,再拿到第 0 -i+ 2 个元素,插入到 0 -i+ 1 中适合的地位。始终到 0 - n 全副有序。

JAVA 代码

第一种:

public static void insertSorting(int[] arr){for (int i = 1 ; i < arr.length; i++) {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];
    }

以上实现,将插入到适合地位进行替换的条件和 for 循环是否持续,做了合并。第二种实现形式不合并。

第二种:

public static void insertSorting(int[] arr){for (int i = 1 ; i < arr.length; i++) {for (int j = i-1; j >= 0; j--) {if (arr[j]>arr[j+1]) swap(arr,j,j+1);
                else break;
            }
        }
    }
    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];
    }

两种代码的执行是一样的,只是写法不同。第二种代码的 else break;是必须加的,要不然工夫上就会减少,违反了插入排序的思维。

算法 最好工夫 最坏工夫 均匀工夫 额定空间
插入 O(n) O(n²) O(n²) 0/1

在排序算法中,咱们个别都要关注最坏工夫复杂度,咱们能够看到,抉择排序、冒泡排序、插入排序的最坏工夫复杂度都是 O(n²)。

退出移动版