快速排序算法概念
快速排序一般基于递归实现。其思路是这样的:
1.选定一个合适的值(理想情况中值最好,但实现中一般使用数组第一个值),称为“枢轴”(pivot)。
2.基于这个值,将数组分为两部分,较小的分在左边,较大的分在右边。
3.可以肯定,如此一轮下来,这个枢轴的位置一定在最终位置上。
4.对两个子数组分别重复上述过程,直到每个数组只有一个元素。
5.排序完成。
基本实现方式:
public static void quickSort(int[] arr){ qsort(arr, 0, arr.length-1); } private static void qsort(int[] arr, int low, int high){ if (low=pivot) --high; arr[low]=arr[high]; //交换比枢轴小的记录到左端 while (low
使用泛型实现快排算法
下面设计一个QuickSort类,包含了静态函数sort(),可以对任意类型数组进行排序。如果为对象类型数组,则该对象类型必须实现Comparable接口,这样才能使用compareTo函数进行比较。
使用了最基本的快排算法,没有进行优化处理。
源代码如下:
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( ; bbegin){ quickSort(in,begin, a); } if( end-1 > a ) { quickSort(in,a, end); } return; } //使用泛型,对任意对象数组排序,该对象类型数组必须实现Comparable接口 public static > void sort(T[] input){ quickSort(input,0,input.length); } //添加对List对象进行排序的功能,参考了Java中的Java.util.Collections类的sort()函数 public static > void sort(List list){ Object[] t = list.toArray();//将列表转换为数组 quickSort(t,0,t.length); //对数组进行排序 //数组排序完成后再写回到列表中 ListIterator i = list.listIterator(); for (int j=0; j l = new LinkedList (); s = new String[]{"b","a","e","d","f","c"}; System.out.print("LinkedList before sorting: "); for (int j=0; j after sorting: "); for (String ts : l) { System.out.print(ts + " "); } System.out.println(); } }
运行main函数测试,从输出可以看出QuickSort类工作正常:
int[] 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 LinkedListbefore sorting: b a e d f c LinkedList after sorting: a b c d e f