快速排序算法概念
快速排序一般基于递归实现。其思路是这样的：
1.选定一个合适的值（理想情况中值最好，但实现中一般使用数组第一个值）,称为“枢轴”(pivot)。
2.基于这个值，将数组分为两部分，较小的分在左边，较大的分在右边。
3.可以肯定，如此一轮下来，这个枢轴的位置一定在最终位置上。
4.对两个子数组分别重复上述过程，直到每个数组只有一个元素。
5.排序完成。
基本实现方式：
使用泛型实现快排算法
立即学习
“
Java免费学习笔记（深入）
”；
下面设计一个QuickSort类，包含了静态函数sort()，可以对任意类型数组进行排序。如果为对象类型数组，则该对象类型必须实现Comparable接口，这样才能使用compareTo函数进行比较。
使用了最基本的快排算法，没有进行优化处理。
源代码如下：
运行main函数测试，从输出可以看出QuickSort类工作正常：
更多详解Java中使用泛型实现快速排序算法的方法相关文章请关注PHP中文网！
public static void quickSort(int[] arr){
qsort(arr, 0, arr.length-1);
}
private static void qsort(int[] arr, int low, int high){
if (low < high){
int pivot=partition(arr, low, high); //将数组分为两部分
qsort(arr, low, pivot-1); //递归排序左子数组
qsort(arr, pivot+1, high); //递归排序右子数组
}
}
private static int partition(int[] arr, int low, int high){
int pivot = arr[low]; //枢轴记录
while (low=pivot) --high;
arr[low]=arr[high]; //交换比枢轴小的记录到左端
while (low import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Random;
public class QuickSort {
@SuppressWarnings("unchecked")
//对上述快排函数原型修改，使其可以对任意对象类型数组进行排序。这个函数为内部使用，外部排序函数接口为sort()，sort函数要求对象必须实现Comparable接口，可以提供编译时类型检测，见后文。
private static void quickSort(Object[] in,int begin, int end) {
if( begin == end || begin == (end-1) ) return;
Object p = in[begin];
int a = begin +1;
int b = a;
for( ; b < end; b++) {
//该对象类型数组必须实现Comparable接口，这样才能使用compareTo函数进行比较
if( ((Comparableint[] before sorting: 65 48 92 26 3 8 59 21 16 45
int[] after sorting: 3 8 16 21 26 45 48 59 65 92
String[] before sorting: b a e d f c
String[] after sorting: a b c d e f
LinkedList before sorting: b a e d f c
LinkedList after sorting: a b c d e f