java实现选择排序(直接选择排序、堆排序)

 

 

 直接选择排序

 

        选择排序的原理：将数组分为有序区，无序区。初始有序区元素为0，整个数组为无序区。每次遍历从无序区中选出一个最小（或最大）的元素，放在有序区的最后，每一次遍历排序过程都是有序区元素个数增加，无序区元素个数减少的过程，直到无序区元素个数位0。

 

    直接选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的数组进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

 

    

 

	/**
	 * 直接选择排序
	 * 
	 * @param ts
	 */
	public static <T extends Comparable<? super T>> void selectSort(T[] ts) {

		int length = ts.length;
		int min; // 无序区最小元素位置
		T tem; // 辅助空间

		for (int i = 0; i < length - 1; i++) {

			min = i;// 默认取无序区第一个元素为最小值

			// 循环遍历无序区，查找到无序区最小元素
			for (int y = i + 1; y < length; y++)
				if (ts[min].compareTo(ts[y]) > 0)
					min = y;

			if (i == min)
				continue;

			// 把无序区最小元素,插入到有序区末尾
			tem = ts[i];
			ts[i] = ts[min];
			ts[min] = tem;

		}
	}

 

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

 

      直接选择排序耗时的操作有：比较 + 交换赋值。时间复杂度如下：

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

      值操作为0次。即O(n^2)

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

      次（交换次数比冒泡排序少多了），选择排序的效率比较稳定，最好情况和最坏情况差

     不多。即O(n^2)

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

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

3.  稳定性

        直接选择排序是不稳定的。

        因为每次遍历比较完后会使用本次遍历选择的最小元素和无序区的第一个元素交换位置，所以如果无序区第一个元素后面有相同元素的，则可能会改变相同元素的相对顺序。

 

 

 

  堆排序

 

       堆是一颗被完全填满的二叉树，有可能的例外是在底层，底层上的元素从左到右填入。这样的树称为完全二叉树。

 

堆的性质:

 

      比如我们想找出最大元，因为最大元在根上，而且任意子树也是一个堆，那么任意节点就应该大于它的所有后裔。

 

        一个重要的观察发现，因为完全二叉树这么有规律，所以可以用一个数组表表示而不需要使用链， 对于数组中任意位置的i上元素，其左儿子在位置[2i+1]上，右儿子在左儿子后的[（2i+1）+1]位置，它的父亲则在[i-1/2] 上，注意[0]位置是根。如下图

 

    

 

       当新增一个元素24时，我们在下一个可用位置插入元素24。因为24>10,所以破坏了堆的性质，解决：把24朝着根的方向上移，直到24放入正确的位置。 如下图，这里称之为上虑。（堆排序，不会用到）

    

 

        当删除最大元时。由于现在堆少了一个元素，因此堆中最后一个元素必须移动到堆中某个地方。我们的做法是将最后一个元素放在删除的最大元位置。然后向下插入到最大儿子路径的一个正确的位置。这里称之为下虑。堆排中会递归删除最大元。

 

 

       根据上面堆的性质，每次删除最大元后，堆缩小1，因此，堆中最后的单元可以用来存放刚刚删去的元素。

       下图中先进行，先把数组初始化成最大堆，然后递归删除最大元（最左面那根），每次删除的最大元放在数组的length-1，length-2，length-3......

    

 

 

 

在堆的数据结构中，堆中的最大值总是位于根节点。堆中定义以下几种操作：

• 最大堆调整：将堆的末端子节点作调整，使得子节点永远小于父节点
• 创建最大堆：将堆所有数据重新排序
• 堆排序：移除位在第一个数据的根节点，并做最大堆调整的递归运算

 

	/**
	 * 堆排序
	 * 
	 * @param ts
	 */
	public static <T extends Comparable<? super T>> void heapSort(T[] ts) {

		// 通过下虑，将数组初始化成一个堆。
		for (int length = ts.length, i = length / 2 - 1; i >= 0; i--)
			percDown(ts, i, length);

		// 对具有堆性质的数组排序
		for (int len = ts.length - 1; len >= 0; len--) {
			// 将最大元[0]删除，即放到堆尾，堆尾元素放到最大元位置
			swap(ts, len);
			// 对最大元位置元素 下虑
			percDown(ts, 0, len);
		}
	}

	/**
	 * 下虑 找出最大元
	 * 
	 * @param ts
	 * @param index
	 * @param length
	 */
	private static <T extends Comparable<? super T>> void percDown(T[] ts, int i, int length) {

		T temp = ts[i];// 待调整最大元位置元素

		for (int child = leftChild(i); child < length; i = child, child = leftChild(i)) {

			// 判断有右儿子&&右儿子>左儿子
			if (child + 1 != length && ts[child + 1].compareTo(ts[child]) > 0)
				child++;

			// 最大儿子跟父比较
			if (temp.compareTo(ts[child]) < 0)
				ts[i] = ts[child];

			else
				break;
		}

		ts[i] = temp;// 放到正确位置
	}

	/**
	 * 堆尾、堆首互换
	 * 
	 * @param ts
	 * @param index
	 */
	private static <T extends Comparable<? super T>> void swap(T[] ts, int index) {
		T temp = ts[index];
		ts[index] = ts[0];
		ts[0] = temp;
	}

	/**
	 * 左儿子位置
	 * 
	 * @param i
	 * @return
	 */
	private static int leftChild(int i) {
		return i * 2 + 1;
	}

 

 

 1.  时间复杂度：O(nlog₂n)

 

       首先把数组，初始化成一个堆。这个阶段花费O(N)的时间，可以忽略。

 

       然后执行N次的删除最大元，每次最大元删除重排花费的时间为O(logn)，因此

       最差时间复杂：O(nlogn)

       最优时间复杂：O(nlogn)

       平均时间复杂：O(nlogn)

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

 3.  稳定性

          堆排序是不稳定的
         因为在初始化堆时，相同元素可能被分配到不同的父节点下，所以在反复调整堆过程中，可能会改变相同元素的相对顺序

 

 

 简单性能测试

 

 

	/**
	 * 简单的性能测试
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		int num = 100000;
		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();
		// heapSort(inters);
		selectSort(inters);
		tims -= System.currentTimeMillis();
		System.err.println(tims * -1);
	}

 

 

排序方法\数组大小	1000	5000	10000	50000	10w	100w	1000w
选择排序	29	45	104	2.3s	10s	太长	太长
堆排序	3	15	20	28	40	600	10s

 

 

评论

1 楼 lueye 2016-10-18  

堆排序的时候for循环中是不是应该len > 0 而不是len >= 0呢