Evaluating the efficiency and performance of Java Quick Sort

Performance Analysis and Comparison of Java Quick Sort

Quick Sort (Quick Sort) is a comparison-based sorting algorithm, because of its fast execution speed and better performance performance and is widely used in actual development. This article will perform a performance analysis of the quick sort algorithm in Java and compare it with other common sorting algorithms.

1. Quick sorting algorithm principle
   Quick sorting adopts the idea of ​​divide and conquer method. By dividing the data to be sorted into two independent parts, the left and right subsequences are recursively sorted respectively, so as to achieve The entire sequence is ordered. The specific algorithm steps are as follows:
   1) Select an axis value (Pivot) from the array, usually the first element of the array.
   2) Divide the array into left and right subsequences through one pass of sorting, so that the elements in the left subsequence are less than or equal to the axis value, and the elements in the right subsequence are greater than the axis value.
   3) Quick sort the left and right subsequences recursively until the sequence length is 1 or 0.
   4) Finally get the sorted sequence.
2. Quick sort implementation in Java
   The following is a sample code to implement quick sort in 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));
  }
}

3. Performance analysis and comparison
   In order to evaluate quick sort The performance of the algorithm, we compare it with several other common sorting algorithms. The following is a sample code that uses Java's System.nanoTime() method to calculate the algorithm execution time:

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) {
    // 省略快速排序的具体实现
  }
}

By running the above code, we can get the execution of each sorting algorithm time. According to experimental results, the quick sort algorithm is generally faster than bubble sort, insertion sort, and selection sort, especially for sorting large-scale data sets. Of course, in some specific cases, the performance of other sorting algorithms may be better, so specific analysis of specific problems is performed and the most appropriate sorting algorithm is selected based on the actual situation.

Summary:
This article performs a performance analysis of the quick sort algorithm in Java and compares it with other common sorting algorithms. Through experimental results, we can conclude that quick sort is generally an efficient sorting algorithm, especially suitable for sorting large-scale data sets. However, for specific problems, we need to choose the most appropriate sorting algorithm based on the actual situation.

The above is the detailed content of Evaluating the efficiency and performance of Java Quick Sort. For more information, please follow other related articles on the PHP Chinese website!