Menilai kecekapan dan prestasi Java Quick Sort

Analisis prestasi dan perbandingan Java Quick Sort

Quick Sort (Quick Sort) ialah algoritma pengisihan berasaskan perbandingan yang digunakan secara meluas dalam pembangunan sebenar kerana kelajuan pelaksanaannya yang pantas dan prestasi yang baik. Artikel ini akan melakukan analisis prestasi algoritma isihan pantas dalam Java dan membandingkannya dengan algoritma isihan biasa yang lain. . tujuan menyusun keseluruhan urutan. Langkah algoritma khusus adalah seperti berikut:

1) Pilih nilai paksi (Pivot) daripada tatasusunan, biasanya elemen pertama tatasusunan.

2) Bahagikan tatasusunan kepada urutan kiri dan kanan melalui satu laluan pengisihan, supaya unsur-unsur dalam urutan kiri adalah kurang daripada atau sama dengan nilai paksi, dan unsur-unsur dalam urutan kanan lebih besar daripada nilai paksi.
1. 3) Isih pantas urutan kiri dan kanan secara rekursif sehingga panjang jujukan ialah 1 atau 0.
   4) Akhirnya dapatkan urutan yang disusun.
   
   Pelaksanaan Isih Pantas dalam Java
   Berikut ialah contoh kod untuk melaksanakan Isih Pantas dalam Java:
   

public class QuickSort {
  public static void quickSort(int[] arr, int low, int high) {
    if (low < high) {
      int pivotIdx = partition(arr, low, high);
      quickSort(arr, low, pivotIdx - 1);
      quickSort(arr, pivotIdx + 1, high);
    }
  }
  
  private static int partition(int[] arr, int low, int high) {
    int pivot = arr[low];
    int i = low + 1;
    int j = high;
    
    while (i <= j) {
      if (arr[i] <= pivot) {
        i++;
      } else if (arr[j] > pivot) {
        j--;
      } else {
        swap(arr, i, j);
      }
    }
    
    swap(arr, low, j);
    
    return j;
  }
  
  private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
  
  public static void main(String[] args) {
    int[] arr = {5, 2, 9, 1, 3, 7};
    quickSort(arr, 0, arr.length - 1);
    System.out.println(Arrays.toString(arr));
  }
}

2. 
   Analisis dan Perbandingan Prestasi
Untuk menilai prestasi algoritma Isih Pantas, kami membandingkannya dengan beberapa algoritma pengisihan biasa yang lain Bandingkan. Di bawah ialah contoh kod yang menggunakan kaedah

Java untuk mengira masa pelaksanaan algoritma:

3. import java.util.Arrays;
   
   public class SortComparison {
     public static void main(String[] args) {
       int[] arr = generateArray(10000);
       
       long startTime = System.nanoTime();
       bubbleSort(arr.clone());
       long endTime = System.nanoTime();
       System.out.println("Bubble Sort: " + (endTime - startTime) + " ns");
       
       startTime = System.nanoTime();
       insertionSort(arr.clone());
       endTime = System.nanoTime();
       System.out.println("Insertion Sort: " + (endTime - startTime) + " ns");
       
       startTime = System.nanoTime();
       selectionSort(arr.clone());
       endTime = System.nanoTime();
       System.out.println("Selection Sort: " + (endTime - startTime) + " ns");
       
       startTime = System.nanoTime();
       quickSort(arr.clone(), 0, arr.length - 1);
       endTime = System.nanoTime();
       System.out.println("Quick Sort: " + (endTime - startTime) + " ns");
     }
     
     private static int[] generateArray(int size) {
       int[] arr = new int[size];
       for (int i = 0; i < size; i++) {
         arr[i] = (int)(Math.random() * size);
       }
       return arr;
     }
     
     private static void bubbleSort(int[] arr) {
       // 省略冒泡排序的具体实现
     }
     
     private static void insertionSort(int[] arr) {
       // 省略插入排序的具体实现
     }
     
     private static void selectionSort(int[] arr) {
       // 省略选择排序的具体实现
     }
     
     private static void quickSort(int[] arr, int low, int high) {
       // 省略快速排序的具体实现
     }
   }

   
   Dengan menjalankan kod di atas, kita boleh mendapatkan masa pelaksanaan setiap algoritma pengisihan. Mengikut keputusan percubaan, algoritma isihan pantas biasanya lebih pantas daripada isihan gelembung, isihan sisipan dan isihan pemilihan, terutamanya untuk mengisih set data berskala besar. Sudah tentu, dalam beberapa kes tertentu, prestasi algoritma pengisihan lain mungkin lebih baik, jadi analisis khusus masalah khusus dilakukan dan algoritma pengisihan yang paling sesuai dipilih berdasarkan situasi sebenar. System.nanoTime()Ringkasan:

Artikel ini menjalankan analisis prestasi algoritma isihan pantas dalam Java dan membandingkannya dengan algoritma isihan biasa yang lain. Melalui keputusan percubaan, kita boleh membuat kesimpulan bahawa isihan pantas secara amnya merupakan algoritma pengisihan yang cekap, terutamanya sesuai untuk mengisih set data berskala besar. Walau bagaimanapun, untuk masalah tertentu, kita perlu memilih algoritma pengisihan yang paling sesuai berdasarkan situasi sebenar.

Atas ialah kandungan terperinci Menilai kecekapan dan prestasi Java Quick Sort. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!