java数组详解(包括数据的初始化、比较、排序、重要方法）(二)
(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（n^2），虽然不及堆排序、快速排序的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 < a.length; j++) {
if(a[i] > a[j]){
int temp;
temp = a[j];
a[j] = a[i];
a[i] = 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 < args.length; j++) {
if (args[min] > args[j]) {
min = j;
}
}
if (min != i) {
int temp = args[i];
args[i] = args[min];
args[min] = 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 < args.length; i++) {
for (int j = i; j > 0; j--) {
if (args[j] < args[j - 1]) {
int temp = args[j - 1];
args[j - 1] = args[j];
args[j] = temp;
} else
break;
}
}
return args;
}
}
折半插入排序
折半插入排序（binary insertion sort）是对插入排序算法的一种改进，由于排序算法过程中，就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度。
在将一个新元素插入已排好序的数组的过程中，寻找插入点时，将待插入区域的首元素设置为a[low]，末元素设置为a[high]，则轮比较时将待插入元素与a[m]，其中m=(low+high)/2相比较,如果比参考元素小，则选择a