详解Java中使用泛型实现快速排序算法的方法
程序员文章站
2024-03-11 21:10:49
快速排序算法概念
快速排序一般基于递归实现。其思路是这样的:
1.选定一个合适的值(理想情况中值最好,但实现中一般使用数组第一个值),称为“枢轴”(pivot)。
2...
快速排序算法概念
快速排序一般基于递归实现。其思路是这样的:
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 < 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<high){ while (low<high && arr[high]>=pivot) --high; arr[low]=arr[high]; //交换比枢轴小的记录到左端 while (low<high && arr[low]<=pivot) ++low; arr[high] = arr[low]; //交换比枢轴小的记录到右端 } //扫描完成,枢轴到位 arr[low] = pivot; //返回的是枢轴的位置 return 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( ; b < end; b++) { //该对象类型数组必须实现comparable接口,这样才能使用compareto函数进行比较 if( ((comparable<object>)in[b]).compareto(p) < 0) { if(a == b){a++; continue;} object temp = in[a]; in[a] = in[b]; in[b] = temp; a++; } } in[begin] = in[a-1]; in[a-1] = p; if( a-1 > begin){ quicksort(in,begin, a); } if( end-1 > a ) { quicksort(in,a, end); } return; } //使用泛型,对任意对象数组排序,该对象类型数组必须实现comparable接口 public static <t extends comparable<? super t>> void sort(t[] input){ quicksort(input,0,input.length); } //添加对list对象进行排序的功能,参考了java中的java.util.collections类的sort()函数 public static <t extends comparable<? super t>> void sort(list<t> list){ object[] t = list.toarray();//将列表转换为数组 quicksort(t,0,t.length); //对数组进行排序 //数组排序完成后再写回到列表中 listiterator<t> i = list.listiterator(); for (int j=0; j<t.length; j++) { i.next(); i.set((t)t[j]); } } //由于java中原始数据类型(int、double、byte等)无法使用泛型,所以只能使用函数重载机制实现对这些原始类型数组(int[]、double[]、byte[]等)的排序。这里为了共用同一个排序函数,利用原始类型的(autoboxing,unboxing)机制将其封装为对应对象类型,组成新的对象数组,排序后再解封装,这样的缺点是需要额外的转换步骤、额外的空间保存封装后的数组。另一种方式是将排序代码复制到各个重载函数中,官方api中的java.util.arrays这个类中的sort()函数就是使用这种方法,可以从arrays类的源代码看出。 public static void sort(int[] input){ integer[] t = new integer[input.length]; for(int i = 0; i < input.length; i++){ t[i] = input[i];//封装 } quicksort(t,0,t.length);//排序 for(int i = 0; i < input.length; i++){ input[i] = t[i];//解封装 } } //double[]数组的重载函数 public static void sort(double[] input){ double[] t = new double[input.length]; for(int i = 0; i < input.length; i++){ t[i] = input[i]; } quicksort(t,0,t.length); for(int i = 0; i < input.length; i++){ input[i] = t[i]; } } //byte[]数组的重载函数 public static void sort(byte[] input){ byte[] t = new byte[input.length]; for(int i = 0; i < input.length; i++){ t[i] = input[i]; } quicksort(t,0,t.length); for(int i = 0; i < input.length; i++){ input[i] = t[i]; } } //short[]数组的重载函数 public static void sort(short[] input){ short[] t = new short[input.length]; for(int i = 0; i < input.length; i++){ t[i] = input[i]; } quicksort(t,0,t.length); for(int i = 0; i < input.length; i++){ input[i] = t[i]; } } //char[]数组的重载函数 public static void sort(char[] input){ character[] t = new character[input.length]; for(int i = 0; i < input.length; i++){ t[i] = input[i]; } quicksort(t,0,t.length); for(int i = 0; i < input.length; i++){ input[i] = t[i]; } } //float[]数组的重载函数 public static void sort(float[] input){ float[] t = new float[input.length]; for(int i = 0; i < input.length; i++){ t[i] = input[i]; } quicksort(t,0,t.length); for(int i = 0; i < input.length; i++){ input[i] = t[i]; } } //测试用的main函数 public static void main(string[] args) { //生产一个随机数组成的int[]数组,用来测试 int len = 10; int[] input = new int[len]; random r = new random(); system.out.print("int[] before sorting: "); for(int i = 0; i < input.length; i++) { input[i] = r.nextint(10*len); system.out.print(input[i] + " "); } system.out.println(); system.out.print("int[] after sorting: "); sort(input); for(int i : input) { system.out.print(i + " "); } system.out.println(); //生成一个字符串数组,用来测试 string[] s = new string[]{"b","a","e","d","f","c"}; system.out.print("string[] before sorting: "); for(int i = 0; i < s.length; i++) { system.out.print(s[i] + " "); } system.out.println(); system.out.print("string[] after sorting: "); sort(s); for(int i = 0; i < s.length; i++) { system.out.print(s[i] + " "); } system.out.println(); //生成一个字符串列表,用来测试 list<string> l = new linkedlist<string>(); s = new string[]{"b","a","e","d","f","c"}; system.out.print("linkedlist<string> before sorting: "); for (int j=0; j<s.length; j++) { l.add(s[j]); system.out.print(s[j] + " "); } system.out.println(); sort(l); system.out.print("linkedlist<string> 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 linkedlist<string> before sorting: b a e d f c linkedlist<string> after sorting: a b c d e f