java数组详解.docx

java数组详解(包括数据的初始化、比较、排序、重要方法）2012-12-21 09:08:54 我来说两句 作者：dannor2010 收藏 我要投稿一维数组声明方式：java type var 或 type var; 例子：int a , int a; Java中使用关键字new创建数组对象，格式为：数组名 = new 数组元素的类型 数组元素的个数例子： int s ; s = new int5 ; 或者也可以自己创建类java view plaincopyPeople p ； p = new people10; 代码：java public class Study / public static void main(String args) / int a = new int5; / People p; / p = new People10; / / / class People / / public static void main(String args) int a; a = new int5; for(int i=0; i 5; i +) ai = i; for(int i=0; i 5; i +) System.out.println(ai); 初始化：1.动态初始化：数组定义与为数组分配空间和赋值的操作分开进行；2.静态初始化：在定义数字的同时就为数组元素分配空间并赋值；3.默认初始化：数组是引用类型，它的元素相当于类的成员变量，因此数组分配空间后，每个元素也被按照成员变量的规则被隐士初始化。 1.动态初始化示例代码数组定义与为数组分配空间和赋值的操作分开进行；java public class Study public static void main(String args) int a = new int3; a0 = 1; a1 = 2; a2 = 3; Date d = new Date3; d0 = new Date(2008,4,5); d1 = new Date(2008,4,5); d2 = new Date(2008,4,5); class Date int year, month,day; public Date(int year, int month, int day) this.year = year; this.month = month; this.day = day; 2、静态代码示例在定义数字的同时就为数组元素分配空间并赋值；java public class Study public static void main(String args) Date d = new Date(2012, 12, 12),new Date(2012, 12, 12),new Date(2012, 12, 12); class Date int year, month,day; public Date(int year, int month, int day) this.year = year; this.month = month; this.day = day; 3、默认初始化数组是引用类型，它的元素相当于类的成员变量，因此数组分配空间后，每个元素也被按照成员变量的规则被隐士初始化。java public class Study public static void main(String args) int a = new int5; System.out.println( + a3); 二维数组的定义声明方式：java type arrayName; 例子：java int intArray; 如：java int a=2，3，1，5，3，4; 定义了一个32的数组，并对每个元素赋值。初始化：1.动态初始化：数组定义与为数组分配空间和赋值的操作分开进行；2.静态初始化：在定义数字的同时就为数组元素分配空间并赋值；3.默认初始化：数组是引用类型，它的元素相当于类的成员变量，因此数组分配空间后，每个元素也被按照成员变量的规则被隐士初始化。 二维数组初始化规则其实和一维数组一样，我就不多说了。写两个简单例子： 1、规则二维数组：java public class Study public static void main(String args) int a = 1, 2, 3, 4,5, 6; for(int i = 0; ia.length; i+) for(int j = 0; jai.length; j+) System.out.println(aij); 2、不规则二维数组：java public class Study public static void main(String args) int b = 1, 2, 3, 4, 5,5, 6, 7, 8; for(int i = 0; ib.length; i+) for(int j = 0; jbi.length; j+) System.out.println(bij); 数组排序JAVA中在运用数组进行排序功能时，一般有四种方法：快速排序法、冒泡法、选择排序法、插入排序法。1、利用Arrays带有的排序方法快速排序该排序算法是一个经过调优的快速排序法，改编自 Jon L. Bentley 和 M. Douglas McIlroy 合著的 Engineering a Sort Function, Software-Practice and Experience Vol. 23(11) P. 1249-1265 (November 1993)。此算法在许多数据集上提供 n*log(n) 性能，这导致其他快速排序会降低二次型性能。public static void sort(int a, int fromIndex, int toIndex)对指定 int 型数组的指定范围按数字升序进行排序。排序的范围从索引 fromIndex（包括）一直到索引 toIndex（不包括）。java public class Study public static void main(String args) int a = 5, 4, 2, 4, 9, 1 ; Arrays.sort(a); for (int i : a) System.out.println(i); 2、冒泡排序冒泡排序：它的时间复杂度为O（n2），虽然不及堆排序、快速排序的O（nlogn，底数为2），但是有两个优点：1.“编程复杂度”很低，很容易写出代码；2.具有稳定性，这里的稳定性是指原序列中相同元素的相对顺序仍然保持到排序后的序列，而堆排序、快速排序均不具有稳定性。不过，一路、二路归并排序、不平衡二叉树排序的速度均比冒泡排序快，且具有稳定性，但速度不及堆排序、快速排序。基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。java import java.util.Arrays; public class Study public static void main(String args) int a = 5, 4, 2, 4, 9, 1 ; bubbleSort(a); for (int i : a) System.out.println(i); public static int bubbleSort(int a) for (int i = 0; i a.length - 1; i+) for (int j = i + 1; j aj) int temp; temp = aj; aj = ai; ai = temp; return a; 3、选择排序算法我们主要介绍简单选择排序、树型选择排序和堆排序。简单排序：在简单选择排序过程中，所需移动记录的次数比较少。最好情况下，即待排序记录初始状态就已经是正序排列了，则不需要移动记录。最坏情况下，即待排序记录初始状态是按逆序排列的，则需要移动记录的次数最多为3（n-1）。简单选择过程中需要进行的比较次数与初始状态下待排序的记录序列的排列情况无关。当i=1时，需进行n-1次比较；当i=2时，需进行n-2次比较；依次类推，共需要进行的比较次数是 =(n-1)+(n-2)+2+1=n(n-1)/2，即进行比较操作的时间复杂度为O(n2)。这种方法其实是对冒泡排序的深入。java public class Study public static void main(String args) int a = 5, 4, 2, 4, 9, 1 ; selectSort(a); for (int i : a) System.out.println(i); public static int selectSort(int args) for (int i = 0; i args.length - 1; i+) int min = i; for (int j = i + 1; j argsj) min = j; if (min != i) int temp = argsi; argsi = argsmin; argsmin = temp; return args; 4、插入排序算法包括：直接插入排序，二分插入排序（又称折半插入排序），链表插入排序，希尔排序（又称缩小增量排序）。 直接插入排序：java public class Study public static void main(String args) int a = 5, 4, 2, 4, 9, 1 ; insertSort(a); for (int i : a) System.out.println(i); public static int insertSort(int args) / 插入排序算法 for (int i = 1; i 0; j-) if (argsj argsj - 1) int temp = argsj - 1; argsj - 1 = argsj; argsj = temp; else break; return args; 折半插入排序折半插入排序（binary insertion sort）是对插入排序算法的一种改进，由于排序算法过程中，就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度。在将一个新元素插入已排好序的数组的过程中，寻找插入点时，将待插入区域的首元素设置为alow，末元素设置为ahigh，则轮比较时将待插入元素与am，其中m=(low+high)/2相比较,如果比参考元素小，则选择alow到am-1为新的插入区域(即high=m-1)，否则选择am+1到ahigh为新的插入区域（即low=m+1），如此直至low=high不成立，将此位置之后所有元素后移一位，并将新元素插入ahigh+1。折半插入排序算法是一种稳定的排序算法，比直接插入算法明显减少了关键字之间比较的次数，因此速度比直接插入排序算法快，但记录移动的次数没有变，所以折半插入排序算法的时间复杂度仍然为O(n2)，与直接插入排序算法相同。java public class Study public static void main(String args) int a = 5, 4, 2, 4, 9, 1 ; halfInsert(a); for (int i : a) System.out.println(i); public static int halfInsert(int R) for (int i = 1; i R.length; i+) / 从第二个元素开始，需要做n-1趟插入排序，第一个元素自成有序区 int temp = Ri;/ 暂存 int low = 0;/ 定义从第一个元素开始为有序区 int high = i - 1;/ 有序区的元素从一个开始逐渐增加 / low和high分别指向有序区中的第一个和最后一个元素 while (low = high) / 寻找在有序区中插入的位置，最后使highlow，就找到插入的位置 / 为high+1；也是low的位置 int m = (low + high) / 2;/ 有序区的中间元素 if (temp low; j-) / 把从low开始以后或high+1以后的元素向后移动，插入 Rj = Rj - 1;/ 移动元素 Rlow = temp;/ 插入在合适的位置 return R; 二分查找：二分查找原理很容易懂，想象为二叉查找树就明白了。java int binarySearch(int a, int value) int low = 0; int high = a.length-1; while(low value) high = mid-1; else low = mid +1; return -1; 5、快速排序算法通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分关键字小，则分别对这两部分继续进行排序，直到整个序列有序。 java void quickSort(int a, int low, int high) p = get(a, low, high); quickSort(a, low, p-1); quickSort(a, p+1, high); int get(int a, int low, int high) compare = alow; while(low high) /无论如何置换, 被置换的都包含compare的值 while(low=compare) high-; /在 lowhigh 的情况下找到ahighcompare并置换 temp = alow; alow = ahigh; ahigh = temp; while(lowhigh & alow=compare) low+; /在 lowcompare并置换 temp = alow; alow = ahigh; ahigh = temp; return low; /while(low=hight)停止循环, 并返回枢轴位置 数组重要方法一、填充数组：Arrays.fill()方法 缺点：填充的数据单一。用法1：接受2个参数Arrays.fill（ a1, value ）;注：a1是一个数组变量，value是一个a1中元素数据类型的值，作用：填充a1数组中的每个元素都是value例如：java public class Study public static void main(String args) int a = new int5; Arrays.fill(a, 1); for (int i : a) System.out.println(i); 输出结果为：java 1 用法2：接受4个参数第一个参数指操作的数组，第二个和第三个指在该数组的某个区域插入第四个参数，第二个参数指起始元素下标（包含该下标），第三个参数指结束下标（不包含该下标），注意：java的数组下标从0开始例如：java public class Study public static void main(String args) int a = new int5; Arrays.fill(a, 1); Arrays.fill(a, 1, 3, 2); for (int i : a) System.out.println(i); 结果：java 1 二、复制数组：clone()方法 clone（）方法，限制：全部复制，无法部分的复制。java public class Study public static void main(String args) int a = new int5; int b; Arrays.fill(a, 1); b = a.clone(); for (int i : b) System.out.println(i); 结果：java 三、比较数组：Arrays.equala()方法 comparable接口：compareTo()方法 ， 实现comparable接口的类有了自身的比较功能 comparator接口：compare()方法和equals()方法 一般只需实现compare()方法 用于编写自定义的比较方法 例子：定义Person类，对该类进行比较java public class Person String firstname, lastname; Boolean sex; int age; public Person(String firstname, String lastname, Boolean sex, Integer age) super(); this.firstname = firstname; this.lastname = lastname; this.sex = sex; this.age = age; public String getFirstname() return firstname; public void setFirstname(String firstname) this.firstname = firstname; public String getLastname() return lastname; public void setLastname(String lastname) this.lastname = lastname; public Boolean getSex() return sex; public void setSex(Boolean sex) this.sex = sex; public Integer getAge() return age; public void setAge(Integer age) this.age = age; 实现Comparator，定义自定义比较器import java.util.Comparator;public class PersonComparator implements Comparator Overridepublic int compare(Person arg0, Person arg1) if (arg0.getAge() arg1.getAge() return -1;return 1;测试比较器java public class Study public static void main(String args) Person p = new Person(ouyang, feng, Boolean.TRUE, 27), new