排序算法(四)--快速排序
程序员文章站
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
小结:这个算算法有很多改进之处,并且各种效率针对的情况不同,后面有机会再逐步分析
排序个人认为对小数据没什么意义的,大量数据才能看出效果,根据数据的不同,采取不同的排序
上一篇: 反射(一)----原理机制和基本运用
下一篇: 如何规划你的职业发展道路