詳解Java中使用泛型實現(xiàn)快速排序算法的方法
更新時間：2016年05月04日 15:52:21 作者：飛翔的貓咪
這篇文章主要介紹了Java中使用泛型實現(xiàn)快速排序算法的方法,快速排序的平均時間復雜度為(n\log n),文中的方法立足于基礎而并沒有考慮優(yōu)化處理,需要的朋友可以參考下
快速排序算法概念
快速排序一般基于遞歸實現(xiàn)。其思路是這樣的：
1.選定一個合適的值（理想情況中值最好，但實現(xiàn)中一般使用數(shù)組第一個值）,稱為“樞軸”(pivot)。
2.基于這個值，將數(shù)組分為兩部分，較小的分在左邊，較大的分在右邊。
3.可以肯定，如此一輪下來，這個樞軸的位置一定在最終位置上。
4.對兩個子數(shù)組分別重復上述過程，直到每個數(shù)組只有一個元素。
5.排序完成。
基本實現(xiàn)方式：
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); //將數(shù)組分為兩部分
qsort(arr, low, pivot-1); //遞歸排序左子數(shù)組
qsort(arr, pivot+1, high); //遞歸排序右子數(shù)組
}
}
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;
}
使用泛型實現(xiàn)快排算法
下面設計一個QuickSort類，包含了靜態(tài)函數(shù)sort()，可以對任意類型數(shù)組進行排序。如果為對象類型數(shù)組，則該對象類型必須實現(xiàn)Comparable接口，這樣才能使用compareTo函數(shù)進行比較。
使用了最基本的快排算法，沒有進行優(yōu)化處理。
源代碼如下：
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Random;
public class QuickSort {
@SuppressWarnings("unchecked")
//對上述快排函數(shù)原型修改，使其可以對任意對象類型數(shù)組進行排序。這個函數(shù)為內部使用，外部排序函數(shù)接口為sort()，sort函數(shù)要求對象必須實現(xiàn)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++) {
//該對象類型數(shù)組必須實現(xiàn)Comparable接口，這樣才能使用compareTo函數(shù)進行比較
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;
}
//使用泛型，對任意對象數(shù)組排序，該對象類型數(shù)組必須實現(xiàn)Comparable接口
public static <T extends Comparable<? super T>> void sort(T[] input){
quickSort(input,0,input.length);
}
//添加對List對象進行排序的功能，參考了Java中的Java.util.Collections類的sort()函數(shù)
public static <T extends Comparable<? super T>> void sort(List<T> list){
Object[] t = list.toArray();//將列表轉換為數(shù)組
quickSort(t,0,t.length); //對數(shù)組進行排序
//數(shù)組排序完成后再寫回到列表中
ListIterator<T> i = list.listIterator();
for (int j=0; j<t.length; j++) {
i.next();
i.set((T)t[j]);
}
}
//由于Java中原始數(shù)據類型（int、double、byte等）無法使用泛型，所以只能使用函數(shù)重載機制實現(xiàn)對這些原始類型數(shù)組（int[]、double[]、byte[]等）的排序。這里為了共用同一個排序函數(shù)，利用原始類型的(AutoBoxing，UnBoxing)機制將其封裝為對應對象類型，組成新的對象數(shù)組，排序后再解封裝，這樣的缺點是需要額外的轉換步驟、額外的空間保存封裝后的數(shù)組。另一種方式是將排序代碼復制到各個重載函數(shù)中，官方API中的Java.util.Arrays這個類中的sort()函數(shù)就是使用這種方法，可以從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[]數(shù)組的重載函數(shù)
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[]數(shù)組的重載函數(shù)
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[]數(shù)組的重載函數(shù)
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[]數(shù)組的重載函數(shù)
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[]數(shù)組的重載函數(shù)
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函數(shù)
public static void main(String[] args) {
//生產一個隨機數(shù)組成的int[]數(shù)組，用來測試
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();
//生成一個字符串數(shù)組，用來測試
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函數(shù)測試，從輸出可以看出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
相關文章
SpringCloud?Feign?傳輸Date類型參數(shù)存在誤差的問題
這篇文章主要介紹了SpringCloud?Feign?傳輸Date類型參數(shù)存在誤差的問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-03-03
這篇文章主要介紹了POI通用導出Excel(.xls,.xlsx)的方法，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2019-05-05
這篇文章主要介紹了SpringMVC方法返回值多種情況代碼實例,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-09-09
這篇文章主要介紹了SpringBoot2.0整合WebSocket代碼實例,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2019-11-11
這篇文章主要為大家分享了最有價值的三道關于算法的面試題，涵蓋內容全面，包括數(shù)據結構和算法相關的題目、經典面試編程題等，感興趣的小伙伴們可以參考一下2021-08-08
詳解基于SpringBoot使用AOP技術實現(xiàn)操作日志管理
這篇文章主要介紹了詳解基于SpringBoot使用AOP技術實現(xiàn)操作日志管理，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2019-11-11
java實現(xiàn)獲取網站的keywords，description
這篇文章主要介紹了java實現(xiàn)獲取網站的keywords，description的相關資料,需要的朋友可以參考下2015-03-03
本文主要介紹Java 生成二維碼的幾種方法，這里給大家詳細介紹了java生成二維碼的三種工具，并附有示例代碼供大家參考，開發(fā)java 二維碼的朋友可以參考下2016-08-08
本篇文章主要介紹了Java實現(xiàn)簡單的緩存方法實例，需要的朋友可以參考下2017-04-04
這篇文章主要介紹了詳解設計模式在Spring中的應用(9種)，詳細的介紹了這9種模式在項目中的應用，具有一定的參考價值，感興趣的可以了解一下2019-04-04