java实现交换排序(冒泡排序、快速排序)

 

冒泡排序

   由于它的简洁，冒泡排序通常被用来对于程序设计入门的学生介绍算法的概念。  

 

冒泡排序算法的运作如下：

 

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

	/**
	 * 冒泡排序
	 * 
	 * @param ts
	 */
	public static <T extends Comparable<? super T>> void BubbleSort(T[] ts) {
		// 如果一次都没有交换，表示已经排好序
		boolean isSorted = false;
		// 从0到i中找出最大值
		for (int i = ts.length - 1; i > 0; i--) {

			isSorted = true;

			for (int y = 0; y < i; y++) {

				if (ts[y].compareTo(ts[y + 1]) > 0) {

					isSorted = false;
					T temp = ts[y + 1];
					ts[y + 1] = ts[y];
					ts[y] = temp;

				}

			}

			if (isSorted)
				break;
		}
	}

 

 

1.  时间复杂度：O(n^2)

 

      冒泡排序耗时的操作有：比较 + 交换赋值。时间复杂度如下：

1)    最好情况：序列是升序排列，在这种情况下，需要进行的比较操作为（n-1）次。交换操

        作为0次。即O(n)

2)   最坏情况：序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。交换操作数和比

       较操作数一样。即O(n^2)

 

3)   渐进时间复杂度（平均时间复杂度）：O(n^2)

2.   空间复杂度：O(1)

3.  稳定性

         冒泡排序是稳定的，不会改变相同元素的相对顺序。

 

 

快速排序

 

       快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序n个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n)算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来

        基本思想参考:http://ahalei.blog.51cto.com/4767671/1365285

 

       本例中排序思想：补充快排的一些细节。

 

         1）从ts[left]、ts[center]、ts[right]选出中间值作为基准值。

              好处：三个元素中最小者被分在ts[left]，而这正是分割阶段应该将它放到的位置。三

                        个元素中最大着被分在ts[right]，这也是正确位置，因为它大于基准值。因此我

                        们可以把基准放到a[right-1]。

 

         2）左面开始位置 i ,右面开始位置 j

 

         3）经过第1步，left<基准，right>基准，基准位置在[right-1]  。因此 i = left+1 ,j = right-2

 

         4）快排是用递归来实现的,所以到最后，会经常出现小数组排序的情况，即排序区域只有〈=20个元素。对于小的数组，快排不如插入排序。本例中采用一种好的截止范围是N=10,这种做法刚好避免了在三个元素取中值而实际上却只有一个或两个元素的情况。

 

	/**
	 * 快速排序
	 */
	public static <T extends Comparable<? super T>> void quickSort(T[] ts) {

		quickSort(ts, 0, ts.length - 1);
	}

	/**
	 * 主例程
	 */
	private static <T extends Comparable<? super T>> void quickSort(T[] ts, int left, int right) {

		if (left + 10 <= right) {

			T pivot = median3(ts, left, right);

			int i = left, j = right - 1;

			for (;;) {// 开始i,j交换

				while (ts[++i].compareTo(pivot) < 0) {}// i>=pivot stop
				while (ts[--j].compareTo(pivot) > 0) {}// j<=pivot stop

				if (i < j)
					swapRef(ts, i, j);// i,j交换
				else
					break;

			}

			swapRef(ts, i, right - 1); // 恢复基准值位置

			quickSort(ts, left, i - 1); // 排序小元素
			quickSort(ts, i + 1, right);// 排序大元素

		} 
		else  //排序元素个数小于10，采用直接插入排序
			insertSort(ts, left, right);

	}

	/**
	 * left\right\center 取中值=基准（pivot）
	 */
	private static <T extends Comparable<? super T>> T median3(T[] ts, int left, int right) {

		int center = (left + right) / 2;

		// 两步确定3个值中的最小，放到left位置
		if (ts[center].compareTo(ts[left]) < 0)
			swapRef(ts, center, left);
		if (ts[right].compareTo(ts[left]) < 0)
			swapRef(ts, right, left);
		if (ts[right].compareTo(ts[center]) < 0)
			swapRef(ts, center, right);

		// 基准 位置
		swapRef(ts, center, right - 1);

		return ts[right - 1];
	}

	/**
	 * 交换元素位置
	 */
	private static <T extends Comparable<? super T>> void swapRef(T[] ts, int x, int y) {
		T temp = ts[x];
		ts[x] = ts[y];
		ts[y] = temp;
	}

	/**
	 * 插入排序
	 */
	private static <T extends Comparable<? super T>> void insertSort(T[] ts, int left, int right) {
		int y;
		for (int i = left + 1; i <= right; i++) {
			T temp = ts[i];
			for (y = i; y > left && temp.compareTo(ts[y - 1]) < 0; y--)
				ts[y] = ts[y - 1];
			ts[y] = temp;
		}

	}

1.  时间复杂度：O(n^2)

 

       最差时间复杂：O(n^2)

       最优时间复杂：O(nlogn)

       平均时间复杂：O(nlogn)

2.   空间复杂度：

 

           O(n log n)

3.  稳定性

         不稳定。

 

 

 简单性能测试

 

	/**
	 * 简单的
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		int num = 1000000;
		Integer[] inters = new Integer[num];
		Random inter = new Random();
		for (int i = 0; i < num; i++) {
			inters[i] = inter.nextInt(num);
		}
		long tims = System.currentTimeMillis();
		quickSort(inters);
		tims -= System.currentTimeMillis();
		System.err.println(tims * -1);
		// System.err.println(Arrays.toString(inters));
	}

 

 

 

 

排序方法\数组大小	1000	5000	10000	50000	10w	100w	1000w
直接插入排序	17	50	130	2.4s	10s	太长	太长
二分for循环	8	43	60	950	5s	太长	太长
二分java本地copy	1	10	23	165	470	50s	太长
选择排序	29	45	104	2.3s	10s	太长	太长
冒泡排序	35	106	320	8s	38s	太长	太长
希尔增量排序	2	11	20	38	55	1s	20s
堆排序	3	15	20	28	40	600	10s
快速排序	1	9	19	80(比较不稳定)	130(不稳)	250	3.7s