JAVA数据结构和算法第二版书中冒泡排序貌似有错？

今天周末，无聊，回顾下数据结构，然后按对冒泡的理解随便写了个冒泡排序，通了！~，翻开经典：《JAVA数据结构和算法第二版》，看看经典是怎么写的。嗯，经典的思路是要好些，虽然比较次数一样，但是循环次数少很多，运行了下，啊！？怎么排序不对！？

 

如下我的代码：

 

package org.acooly.datastructure.sort;

import org.apache.commons.lang.ArrayUtils;
import org.apache.commons.lang.math.RandomUtils;

public abstract class Sort {

	public static void main(String[] args) {
		int dataSize = 10;
		int[] data = new int[dataSize];
		for (int i = 0; i < data.length; i++) {
			int member = RandomUtils.nextInt(dataSize * 10);
			if (!ArrayUtils.contains(data, member)) {
				data[i] = member;
			}
		}
		data = new int[] { 3, 21, 46, 75, 56, 39, 7, 95, 93, 1 };
		printArray("原始数据: ", data);
		bubbleSort(data);
		printArray("经典冒泡排序: ", data);
		
		System.out.println();
		
		data = new int[] { 3, 21, 46, 75, 56, 39, 7, 95, 93, 1 };
		printArray("原始数据: ", data);
		myBubble(data);
		printArray("我的冒泡排序: ", data);

	}

	/**
	 * 我的写法
	 * @param data
	 */
	public static void myBubble(int[] data) {
		int swapCount = 0;
		int loopCount = 0;
		for (int j = 0; j < data.length - 1; j++) {
			for (int i = 1; i < data.length; i++) {
				if (data[i] < data[i - 1]) {
					swap(data, i, i - 1);
					swapCount++;
				}
				loopCount++;
			}
		}
		System.out.println("交换次数：" + swapCount);
		System.out.println("循环次数：" + loopCount);
	}

	
	/**
	 * JAVA数据结构和算法第二版的写法
	 * @param data
	 */
	public static void bubbleSort(int[] data){
		int swapCount = 0;
		int loopCount = 0;
		for (int out = data.length - 1; out > 1; out--) {
			for (int in = 0; in < out; in++) {
				if(data[in] > data[in+1]){
					swap(data,in,in+1);
					swapCount++;
				}
				loopCount++;
			}
			printArray("out " + out + ": ", data);
		}
		System.out.println("交换次数：" + swapCount);
		System.out.println("循环次数：" + loopCount);
	}
	

	

	/**
	 * 交换数组中两个元素的值
	 * 
	 * @param data
	 * @param i
	 * @param j
	 */
	public static void swap(int[] data, int i, int j) {
		int temp = data[i];
		data[i] = data[j];
		data[j] = temp;
	}

	public static void printArray(String message, int[] data) {
		System.out.println(message + ArrayUtils.toString(data));
	}

}

 

 

 运行结果：

 

原始数据: {3,21,46,75,56,39,7,95,93,1}
out 9: {3,21,46,56,39,7,75,93,1,95}
out 8: {3,21,46,39,7,56,75,1,93,95}
out 7: {3,21,39,7,46,56,1,75,93,95}
out 6: {3,21,7,39,46,1,56,75,93,95}
out 5: {3,7,21,39,1,46,56,75,93,95}
out 4: {3,7,21,1,39,46,56,75,93,95}
out 3: {3,7,1,21,39,46,56,75,93,95}
out 2: {3,1,7,21,39,46,56,75,93,95}   //经典书中写法，到2就结束了？少了一次比较？
交换次数：18
循环次数：44
经典冒泡排序: {3,1,7,21,39,46,56,75,93,95}

原始数据: {3,21,46,75,56,39,7,95,93,1}
交换次数：19
循环次数：81
我的冒泡排序: {1,3,7,21,39,46,56,75,93,95}

 

代码中的in < out应该是in <= out才对吧？

 

不相信经典会错，然后COPY书中原始代码试试：

 

 

package org.acooly.datastructure.sort;

public class ArrayBub {

	private long[] a;
	private int nElems;
	
	public ArrayBub(int max) {
		a = new long[max];
		nElems = 0;
	}
	
	public void insert(long value){
		a[nElems] = value;
		nElems++;
	}
	
	public void display(){
		for (int j = 0; j < nElems; j++) 
			System.out.print(a[j] + " ");
		System.out.println("");
	}
	
	public void bubbleSort(){
		int out,in;
		for (out = nElems - 1; out > 1; out--) {
			for (in = 0; in < out; in++) {
				if(a[in] > a[in + 1])
					swap(in,in+1);
			}
		}
	}
	
	
	private void swap(int one,int two){
		long temp = a[one];
		a[one] = a[two];
		a[two] = temp;
	}
	
}

 

 

 

package org.acooly.datastructure.sort;

public class BubbleSortApp {

	public static void main(String[] args) {
		System.out.println("书中原始测试：");
		int maxSize = 100;
		ArrayBub arr;
		arr = new ArrayBub(maxSize);
		arr.insert(77);
		arr.insert(99);
		arr.insert(44);
		arr.insert(55);
		arr.insert(22);
		arr.insert(88);
		arr.insert(11);
		arr.insert(00);
		arr.insert(66);
		arr.insert(33);
		arr.display();
		
		arr.bubbleSort();
		arr.display();
		arr = null;

		
		System.out.println("我变了下数组数据的测试：");
		//{ 3, 21, 46, 75, 56, 39, 7, 95, 93, 1 };
		arr = new ArrayBub(maxSize);
		arr.insert(3);
		arr.insert(21);
		arr.insert(46);
		arr.insert(75);
		arr.insert(56);
		arr.insert(39);
		arr.insert(7);
		arr.insert(95);
		arr.insert(93);
		arr.insert(1);
		arr.display();
		
		arr.bubbleSort();
		arr.display();

	}
}

 

 

 

运行结果：

 

书中原始测试：
77 99 44 55 22 88 11 0 66 33 
0 11 22 33 44 55 66 77 88 99 
我变了下数组数据的测试：
3 21 46 75 56 39 7 95 93 1 
3 1 7 21 39 46 56 75 93 95 

 

 

貌似真有错？！

 

评论

2 楼 zp820705 2011-07-11  

你说的对，受教。

1 楼 sjzzdf 2011-07-10  

for (int i = 1; i < data.length; i++) {  
                if (data[i] < data[i - 1]) {  
                    swap(data, i, i - 1);   ????你冒泡排序的j呢？没用上？而且你冒泡的算法似乎就没搞清楚。

下面是我写的：
public class BubbleSort{
public static void main(String[] args) throws Exception{

int []ary=new int[]{9,8,7,6,4,2,4};
int len=ary.length;
for(int i=0;i<len-1;i++)
  for(int j=i+1;j<len;j++)
    {
     if(ary[j]<ary[i]){
          int temp=ary[j];
          ary[j]=ary[i];
          ary[i]=temp;

       } 

     }
for(int k=0;k<len;k++)
{System.out.print("  "+ary[k]);}

}

}