这一个算是一个比较完善的快速排序了吧,就是代码多了点,没办法,要想性能好,考虑的东西就得多点。
package sort;
public class QuickSort {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int n = 10000000;
int[] arr = new int[n];
for (int i = n; i > 0; i--) {
arr[i - 1] = i;
}
QuickSort q = new QuickSort(arr);
long now = System.currentTimeMillis();
q.sort();
System.out.println("time="+(System.currentTimeMillis() - now));
//q.display();
}
private int[] arr;
public QuickSort(int[] arr){
this.arr = arr;
}
public void display(){
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
public void sort(){
recQuickSort(0,arr.length - 1);
}
private void recQuickSort(int left,int right){
int size = right - left + 1;
if(size < 10){
//小于10的小数组可以用插入排序,比较省事
insertSort(left,right);
}else{
int maddie = getMiddleValue(left,right);
//获取最平均的枢纽值
int partition = partitionIt(left,right,maddie);
recQuickSort(left,partition - 1);
recQuickSort(partition + 1,right);
}
}
/**将指定范围内的数据用枢纽值切割成两个部分,
* 枢纽值做为分界,在枢纽值左边的全部小于它,右边全部大于它
* @param left 左边索引
* @param right 右边索引
* @param privot 枢纽值
* @return
*/
private int partitionIt( int left, int right, int privot) {
int leftPtr = left;
int rightPtr = right - 1;
while(true){
//左边第二个数据(第一个数据已经在getMiddleValue方法里排好序,肯定比枢纽值小)和枢纽值比较,碰到小于枢纽值的数据停止比较
while(arr[++leftPtr] < privot);
//右边第三个数据和枢纽值比较(右边第一个在getMiddleValue方法里排序肯定比枢纽值大,第二个是枢纽值本身,都不用比较)
while(arr[--rightPtr] > privot);
//指针交叉停止比较
if(leftPtr >= rightPtr){
break;
}else{
//将左边小于枢纽值的数据和右边大于枢纽值的数据交换
swap(leftPtr,rightPtr);
}
}
//将枢纽值放到边界处(此时该枢纽值已经处于最终排序的位置,也就是说它不需要再移动了)
swap(leftPtr,right - 1);
return leftPtr;
}
/**获取比较平均的枢纽值(这在逆序的情况下很有用)
* 分别取最左,中间,最右三个值,取当中的中间值作为枢纽值,并对它们排序
* @param left
* @param right
* @return
*/
private int getMiddleValue( int left, int right) {
int middle = (left + right)/2;
if(arr[left] > arr[middle])
swap(left,middle);
if(arr[left] > arr[right])
swap(left,right);
if(arr[middle] > arr[right])
swap(middle,right);
//中间值和最右边倒数第二个值交换,这样的话最右边和其左边第一个都不用参加和枢纽值的比较,因为他们是大于等于的。
swap(middle,right - 1);
return arr[right - 1];
}
/**交换元素
* @param a
* @param b
*/
private void swap(int a,int b){
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
/**插入排序
* @param left
* @param right
*/
private void insertSort(int left,int right){
int out,inner,temp;
for (out = left + 1 ; out < right; out++) {
temp = arr[out];
inner = out;
while(inner > left && arr[inner - 1] >= temp){
arr[inner] = arr[inner - 1];
inner--;
}
arr[inner] = temp;
}
}
}
100w逆序排序耗时28毫秒。比希尔快一点哦。付出的是复杂的算法和大量的代码。看如何取舍咯。
分享到:
相关推荐
2、熟练使用高级编程语言实现不同的快速排序算法。 3、利用实验测试给出不同快速排序算法的性能以理解其优缺点。 快速排序是算法导论中的经典算法。在本实验中,给定一个长为 n 的整数数 组,要求将数组升序排序。
源码中含有多个快速排序算法的类。而且还可以比较它们的排序速度。
高级排序 数据结构 归并排序,堆排序,希尔排序,快速排序
易语言高级表格各列同步排序源码,高级表格各列同步排序,自动编号,填充随机数据,高级表格排序,设置排序方向,快速排序
这份资源提供了Java中如何实现快速排序的全面指南。文档中涵盖了快速排序的基本概念,包括如何对数组进行排序以及如何在Java中实现快速排序。此外,文档还包括一个逐步指南,介绍了如何在Java中实现快速排序,包括...
高级排序算法 归并排序 归并排序改进 归并排序自底向上 快速排序 随机化快速排序 双路快速排序 三路快速排序 堆和堆排序 堆的基本存储 ShiftUp ShiftDown 基础堆排序和Heapify 优化的堆排序 索引堆(IndexHeap) 索引...
易语言超级列表框排序模块例程源码例程程序结合易语言扩展界面支持库,调用易语言超级列表框单列排序.ec模块,可以对数值型、文本型、时间型、逻辑性的数据进行排序。本易语言源码例程属于易语言初级教程。资源作者...
内容涵盖快速排序的定义、四种实现方法(选择第一个数字、选择中间的数字、选择第一个和最后一个数字的平均值、随机选择一个数字)、优化技巧(三数取中法、尾递归优化、缓存优化)以及实战应用、变体、挑战和乐趣等...
通过实验,帮助学生由浅入深地掌握各种简单排序和高级排序的基本思想,让他们比较其性能,也让他们更好地理解希尔排序和快速排序的方法。 1.任意输入一个数组并利用简单选择排序算法对此数组的元素按从大到小的顺序...
本文实例讲述了JS排序算法之希尔排序与快速排序实现方法。分享给大家供大家参考,具体如下: 希尔排序: 定义一个间隔序列,例如是5,3,1。第一次处理,会处理所有间隔为5的,下一次会处理间隔为3的,最后一次处理...
算法导论及算法设计与分析(高级版)的程序
一、实验目的 1、掌握排序的不同方法,并能用高级语言实现排序算法 二、实验内容 2、实现快速和堆排序算法。(可选作)
排序算法是一种基本并且常用的算法。... 第四部分是我送给大家的一个餐后的甜点——一个基于模板的通用快速排序。由于是模板函数 可以对任何数据类型排序(抱歉,里面使用了一些论坛专家的呢称)。
快速排序 归并排序 希尔排序掌握常用的排序方法,并掌握用高级语言实现排序算法的方法; 深刻理解排序的定义和各种排序方法的特点,并能加以灵活应用; 了解各种方法的排序过程及其依据的原则,并掌握各种排序方法...
该文档涵盖了数组排序的基本概念,包括如何实现各种排序算法,如冒泡排序、选择排序、插入排序、归并排序和快速排序。此外,文档还为每个排序算法提供了详细的代码示例和实现细节。 该文档还涵盖了高级主题,如如何...
(1) 首先产生包含 1,000,000 个随机数(数据类型可选整型或者浮点型)的数据文件 (2) 每次数据分割后产生两个新的进程(或线程)处理分割后的数据,每
第二部分是高级排序算法,复杂度为O(Log2(N))。这里我们只介绍一种算法。另外还有几种算法因为涉及树与堆的概念,所以这里不于讨论。 第三部分类似动脑筋。这里的两种算法并不是最好的(甚至有最慢的),但是算法...
本资源包含了一系列精心编写的C和C++源码示例,旨在帮助开发者更好地理解和掌握这两种语言的核心概念和高级特性。这些源码覆盖了从基础语法到数据结构、算法实现等多个方面,适合不同水平的开发者学习和参考。 适用...
C++ 基数排序 大家好,今天带来的是自己...高级一些的有快速排序,希尔排序,堆排序,归并排序,基数排序等. 其中时间复杂度为O(n*logn)的算法有快速排序,归并排序和堆排序等,其中快速排序的使用最为广泛.时间复杂度为O
对于数据表的查询操作,由简单的单表查询,到多表查询,分组查询,模糊查询,排序,起别名等 3. 数据库高级部分,视图,索引,触发器,存储过程,事务,安全管理,数据库备份与还原等 阅读建议:无论你是MySQL数据...