自己写的快速排序
测试效率:对于 20000 个随机数排序
插入排序:Time cost:2005ms
手写快排:Time cost:12ms
Sun API Arrays.sort() Time cost:3ms
import java.util.Arrays;
import java.util.Date;
// 快速排序
/**
* author : Jason liu
* 有三点优化:
* 1、选择 枢轴项时,选第一个元素、最后元素和中间元素的中值
* 2、边缘效应,对于不大于10的子数组,采用简单的 插入排序
* 3、总是先排序较小的子数组(空间效率高),本程序未采用
*/
public class Quicksort {
// 私有化 构造函数,不可产生实例
private Quicksort(){}
public static <T extends Comparable<T>> void sort(T[] list)
{
quick(list ,0, list.length-1);
//边缘效应,对于长度不超过10的子数组,直接插入排序
insertSort(list);
}
// 递归
static <T extends Comparable<T>> void quick(T[] list, int lo, int hi)
{
if( (hi-lo)>10 )
{
// 分治
int splitPoint =split(list,lo,hi);
quick(list, lo,splitPoint-1);
quick(list, splitPoint+1,hi);
}
}
// 分治
static <T extends Comparable<T>> int split(T[] list, int lo, int hi)
{
// 获取枢轴项
int median=getMedian(list,lo,hi);
// 把枢轴项 放到 最前端
T temp=list[lo]; list[lo]=list[median]; list[median]=temp;
T piovt=list[lo];
int left=lo+1;
int right=hi;
while(left<=right)
{
// 1 移动 左游标 left,获取第一个不小于 pivot的项
while(left<=hi&&left<=right)
{
if(list[left].compareTo(piovt)>=0) break;
left++;
}
// 2 移动 右游标 right,获取第一个小于 pivot 的项
while(right>lo&&left<=right)
{
if(list[right].compareTo(piovt)<0) break;
right--;
}
// 3 交换 获取的两项
if(left<right)
{
temp=list[left]; list[left]=list[right]; list[right]=temp;
left++; right--;
}
}
// 交换 枢轴项
temp=list[right]; list[right]=list[lo]; list[lo]=temp;
return right;
}
// 获取枢轴项,选择第一个元素、中间元素和最后一个元素的中值
static <T extends Comparable<T>> int getMedian(T[] list, int lo,int hi)
{
int mid=(lo+hi)/2;
if(list[lo].compareTo(list[mid])<0)
{
if(list[mid].compareTo(list[hi])<0) return mid;
else if(list[lo].compareTo(list[hi])<0) return hi;
else return lo;
}
else
{
if(list[lo].compareTo(list[hi])<0) return lo;
else if (list[mid].compareTo(list[hi])<0) return hi;
else return mid;
}
}
static <T extends Comparable<T>> void insertSort(T[] list)
{
T temp;
int j;
for(int i=1; i<list.length; i++)
{
j=i-1;
temp=list[i];
while(j>=0&&list[j].compareTo(temp)>0)
{
list[j+1]=list[j];
j--;
}
list[j+1]=temp;
}
}
public static void main(String[] args) {
Integer [] arr=new Integer [20000];
for(int i=0;i<arr.length;i++)
{
arr[i]=(int)(Math.random()*20000);
}
// System.out.println(Arrays.toString(arr)+"\n");
// insert sort:
Date d1=new Date();
Quicksort.<Integer>insertSort(arr);
Date d2=new Date();
System.out.println("Time cost:"+(d2.getTime()-d1.getTime()));
// System.out.println(Arrays.toString(arr));
// quick sort:
d1=new Date();
Quicksort.<Integer>sort(arr);
d2=new Date();
System.out.println("Time cost:"+(d2.getTime()-d1.getTime()));
// System.out.println(Arrays.toString(arr));
// Sun API
d1=new Date();
Arrays.sort(arr);
d2=new Date();
System.out.println("Time cost:"+(d2.getTime()-d1.getTime()));
// System.out.println(Arrays.toString(arr));
}
}
分享到:
相关推荐
快速排序QuickSort.java
然后定义了quickSort函数来实现快速排序算法。在main函数中,我们定义了一个数组并对其进行快速排序,并打印排序后的结果。 快速排序是一种高效的排序算法,它的实现相对简单但性能优秀。希望这个示例能帮助你理解...
日本程序员norahiko,写了一个排序算法的动画演示,非常有趣...目前,最常见的排序算法大概有七八种,其中"快速排序"(Quicksort)使用得最广泛,速度也较快。它是图灵奖得主C. A. R. Hoare(1934--)于1960时提出来的
快速排序是20世纪十大算法之一,可见其精妙之处,相较于其他复杂度为O(n^2),可以提高到n*logn.一般我们研究快速排序基本采用内置类型,如int型数据,本类为了更通用,采用了模板类,具体数据对象类型可根据用户自己...
下面小编就为大家带来一篇Java快速排序QuickSort(实例)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧
本文实例讲述了PHP快速排序quicksort。分享给大家供大家参考,具体如下: quicksort 在快速排序算法中,使用了分治策略。首先把序列分成两个子序列,递归地对子序列进行排序,直到整个序列排序结束。(即一分为二的...
很好aospiupdoaspdasdasdsadasd
资源名:quicksort_matlab_快速排序 资源类型:matlab项目全套源码 源码说明: 全部项目源码都是经过测试校正后百分百成功运行的,如果您下载后不能运行可联系我进行指导或者更换。 适合人群:新手及有一定经验的...
快速排序(Quicksort)的Javascript实现 快速排序(Quicksort)是一种高效的排序算法,由图灵奖得主C. A. R. Hoare于1960年提出。该算法的思想很简单,整个排序过程只需要三步:(1)在数据集之中,选择一个元素...
快速排序源代码,采用C++编写,经测试未发现BUG,供大家参考
void quicksort(int A[],int p,int r) { int q; if(p) { q=partition(A,p,r); quicksort(A,p,q-1); quicksort(A,q+1,r); } } /****************************************************/
分治法的应用,快速排序是其中一种。注释便于读者明白。
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(n log n) 算法更快,因为...
分治法的另外一种排序算法,快速排序。有注释,便于阅读,因为交换时使用的引用,暂时归为C++,C语言版稍后奉上。
PHP_基于php实现的快速排序算法_QuickSort
用分治的思想模拟快速排序的迭代过程,快速排序平均运行时间可以和Heapsort媲美
QuickSort快速排序的实现 [Qsort类] 使用C++模版,可实现自定义类型的排序方式 同时通过折半查找检索元素 附带控制台演示 欢迎指正和建议 程序详细描述可见:...
C# 快速排序源码, 包含调用方式和注释,QuickSort.cs ///调用方式 /// /// int[] arr = new int[] { 5,3,9,6,4,7,8,1,2}; /// QuickSort.quickSort(arr, 0, arr.Length - 1); /// ///
快速排序 快速排序(Quicksort)是一种常见的、高效的排序算法,它基于分治(Divide and Conquer)的思想