package com.tnt.sortingalgorithm;
import java.util.Comparator;
import java.util.Random;
/**
* 快速排序
*
* @author Frankco
*
*/
public class Quicksort {
public static final Random RND = new Random();
/**
* swap译为:交换
* @param array
* @param i
* @param j
*/
private static void swap(Object[] array, int i, int j) {
Object tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
/**
* Comparable和Comparator的区别?
* Comparable适合用于将实体对象排序
* @param <E>
* @param array
* @param begin
* @param end
* @param cmp
* @return
*/
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);
}
/**
* 递归
* @param <E>
* @param array
* @param begin
* @param end
* @param cmp
*/
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);
}
/**
* 测试
* @param args
*/
public static void main(String[] args) {
Integer[] arr = { 11, 52, 6, 8, 3, 4, 5, 7, 4, 6, 69, 8, 2, 5, 5, 2, 4,
2 };
sort(arr, new Comparator<Integer>() {
public int compare(Integer a, Integer b) {
if (a > b)
return 1;
else if (a < b)
return -1;
else
return 0;
}
});
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
}
分享到:
相关推荐
快速排序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实现
快速排序源代码,采用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)的思想