打开《Java语言程序设计与应用》_从基础向熟练进发_3.6.3 插入排序

【摘要】 本书摘自《Java语言程序设计与应用》一书中第3章，第6节，由徐俊武编著。

3.6.3 插入排序

基本思想：直接插入排序的基本操作是将一个记录插入已经排好的有序表 中，从而得到一个新的、记录数增1的有序表。对于给定的一组记录，初始时假 定第一个记录自成一个有序序列，其余记录为无序序列。接着从第二个记录开 始，按照记录的大小依次将当前处理的记录插入其之前的有序序列中，直到最后 一个记录插到有序序列中为止。

复杂度分析：最好的情况，也就是要排序的表本身就是有序的，此时只有数 据比较，没有数据移动，时间复杂度为 O(n)。 最坏的情况，即待排序的表是逆序 的情况，此时需要比较的次数为：2+3+ …+n=(n+2)(n-1)/2 次，而记录移 动的最大值也达到了 (n+4)(n-1)/2 次。如果排序记录是随机的，那么根据 概率相同的原则，平均比较和移动次数约为 n²/4 次，因此，得出直接插入排序法 的时间复杂度为 O(n²)。 从这里可以看出，同样的是时间复杂度 O(n²), 直接插 入排序法比冒泡和简单选择排序的性能要好一些。

排序过程如下：

以数组{38,65,97,76,13,27,49}为例

第一趟：[38]659776132749

第二趟：[3865]9776132749

第三趟：[386597]76132749

第四趟：[38657697]132749

第五趟：[1338657697]2749

第六趟：[132738657697]49第七趟：[13273849657697]

最后排序结果：

13273849657697

代码实现如下：

public class InsertSort {

public static void insertSort(int[] a){

int i,j,insertNote; //要插入的数据

for (i=1;i

//从数组的第二个元素开始循环将数组中的元素插入 insertNote=a[i];

//设置数组中的第2个元素为第一次循环要插入的数据

j=i- 1;

whij(>1 insertNote

//如果要插入的元素小于第 j 个元素，就将第 个元素向后移动

j--;

}

a[j+1]=insertNote;

//直到要插入的元素不小于第う个元素，将 insertNote 插入数组中

)

public static void main(String[] args){

int a[]={38,65,97,76,13,27,49};

insertSort(a);

System.out.println(Arrays,toString(a));

3.7 多 维 数 组

3.7.1 多维数组的定义

Java 中没有真正的多维数组，但因为数组元素可以说明为任何类型，所以 可以建立数组的数组(的数组……),由此得到多维数组。 一般来讲，n 维数组是n-1 维数组的数组。

以二维数组为例，来看多维数组的定义。二维数组的定义方式如下： type arrayName[][];

例如：

int intArray[][];

也可以采取另一种定义方式：

type[][] arrayname;

与一维数组一样，定义时对数组元素也没有分配内存空间，同样要使用运算 符new 来分配内存，然后才可以访问每个元素。

3.7.2 多维数组的初始化

与一维数组一样，多维数组的初始化也分为静态和动态两种。

静态初始化时，在定义数组的同时为数组分配空间。以二维数组为例，如下 所示：

int intArray[][]={{2,3},{1,2},{3,4}};

这里，不必指出数组每一维的大小，系统会根据初始化时给出的初始值的个 数自己算出数组每一维的大小。

最外层括号所含各元素是数组第一维的各元素，最内层括号对应数组最后 一维的元素。这里，数组 intArray为一个3行2列的数组，它的形式如下：

23

1.2

34

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们 [email protected] 处理，核实后本网站将在24小时内删除侵权内容。