欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-07-12 15:57:57
...
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

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

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