就这段代码，下面有3种简单的排序法：冒泡、选择、插入。
我的问题是，为什么冒泡排序和选择排序在对数组进行逆序排序的时候花的时间比对随机数组进行排序所花的时间少呢？
[code="java"]import java.util.Random;
public class ArrayUtil {
public static void bubbleSort(int[] array){
for(int i=0; i<array.length - 1; i++){
for(int j=0; j<array.length - i - 1; j++){
if(array[j]>array[j + 1]){
swap(array, j, j + 1);
}
}
}
}
public static void selectionSort(int[] array){
for(int i=0; i<array.length - 1; i++){
int minIndex = i;
for(int j=i; j<array.length - 1; j++){
if(array[j + 1] < array[minIndex]){
minIndex = j + 1;
}
}
swap(array, i, minIndex);
}
}
public static void insertionSort(int[] array){
for(int i=1; i<array.length; i++){
if(array[i]<array[i - 1]){
int temp = array[i];
int j = i - 1;
while(j>=0 && temp<array[j]){
array[j + 1] = array[j];
j--;
}
array[j + 1] = temp;
}
}
}
private static void swap(int[] array, int index1, int index2) {
int temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}
public static void main(String[] args){
int[] array = new int[10000];
generateRandomArray(array);
long b = System.currentTimeMillis();
ArrayUtil.bubbleSort(array);
long e = System.currentTimeMillis();
System.out.println("冒泡+随机:" + (e - b)/1000.0);
generateContradictoryArray(array);
b = System.currentTimeMillis();
ArrayUtil.bubbleSort(array);
e = System.currentTimeMillis();
System.out.println("冒泡+逆序:" + (e - b)/1000.0);
generateRandomArray(array);
b = System.currentTimeMillis();
ArrayUtil.selectionSort(array);
e = System.currentTimeMillis();
System.out.println("选择+随机:" + (e - b)/1000.0);
generateContradictoryArray(array);
b = System.currentTimeMillis();
ArrayUtil.selectionSort(array);
e = System.currentTimeMillis();
System.out.println("选择+逆序:" + (e - b)/1000.0);
generateRandomArray(array);
b = System.currentTimeMillis();
ArrayUtil.insertionSort(array);
e = System.currentTimeMillis();
System.out.println("插入+随机:" + (e - b)/1000.0);
generateContradictoryArray(array);
b = System.currentTimeMillis();
ArrayUtil.insertionSort(array);
e = System.currentTimeMillis();
System.out.println("插入+逆序:" + (e - b)/1000.0);
}
private static void generateContradictoryArray(int[] array) {
for(int i=0; i<array.length; i++){
array[i] = array.length - i;
}
}
private static void generateRandomArray(int[] array) {
Random random = new Random();
for(int i=0; i<array.length; i++){
array[i] = random.nextInt();
}
}
}
[/code]
还有，java.util.ArrayList源代码里ensureCapacity方法中这一句[code="java"]int newCapacity = (oldCapacity * 3)/2 + 1;[/code]为什么用这个*3/2+1？这是什么公式？有什么好处？
[b]问题补充：[/b]
[quote="mymGrubby"]这个是一个在增量处理的问题，有专家统计过1.5倍的增量方式是效率综合最高的。
增量的方式:
1.newCapacity = 所需要的值。
2.newCapacity = oldCapacity + 特定值。
3.newCapacity = oldCapacity * 倍数(>1)。
第一种 当前空间效率最好。但ArrayList变化时要频繁申请内存。
第二种 总体效率比第一种好，但没有第三种好。
第三种 倍数是关键，倍数太大，当前内存浪费过多，倍数太小要频繁申请内存。以前这个倍数大概是2，但数大量数据证明1.5是最好的倍数，再加1应该有更好的效率(oldCapacity 比较小的时候)。[/quote]
果然，在JDK1.1中，Vector的源代码是这样：
[code="java"] private void ensureCapacityHelper(int minCapacity) {
int oldCapacity = elementData.length;
Object oldData[] = elementData;
int newCapacity = (capacityIncrement > 0) ?
(oldCapacity + capacityIncrement) : (oldCapacity * 2);
if (newCapacity < minCapacity) {
newCapacity = minCapacity;
}
elementData = new Object[newCapacity];
System.arraycopy(oldData, 0, elementData, 0, elementCount);
}[/code]
谢谢[url="http://mymgrubby.iteye.com/"]mymGrubby[/url]
还有一个问题就是为什么冒泡排序和选择排序在对数组进行逆序排序的时候花的时间比对随机数组进行排序所花的时间少呢？
[b]问题补充：[/b]
[quote="xuyao"]我来回答一地问题，因为是随即数位数太多了，比较要比较高位，所以开销很大，这样没有可比性。你的逆序最大才1000，所以逆序快，建议生成同等位数的再试试。我反正试过了。[/quote]
首先谢谢你的回答。
我刚把generateRandomArray()方法给改了，改成这样：
[code="java"]private static void generateRandomArray(int[] array) {
Random random = new Random();
for(int i=0; i<array.length; ){
int item = random.nextInt(10000);
int j;
if(i==0) array[i]=item;
for(j=0; j<i; ){
if(array[j]==item) break;
j++;
}
if(j==i){
array[i] = item;
i++;
}
}
}[/code]
这样保证了生成的随机数组不包含重复的数字，并且是0到10000内的数字。但结果似乎仍然是老样子。
[quote="xuyao"]你的逆序最大才1000[/quote]array.length是10000，第一次循环，i=0，array.length - i应该是10000吧。 :)
[b]问题补充：[/b]
[quote="mymGrubby"]对冒泡排序和选择排序来说，逆序情况下比随机情况下swap操作要少很多。[/quote]
这个应该是不对的，冒泡排序逆序情况下每一步都要swap操作，是49995000次，随机的时候要少得多，比如我刚运行了一下，只swap了25152355次。而选择排序的swap操作在逆序情况下和随机情况下是一样的，都是9999次。
[b]问题补充：[/b]
[quote="RednaxelaFX"]主要还是因为冒泡排序中除了交换之外，寻找逆序对的额外消耗太大了，无法忽略。如果遍历整个数组只完成了一次交换，而这个数组的长度有很大，那么遍历的过程本身显然就有着无法忽略的开销。 [/quote]
可是似乎逆序的时候同样也要遍历相同次数，我并没有在哪个条件下改变i、j的增量，也没有在哪个条件下跳出某次循环。
寻找逆序对的操作同样存在于对逆序数组排序的整个过程中呀。是吧？ :)
