快速排序是一种排序算法,由东尼·霍尔所发展的,以平均性能来说,排序 n
个项目要Θ(n
log n
)次比较。然而,在最坏的性能下,它需要Θ(n
2
)次比较。一般来说,快速排序实际上明显地比其他Θ(n
log n
) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来,且在大部分真实世界的数据,可以决定设计的选择,减少所需时间的二次方项之可能性。
java代码:
import java.util.Comparator;
import java.util.Random;
public class Quicksort {
public static final Random RND = new Random();
private static void swap(Object[] array, int i, int j) {
Object tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
private static <E> int partition(E[] array, int begin, int end, Comparator<? super E> cmp) {
int index = begin + RND.nextInt(end - begin + 1);
E pivot = array[index];
swap(array, index, end);
for (int i = index = begin; i < end; ++ i) {
if (cmp.compare(array[i], pivot) <= 0) {
swap(array, index++, i);
}
}
swap(array, index, end);
return (index);
}
private static <E> void qsort(E[] array, int begin, int end, Comparator<? super E> cmp) {
if (end > begin) {
int index = partition(array, begin, end, cmp);
qsort(array, begin, index - 1, cmp);
qsort(array, index + 1, end, cmp);
}
}
public static <E> void sort(E[] array, Comparator<? super E> cmp) {
qsort(array, 0, array.length - 1, cmp);
}
}
详细讲解参考维基百科!
分享到:
相关推荐
C++排序算法之快速排序源码
C++排序算法之快速排序
数据结构排序算法之快速排序,可以再 vc6.0平台上直接运行,按照提示要求操作即可,希望对大家有所帮组……
选择排序 冒泡排序 插入排序 合并排序 快速排序算法原理及代码实现 不同排序算法时间效率的经验分析方法 验证理论分析与经验分析的一致性 当面临巨大数据量的排序的时候,还是优先选择合并排序算法和快速排序算法。...
1、熟悉快速排序的串行算法 2、熟悉快速排序的并行算法 3、实现快速排序的并行算法 3.2 实验环境及软件 单台或联网的多台PC机,Linux操作系统,MPI系统。 3.3实验内容 1、快速排序的基本思想 2、单处理机上快速...
1. 算法思想 选取一个基准值,将待排序数据分为左(小于基准值)右(大于基准值)两个区间,然后对两个分区的数据进行同样的循环操作,最后便可得到一组有序数据。...因此快速排序的平均时间复杂度为$O(n^
快速排序算法的基本思想是:随机选取数组中的一个值,将所要进行排序的数分为左右两个部分,其中一部分的所有数据都比另外一部分的数据小,然后将所分得的两部分数据进行同样的划分,重复执行以上的划分操作,直到...
舞动的排序算法 快速排序 通过动画演示快速排序,很好的学习,课程资源。
知道快速排序算法的思想,但是一直都没有动手写,今天写了下,发现还不是那么容易
快速排序的并行实现,提高效率。快速排序算法并行化的一个简单思想是,对每次划分过后所得到的两个序列分别使用两个处理器完成递归排序。
最快的排序算法 谁才是最强的排序算法:快速排序-归并排序-堆排序,排序算法数据结构
希尔排序,冒泡排序、快速排序递归排序,快速排序非递归排序,快速排序改进算法
快速排序算法快速排序算法快速排序算法快速排序算法快速排序算法
快速排序算法C语言实现,快排序算法QuickSort.cpp
用分治算法的思想,加上递归 实现快速排序
c语言版本的数据结构的快速排序算法,适用于新手学习
7大排序算法(快速排序,冒泡排序,选择排序,归并排序,插入排序,希尔排序,堆排序)实现源码
一个简单的算法效率对比,实验证明,快速排序的效率比冒泡的效率高出很多啊!
自己编写的基于java的快速排序和归并算法
详细解释了快速排序的java实现.里面有代码,还有注释说明