快速排序,实现简单
但是N长度的数组所需的时间和NlgN成正比,并且是原地排序,缺点是十分脆弱,导致性能低劣
快速排序的实现简单来说可以是,将一个数组分成两个数组进行分开排序,分别使用递归的方法,是两个数组有序,两个数组有序的话,自然完成了
主要就是这个分开的点的问题,怎么选择?
这个点的选择必须满足:
1.对于某个j,a[j]已经排好了;
2.a[stat]到a[j-1]都小于a[j]
3.a[j+1]到a[end]都大于a[j]
上述三个条件必须同时满足
我们需要一个方法,专门的帮我们去寻找中间点
| public static void sort(Comparable[] a) {// 进行排序的方法
sort(a, 0, a.length – 1); } public static void sort(Comparable[] a,int start,int end) {// 进行排序的方法 if (end<=start) return; int mid = partition(a, start, end); sort(a, start, mid-1); sort(a, mid+1, end); } private static int partition(Comparable[] a, int start, int end) {// 进行断点寻找 int i = start;// 初始化变量 int j = end + 1; Comparable temp = a[start]; while (true) {// 设置无限循环 while (less(a[++i], temp)) { if (i == end) {// 进行判断是否一直小于,从头到尾 break; } } while (less(temp, a[–j])) { if (j == start) { break; } } if (i >= j) break; exch(a, i, j);// 上面两个如果都遇到违反条件的,进行交换 } exch(a, start, j);// 交换到中间 return j;// 交换完成,返回 } |
先去左侧寻找一个比临时值小的,然后去右侧找一个比临时值大的,然后交换
需要注意的点有:
1.使用辅助数组,要注意开销
2.别越界,如果切分元素正好为最大或者最小的元素,注意别让指针跑出数组边界
3.终止元素时候,要考虑到数组中可能包含和切分元素相同的元素
4.如果相同,处理起来左侧扫描最好遇到大于等于切分元素值停下
5.右侧扫描最好遇到小于等于元素值停下
优点在于和其他的算法比较,移动数据较少,
实现的特点在于用一个递增的索引和数组元素进行比较
有极端的情况,极端情况基本等于选择排序
三分法去排序数组,增加了等于的元素部分
对于有重复元素的数组进行改进,从左到右遍历数组,维护一个指针使左边的元素都小于插入点,右边的元素都大于插入点, 还有一部分等于元素
public static void sort(Comparable[] a) {// 进行排序的方法
sort(a, 0, a.length- 1);
}
private static void sort(Comparable[] a,int start,int end) {// 进行排序的方法
if (end<=start)
return;
int x = start;
int i = start + 1;
int y = end;//设置条件
Comparable v = a[start];
while (i<=y) {//不断缩小未确定的范围,如果写成了start会出现指针报错
int cmp = a[i].compareTo(v);
if (cmp<0)//如果小于
exch(a, x++, i++);//交换两者,使小的值在前
else if (cmp>0)//如果大于
exch(a, i, y–);//交换两者,使大值在后面,i不自增的原因是要看是否还大的
else
i++;//相同则自增
}//现在小于v的(start,x-1),等于的(x,y),大于的(y+1,end)
sort(a, start, x-1);
sort(a, y+1, end);
}
流程图也在上面
接下来考虑算法的性能
考虑字符串键都很长的情况下且键的前大部分首字母相同,
三向字符串算法速度最多比普通的少2lnN个
其性能的优越来源于并不依赖字母表的大小