Bagaimana untuk melaksanakan algoritma isihan pantas menggunakan java

Cara melaksanakan algoritma isihan pantas dalam Java

Isih Cepat ialah algoritma isihan yang biasa digunakan dan cekap. Idea asasnya ialah menggunakan strategi bahagi dan takluk (Divide and Conquer) Dengan memilih satu elemen pada satu masa sebagai nilai tanda aras, tatasusunan yang hendak diisih dibahagikan kepada dua bahagian, satu bahagian lebih kecil daripada nilai tanda aras, dan bahagian lain lebih besar daripada nilai penanda aras, dan kemudian dua bahagian dibahagikan kepada dua bahagian Lakukan pengisihan rekursif separa, dan akhirnya mencapai pengisihan keseluruhan tatasusunan.

Di bawah ini kami akan memperkenalkan secara terperinci cara melaksanakan algoritma isihan pantas menggunakan bahasa Java dan memberikan contoh kod khusus. . daripada nilai penanda aras, Elemen di bahagian kanan semuanya lebih besar daripada nilai penanda aras;

Isih bahagian kiri dan kanan dengan cepat secara rekursif.

1. Contoh kod Java:

   • public class QuickSort {
         
         public static void main(String[] args) {
             int[] arr = {5, 7, 2, 9, 3, 6, 1, 8, 4};
             quickSort(arr, 0, arr.length - 1);
             printArray(arr);
         }
         
         public static void quickSort(int[] arr, int low, int high) {
             if (low < high) {
                 int pivotIndex = partition(arr, low, high);  // 将数组划分为两部分，获取基准值的位置
                 quickSort(arr, low, pivotIndex - 1);  // 递归排序基准值左边的部分
                 quickSort(arr, pivotIndex + 1, high);  // 递归排序基准值右边的部分
             }
         }
         
         public static int partition(int[] arr, int low, int high) {
             int pivot = arr[low];  // 选择数组的第一个元素作为基准值
             int left = low + 1;
             int right = high;
             
             while (true) {
                 while (left <= right && arr[left] < pivot) {  // 从左往右找到第一个大于或等于基准值的元素
                     left++;
                 }
                 while (left <= right && arr[right] > pivot) {  // 从右往左找到第一个小于或等于基准值的元素
                     right--;
                 }
                 if (left > right) {
                     break;  // 左右指针相遇时退出循环
                 }
                 swap(arr, left, right);  // 交换左右指针指向的元素
             }
             swap(arr, low, right);  // 将基准值放回正确的位置
             return right;  // 返回基准值的位置
         }
         
         public static void swap(int[] arr, int i, int j) {
             int temp = arr[i];
             arr[i] = arr[j];
             arr[j] = temp;
         }
         
         public static void printArray(int[] arr) {
             for (int num : arr) {
                 System.out.print(num + " ");
             }
             System.out.println();
         }
     }

   • Analisis prestasi:
Kerumitan masa: Purata kerumitan masa isihan pantas ialah O(nlogn), dalam kes yang paling teruk ialah O(n^2), dan dalam kes yang paling teruk ialah O(n^2). Dalam keadaan yang baik, ia adalah O(n);

3. Melalui pengenalan di atas, kami telah mempelajari cara menggunakan bahasa Java untuk melaksanakan algoritma isihan pantas, dan memahami idea asas, langkah dan analisis prestasinya. Isih pantas ialah algoritma pengisihan yang biasa digunakan yang boleh mengisih sebarang jenis data dengan cekap, dan amat sesuai untuk pengisihan data berskala besar.

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan algoritma isihan pantas menggunakan java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!