java实现排序算法之交换排序（冒泡排序、快速排序）

交换排序的主体操作是对数组中的数据不断进行交换操作。交换排序主要有冒泡排序和快速排序。
一、冒泡排序
       冒泡排序，是指计算机的一种排序方法，它的时间复杂度为O（n^2），虽然不及堆排序、快速排序的O（nlogn，底数为2），但是有两个优点：1.“编程复杂度”很低，很容易写出代码；2.具有稳定性，这里的稳定性是指原序列中相同元素的相对顺序仍然保持到排序后的序列，而堆排序、快速排序均不具有稳定性。不过，一路、二路归并排序、不平衡二叉树排序的速度均比冒泡排序快，且具有稳定性，但速度不及堆排序、快速排序。冒泡排序是经过n-1趟子排序完成的，第i趟子排序从第1个数至第n-i个数，若第i个数比后一个数大（则升序，小则降序）则交换两数。
定义数据包装类：

//定义一个数据包装类
public class DataWrap implements Comparable<DataWrap>  
{
	int data;
	String flag;
	public DataWrap(int data, String flag)
	{
		this.data = data;
		this.flag = flag;
	}
	public String toString()
	{
		return data + flag;
	}
	//根据data实例变量来决定两个DataWrap的大小
	public int compareTo(DataWrap dw)
	{
		return this.data > dw.data ? 1 
			: (this.data == dw.data ? 0 : -1);
	}
}

public class BubbleSort
{
	public static void bubbleSort(DataWrap[] data) 
	{
		System.out.println("开始排序");
		int arrayLength = data.length;
		for (int i = 0; i < arrayLength - 1 ; i++ )
		{
			boolean flag = false;
			for (int j = 0; j < arrayLength - 1 - i ; j++ )
			{
				//如果j索引处的元素大于j+1索引处的元素
				if (data[j].compareTo(data[j + 1]) > 0)
				{
					//交换它们
					DataWrap tmp = data[j + 1];
					data[j + 1] = data[j];
					data[j] = tmp;
					flag = true;
				}
			}
			System.out.println(java.util.Arrays.toString(data));
			//如果某趟没有发生交换，则表明已处于有序状态
			if (!flag)
			{
				break;
			}
		}
	}
	public static void main(String[] args)
	{
		DataWrap[] data = {
			new DataWrap(9 , ""),
			new DataWrap(16 , ""),
			new DataWrap(21 , "*"),
			new DataWrap(23 , ""),
			new DataWrap(30 , ""),
			new DataWrap(49 , ""),
			new DataWrap(21 , ""),
			new DataWrap(30 , "*")
		};
		System.out.println("排序之前：\n"
			+ java.util.Arrays.toString(data));
		bubbleSort(data);
		System.out.println("排序之后：\n" 
			+ java.util.Arrays.toString(data));
	}
}

二、快速排序
      快速排序（Quicksort）是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

public class QuickSort
{
	//将指定数组的i和j索引处的元素交换
    private static void swap(DataWrap[] data, int i, int j)
    {
        DataWrap tmp;
        tmp = data[i];
        data[i] = data[j];
        data[j] = tmp;
    }
	//对data数组中从start～end索引范围的子序列进行处理
	//使之满足所有小于分界值的放在左边，所有大于分界值的放在右边
	private static void subSort(DataWrap[] data
		, int start , int end)
	{
		//需要排序
		if (start < end)
		{
			//以第一个元素作为分界值
			DataWrap base = data[start];
			//i从左边搜索，搜索大于分界值的元素的索引
			int i = start;
			//j从右边开始搜索，搜索小于分界值的元素的索引
			int j = end + 1;
			while(true)
			{
				//找到大于分界值的元素的索引，或i已经到了end处
				while(i < end && data[++i].compareTo(base) <= 0);
				//找到小于分界值的元素的索引，或j已经到了start处
				while(j > start && data[--j].compareTo(base) >= 0);
				if (i < j)
				{
					swap(data , i , j);
				}
				else
				{
					break;
				}
			}
			swap(data , start , j);
			//递归左子序列
			subSort(data , start , j - 1);
			//递归右边子序列
			subSort(data , j + 1, end);
		}
	}
	public static void quickSort(DataWrap[] data) 
	{
		subSort(data , 0 , data.length - 1);
	}
	public static void main(String[] args)
	{
		DataWrap[] data = {
			new DataWrap(9 , ""),
			new DataWrap(-16 , ""),
			new DataWrap(21 , "*"),
			new DataWrap(23 , ""),
			new DataWrap(-30 , ""),
			new DataWrap(-49 , ""),
			new DataWrap(21 , ""),
			new DataWrap(30 , "*"),
			new DataWrap(13 , "*")
		};
		System.out.println("排序之前：\n"
			+ java.util.Arrays.toString(data));
		quickSort(data);
		System.out.println("排序之后：\n" 
			+ java.util.Arrays.toString(data));
	}
}

评论

1 楼 cch2012ky 2013-05-08  

   while(true) 
            { 
                //找到大于分界值的元素的索引，或i已经到了end处 
                while(i < end && data[++i].compareTo(base) <= 0); 
                //找到小于分界值的元素的索引，或j已经到了start处 
                while(j > start && data[--j].compareTo(base) >= 0); 
                if (i < j) 
                { 
                    swap(data , i , j); 
                } 
                else 
                { 
                    break; 
                } 
            } 
中判断条件两个compareTo(base) <= 0最好改为compareTo(base) <0，否则会造成时间复杂度降格为O（n平方)