排序算法(四)--快速排序

package sort;

import java.util.Arrays;
import java.util.Random;

/**
 * 快速排序
 * 最坏复杂度：N^2 ，一般是：logn
 * 原理：1.任意选定一个元素key,然后将大于key 的元素放右边，小于key 的元素 放左边
 *       2.将key左右两边元素分别看成一个新的数组，然后再用1 步骤方法，重复，直到只有一个元素为止
 * 分离步骤：
 *       1.选定一个数组t[i]元素作为key，假设选第一个 ,i=0 位置开始
 *       
 *       2.用最后一个元素 j = t.length -1 和 key 做比较，也就是从后(右)开始搜索，条件i<j
 *         2.1 如果t[j] >= key,我们就不需要移动元素（默认大的放后(右)面），继续左移, j--.
 *         2.2 如果t[j] <  key,将t[i] 位置放入当前小的元素t[j],t[i] = t[j]. 然后 i ++.
 *         
 *       3.用前面的元素t[i],和key 做比较，也就是从前（左）开始搜索，条件i<j
 *         3.1 如果t[i] <= key, 我们不需要移动位置，继续 右移,i++
 *         3.2 如果t[i] > key,将大的元素放右边，t[j] = t[i],然后 j--;
 * 
 *       注意：2 3步骤是小的元素左移，大的元素右移，i++,j--,向中间靠拢，才能完成分离
 *       4.当i<j 的时候，重复2 3步骤，直到 i = j.
 *       5.上面完成了一次分离，然后同理，将分离时，key 所在的位置i 作为分界线
 *          把i 前面的元素，和 后面的元素 分别又进行分离，反复迭代，就可以了
 *      比如：现在有a b c d e f g 7个士兵。以a为开始，作为key 拉出来比较
 *      1.从g 后面开始比较，找到一个比a 矮的人，比a高的位置不动。比如现在找到f 比a 矮，
 *        那么就让f 到a 的位置去站着。(a 假设临时站f 的位置)
 *        现在是：g b c d e (a) g
 *      2.然后从前面开始，因为g已经比a 矮了，然后从b 开始比较。找到一个 比a 高的。
 *        假设c 比 a 高，那么c 就跑到现在a 所在的位置。
 *        现在是:g b (a)  d e c g
 *      3.就这样一直到终点，就完成第一次分离了。下面就是循环
 * @author @Ran
 * 
 */
public class Quick<T> extends AbstractSort<T> {

	/**
	 * 二分隔离法，将数据分割成以t[i] 为中线的两部分元素 其中左边的元素全部小于t[i],
	 * 右边的元素全部大于t[i]
	 */
	public <T extends Comparable<? super T>> int dichotomieSwap(T[] t, int i,int j) {
		T key = t[i];
		// 保证每一次 都分完
		while (i < j) {
			// 从后面开始搜索,如果第一个元素大于key,就继续搜索，直到发现小于key                        // 的跳出循环
			while (i < j && t[j].compareTo(key) >= 0) {
				j--;
			}
			// 找到第一个比key 小的元素，并赋值
			if (i < j) {
				setValue(t, i, j);
				i++;
			}
			while (i < j && t[i].compareTo(key) <= 0) {
				// 向前开始搜索，如果搜索的第一个元素小于key,继续搜索，直到                                // 发现大于key 跳出循环
				i++;
			}
			if (i < j) {
				setValue(t, j, i);
				j--;
			}
		}
		setValue(t, i, key);
		// 返回这个中间元素移动到的位置
		return i;
	}
	
    // 重写方法
	public <T extends Comparable<? super T>> T[] swap(T[] t, int i, int j) {
		if (i < j) {
			// 分离
			int mid = dichotomieSwap(t, i, j);
			// 迭代 同原理操作左边
			swap(t, i, mid - 1);
			// 迭代，操作右边数据
			swap(t, mid + 1, j);
		}
		return t;
	}

	// 重写方法
	public <T extends Comparable<? super T>> T[] sort(T[] t) {
		return swap(t, 0, t.length - 1);
	}

	public static void main(String[] args) {
		int a = 30000;
		Integer[] t = new Integer[a];
		Random r = new Random();
		for (int i = 0; i < a; i++) {
			t[i] = r.nextInt(a);
		}
		Integer[] t2 = t.clone();
		System.out.println("未排序结果：" + Arrays.toString(t));
		// 这里用了下 插入排序做比较
		Sort s1 = new Quick();
		Sort s2 = new Insertion();
		s1.sort(s1, t);
		s2.sort(s2, t2);
		System.out.println("排序后结果：" + Arrays.toString(t));
		System.out.println(s1);
		System.out.println(s2);
	}

}

 

 

图例参考：http://blog.csdn.net/wxwzy738/article/details/7832737

小结：这个算算法有很多改进之处，并且各种效率针对的情况不同，后面有机会再逐步分析

          排序个人认为对小数据没什么意义的，大量数据才能看出效果，根据数据的不同，采取不同的排序