就这段代码，下面有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的增量，也没有在哪个条件下跳出某次循环。
寻找逆序对的操作同样存在于对逆序数组排序的整个过程中呀。是吧？ :)
稍微总结一下:
JVM一定是有优化 才造成冒泡的逆序反而快了 这一点毫无疑问 这个优化不是系统的 而是JVM的 因为在.net上结果是合理的
交换的时候的位数对交换没有影响 都是32位int类型 你看到的位数多少是没有意义的 所以是等价的
这个是一个在增量处理的问题，有专家统计过1.5倍的增量方式是效率综合最高的。
增量的方式:
1.newCapacity = 所需要的值。
2.newCapacity = oldCapacity + 特定值。
3.newCapacity = oldCapacity * 倍数(>1)。
第一种 当前空间效率最好。但ArrayList变化时要频繁申请内存。
第二种 总体效率比第一种好，但没有第三种好。
第三种 倍数是关键，倍数太大，当前内存浪费过多，倍数太小要频繁申请内存。以前这个倍数大概是2，但数大量数据证明1.5是最好的倍数，再加1应该有更好的效率(oldCapacity 比较小的时候)。
晕，回答的是第二个问题
我来回答一地问题，因为是随即数位数太多了，比较要比较高位，所以开销很大，这样没有可比性。你的逆序最大才1000，所以逆序快，建议生成同等位数的再试试。我反正试过了。
第一个问题是应为整个排序算法中消耗时间资源的操作是：
[code="java"]swap(int[] array, int index1, int index2)[/code]
对冒泡排序和选择排序来说，逆序情况下比随机情况下swap操作要少很多。
to:mymGrubby,大哥，“对冒泡排序和选择排序来说，逆序情况下比随机情况下swap操作要少很多”搞笑呢吧，逆序的swap是最多的，要把第一个放到交换的最后面，我上面已经说了，是位数的关系。lz，你随即出来的是什么你看了吗？int是几位的？能和1000一下的比吗？不慢才怪
TO:xuyao
请解释一下为什么逆序下选择的排序时间比插入快
to mymGrubby，选择排序，我跑的是一样的。不知道你跑过没有
排序的本质就是消除逆序对。
例如说按升序排列[3, 2, 1]的话，那么逆序对就有：
(3, 2)
(3, 1)
(2, 1)
这三对。
以冒泡为例来看。冒泡排序的本质是每次遇到位置相邻的逆序对时就做一次交换，并保证每一次交换只解决一对逆序对。
回到上面[3, 2, 1]的例子，冒泡的
第一轮：
(3, 2) -> [2, 3, 1] // (2, 1), (3, 1)
(3, 1) -> [2, 1, 3] // (2, 1)
第二轮：
(2, 1) -> [1, 2, 3] // done
那么，不考虑输入中有重复的情况，逆序的输入中含有的逆序对应该是最多的。假设输入长度为n，则逆序对的个数为C(n, 2)（n个元素取2个的组合）。既然如此，在对逆序输入做排序时，冒泡排序要做的swap次数也是C(n, 2)次，也是所有输入可能中最多的。想想看，如果不是正好逆序，那么从长度为n的输入中任意取2个元素，必然有至少有一组不是逆序对。
那么为什么在对随机输入排序的时候反而比较慢？主要还是因为冒泡排序中除了交换之外，寻找逆序对的额外消耗太大了，无法忽略。如果遍历整个数组只完成了一次交换，而这个数组的长度有很大，那么遍历的过程本身显然就有着无法忽略的开销。
正好我这边有些对比表图可以看看：[url]http://rednaxelafx.iteye.com/blog/174063[/url]
晕哦，冒泡逆序搞错了
选择逆序时swap事实只有length/2
比如
选择逆序 4，3，2，1
第一次4和1交换：1，3，2，4
第二次是3和2交换：1,2,3,4
比较还有但交换没有了
后面的交换是自身的交换，应该比较快，或者jvm做了优化？
[code="java"]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;
}
}
if(i != minIndex){
swap(array, i, minIndex);
}
}
}[/code]
冒泡真不知道了，难道jvm对刚变动的数据做了缓存。。。
冒泡排序会不会应为
[code="java"]if(array[j]>array[j + 1])[/code]
这个总是不成立的，对比较分支jvm的预处理造成的效益
to mymGrubby:冒泡真不知道了，难道jvm对刚变动的数据做了缓存。。。这话有道理，也就是RednaxelaFX。相邻的两个单元的操作比跳着找逆序要快，不过这是不是java特有的，我回家用c试试。
To: xuyao
C应该也差不多，这一层可能是jvm层的优化，但很大可能是system层的优化。。。
还有俺这边选择逆序测试下来比插入排序要快
俺来提供一些测试结果 不用JVM 用J#
平台: WinXP + .net2.0 + J#2.0
代码: 楼主的代码 基本上没改 仅 随机数那一行 改成了
Random random = new Random(System.currentTimeMillis());
[quote]
冒泡+随机:0.625
冒泡+逆序:0.656
选择+随机:0.141
选择+逆序:0.14
插入+随机:0.094
插入+逆序:0.219
请按任意键继续. . .
冒泡+随机:0.657
冒泡+逆序:0.656
选择+随机:0.141
选择+逆序:0.14
插入+随机:0.11
插入+逆序:0.203
请按任意键继续. . .
冒泡+随机:0.641
冒泡+逆序:0.656
选择+随机:0.141
选择+逆序:0.14
插入+随机:0.11
插入+逆序:0.203
请按任意键继续. . .
冒泡+随机:0.625
冒泡+逆序:0.688
选择+随机:0.156
选择+逆序:0.125
插入+随机:0.109
插入+逆序:0.203
请按任意键继续. . .
冒泡+随机:0.625
冒泡+逆序:0.688
选择+随机:0.125
选择+逆序:0.14
插入+随机:0.094
插入+逆序:0.203
请按任意键继续. . .
[/quote]
再来提供一下JDK6的测试结果
平台: WinXP + JDK1.6.0_07
代码: 楼主的代码 仅改了随机数
Random random = new Random(System.nanoTime());
[quote]
冒泡+随机:0.421
冒泡+逆序:0.266
选择+随机:0.141
选择+逆序:0.156
插入+随机:0.078
插入+逆序:0.172
冒泡+随机:0.406
冒泡+逆序:0.25
选择+随机:0.156
选择+逆序:0.141
插入+随机:0.094
插入+逆序:0.156
冒泡+随机:0.421
冒泡+逆序:0.266
选择+随机:0.141
选择+逆序:0.14
插入+随机:0.11
插入+逆序:0.156
冒泡+随机:0.406
冒泡+逆序:0.266
选择+随机:0.172
选择+逆序:0.14
插入+随机:0.094
插入+逆序:0.172
冒泡+随机:0.39
冒泡+逆序:0.266
选择+随机:0.141
选择+逆序:0.156
插入+随机:0.078
插入+逆序:0.172
[/quote]
C#太逗乐 居然还有复的
懂行的讲讲为什么
平台: WinXP + .net2.0 + C#2.0
代码:
[code="C#"]
using System;
public class TestSort
{
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 = DateTime.Now.Millisecond;
bubbleSort(array);
long e = DateTime.Now.Millisecond;
Console.WriteLine("冒泡+随机:" + (e - b) / 1000.0);
generateContradictoryArray(array);
b = DateTime.Now.Millisecond;
bubbleSort(array);
e = DateTime.Now.Millisecond;
Console.WriteLine("冒泡+逆序:" + (e - b) / 1000.0);
generateRandomArray(array);
b = DateTime.Now.Millisecond;
selectionSort(array);
e = DateTime.Now.Millisecond;
Console.WriteLine("选择+随机:" + (e - b) / 1000.0);
generateContradictoryArray(array);
b = DateTime.Now.Millisecond;
selectionSort(array);
e = DateTime.Now.Millisecond;
Console.WriteLine("选择+逆序:" + (e - b) / 1000.0);
generateRandomArray(array);
b = DateTime.Now.Millisecond;
insertionSort(array);
e = DateTime.Now.Millisecond;
Console.WriteLine("插入+随机:" + (e - b) / 1000.0);
generateContradictoryArray(array);
b = DateTime.Now.Millisecond;
insertionSort(array);
e = DateTime.Now.Millisecond;
Console.WriteLine("插入+逆序:" + (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(DateTime.Now.Millisecond);
for (int i = 0; i < array.Length; i++)
{
array[i] = random.Next();
}
}
}
[/code]
结果:
[quote]
C:>TestSort
冒泡+随机:0.516
冒泡+逆序:-0.672
选择+随机:0.218
选择+逆序:0.235
插入+随机:0.11
插入+逆序:-0.781
C:>TestSort
冒泡+随机:-0.484
冒泡+逆序:0.328
选择+随机:-0.765
选择+逆序:0.234
插入+随机:0.109
插入+逆序:0.235
C:>TestSort
冒泡+随机:-0.485
冒泡+逆序:0.329
选择+随机:0.234
选择+逆序:0.234
插入+随机:-0.859
插入+逆序:0.218
C:>TestSort
冒泡+随机:0.515
冒泡+逆序:-0.672
选择+随机:0.235
选择+逆序:0.219
插入+随机:0.109
插入+逆序:0.235
C:>TestSort
冒泡+随机:0.516
冒泡+逆序:-0.672
选择+随机:0.218
选择+逆序:0.25
插入+随机:0.125
插入+逆序:0.25
[/quote]
再来提供一下JDK1.4的测试结果
平台: WinXP + JDK1.4.2_08
代码: 楼主的代码 仅改了随机数
Random random = new Random(System.currentTimeMillis());
[quote]
C:\Programs\bea\jdk142_08\bin>javac TestSort.java
C:\Programs\bea\jdk142_08\bin>java TestSort
冒泡+随机:0.5
冒泡+逆序:0.36
选择+随机:0.172
选择+逆序:0.171
插入+随机:0.125
插入+逆序:0.235
C:\Programs\bea\jdk142_08\bin>java TestSort
冒泡+随机:0.485
冒泡+逆序:0.36
选择+随机:0.187
选择+逆序:0.172
插入+随机:0.14
插入+逆序:0.266
C:\Programs\bea\jdk142_08\bin>java TestSort
冒泡+随机:0.484
冒泡+逆序:0.375
选择+随机:0.156
选择+逆序:0.188
插入+随机:0.125
插入+逆序:0.25
C:\Programs\bea\jdk142_08\bin>java TestSort
冒泡+随机:0.485
冒泡+逆序:0.375
选择+随机:0.157
选择+逆序:0.172
插入+随机:0.11
插入+逆序:0.235
C:\Programs\bea\jdk142_08\bin>java TestSort
冒泡+随机:0.5
冒泡+逆序:0.375
选择+随机:0.156
选择+逆序:0.188
插入+随机:0.125
插入+逆序:0.234
[/quote]