コミュニティ 学ぶ ツールライブラリ レジャー
検索
日本語
ホームページ > Java > ＆＃＆チュートリアル > 本文

ジェネリックスを使用して Java でクイックソートアルゴリズムを実装する方法の詳細な説明

高洛峰
リリース： 2017-01-19 09:19:05
オリジナル
1159 人が閲覧しました

クイック ソート アルゴリズムの概念
クイック ソートは通常、再帰的実装に基づいています。考え方は次のとおりです:
1. 「ピボット」と呼ばれる適切な値を選択します (理想的には中央値が最適ですが、実装では通常、配列の最初の値が使用されます)。
2. この値に基づいて、配列を 2 つの部分に分割し、小さい方を左側に、大きい方を右側に配置します。
3. このラウンドの後、このピボットの位置が最終位置にあることを確認できます。
4. 各配列の要素が 1 つだけになるまで、2 つのサブ配列に対して上記のプロセスを繰り返します。
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;
}
ログイン後にコピー

ジェネリックを使用してクイックソートアルゴリズムを実装します

以下は、任意の型の配列をソートできる静的関数sort()を含むQuickSortクラスです。オブジェクト型の配列の場合、compareTo 関数を比較に使用できるように、オブジェクト型は Comparable インターフェイスを実装する必要があります。

最も基本的なクイックソートアルゴリズムが最適化なしで使用されます。

ソースコードは次のとおりです: 

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
ログイン後にコピー

ジェネリックを使用して実装する方法の詳細な説明については、 Java のクイック ソート アルゴリズムについては、PHP 中国語 Web サイトの関連記事に注目してください。


関連ラベル：
Java 快速排序
ソース：php.cn
前の記事：Java でクイックソートアルゴリズムの QuickSort を実装する方法の図による説明 次の記事：Hill ソート アルゴリズムと関連する Java コード実装の詳細な解釈
このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
著者別の最新記事
最新の問題
React の状態が正しい順序でマッピングされない Redux を使用した Next.js プロジェクトがあります。私のストアには、Redux リデューサーを介して更新される一連の状態があります。基本的には、いくつかのコンポーネント...
から 2024-03-31 09:23:01
0
1
323
関連トピック
詳細>
人気のおすすめ
人気のチュートリアル
詳細>
関連するチュートリアル
人気のおすすめ
最新のコース
最新のダウンロード
詳細>
ウェブエフェクト
公式サイト
サイト素材
フロントエンドテンプレート