java数组的总结
数组总结
?
数组的声明：
类型?[]?数组名?或?类型?数组名[]?
声明数组时不能指定其长度。
数组的创建：
Java中使用关键字new创建数组对象，格式为：
数组名?=?new?数组元素的类型?[数组元素的个数]
数组的结构：
在内存中的空间是线性的。其传递为引用传递，即传首地址。一旦创建数组，数组大小便不可改变。length属性表示其大小。
?
【数组排序】
稳定算法：冒泡排序、插入排序、归并排序和基数排序。
不稳定算法：选择排序、快速排序、希尔排序、堆排序。
?
稳定性的概念（摘自百度百科）：
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。
即判断排序后原来相同元素的先后顺序是否发生改变，若是，则不稳定。
?
冒泡排序：
??? 比较相邻两个元素的大小，将较小的元素向前调整。若相邻元素相同，则不需要调整，故先后顺序不会改变。故为稳定算法。
例：
4? 3? 5? 4# 6
3? 4? 5? 4# 6
3? 4? 5? 4# 6
3? 4? 4#?5? 6
3? 4? 4#?5? 6
3? 4? 4#?5? 6
?
选择排序：
??? 依次给每个位置选择最小元素，交换对应位置的元素。
例：?
5???5#??2??1??
1???5#??2??5??
1???2???5#?5??
可看出5和5#的位置发生了变化。故是不稳定算法。
?
插入排序：
????是在一个已经有序的小序列的基础上，一次插入一个元素。只有第一个元素，就是第一个元素。想要插入的元素和已经有序的最大者开始比。
例：（|之前为有序，|后一个为要插入的元素）
2|?5??4??9??8??1??5#?
2??5|?4??9??8??1??5#
2??4??5|?9??8??1??5#
2??4??5??9|?8??1??5#
2??4??5??8??9|?1??5#
1??2??4??5??8??9|?5#
1??2??4??5??5#?8??9|
对于两个相同元素，后一个元素在插入时，从有序序列末位开始往前比较，当遇到相同元素后停止，并不交换顺序（仍在后面）。故为稳定的。?
?
希尔排序：
??? 将整个序列分成若干子序列，分别进行插入排序。实际上是分组插入。虽然插入排序是稳定的，但在不同组别的排序过程中，相同的元素可能发生交叉，稳定性就会被打乱，所以希尔排序是不稳定的。?
例：
?49??38??65??97??76??13??27??49#?55??04??（初始）
?13??27??49#?55??04??49??38??65??97??76??（步长为5）
?13??04??49#?38??27??49??55??65??97??76??（步长为3）
?04??13??27??38??49#?49??55??65??97??76??（步长为1）
可看出两个49的相对顺序变了。?
?
?
附：上述四种排序算法的源代码
/** * 对给定一维数组做冒泡排序 * @param arrayOne 需要排序的数组 * @return 经过排序的数组 */public int[] paixu_maopao(int [] arrayOne) {for (int i = 0; i < arrayOne.length; i++) {for (int j = i+1; j <arrayOne.length; j++) {if(arrayOne[i]>arrayOne[j]){int temp=arrayOne[j];arrayOne[j]=arrayOne[i];arrayOne[i]=temp;}printArrayOne(arrayOne);}}return arrayOne;}/** * 对给定一维数组做选择排序 * @param arrayOne 需要排序的数组 * @return 经过排序的数组 */public int[] paixu_xuanze(int [] arrayOne) {for (int i = 0; i < arrayOne.length; i++) {int low=i;for (int j = i+1; j < arrayOne.length; j++) {if(arrayOne[j]<arrayOne[low]){low=j;}//printArrayOne(arrayOne);}int temp=arrayOne[i];arrayOne[i]=arrayOne[low];arrayOne[low]=temp;}return arrayOne;}/** * 对给定一维数组做插入排序 * @param arrayOne 需要排序的数组 * @return 经过排序的数组 */private int[] paixu_charu(int [] arr) {for (int i = 1; i < arr.length; i++) {for (int j = i; j > 0; j--) {if(arr[j-1]>arr[j]){int temp=arr[j];arr[j]=arr[j-1];arr[j-1]=temp;}}}return arr; }/** * 对给定一维数组做希尔排序 * @param arrayOne 需要排序的数组 * @return 经过排序的数组 */private int [] paixu_xier(int [] arr) {for(int inc=arr.length/2; inc>0;inc/=2){for (int i = inc; i < arr.length; i++) {int temp = arr[i];int j=0;for (j = i ;j >= inc; j-=inc) {if(temp < arr[j-inc]){arr[j]=arr[j-inc];}else{break;}}arr[j]=temp;}}return arr;}?
<!--EndFragment-->