如何使用快速排序算法对整数数组进行就地排序？-Toy模板网

这篇具有很好参考价值的文章主要介绍了如何使用快速排序算法对整数数组进行就地排序？。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

快速排序是什么

快速排序算法是最常用的排序算法之一，尤其是对大型列表进行排序时，大多数编程语言、库都以一种或另一种方式实现了它。在 Java 中，Arrays.sort()方法使用由 Joshua Bloch 等人编写的双枢轴快速排序算法对原始数据类型进行排序。这种实现为大量数据集提供了更好的性能，传统的快速排序算法降低了二次性能。此方法还使用另一种很好的排序算法 MergeSort来对对象进行排序。C++ STL 库中也提供了快速排序实现。

为什么选择快速排序

你有没有想过为什么快速排序如此受欢迎？

1、它是我们拥有的最快的排序算法之一。平均而言，快速排序是一种 O(n log n) 算法，而最坏的情况是 O(n^2)，与冒泡排序或插入排序相比要好得多。

2、排序发生在同一个数组中，不需要额外的内存。

3、快速排序在对大量数字列表进行排序时非常高效，因为它不需要额外的内存，是一种非常节省空间的排序算法。快速排序也是一种自然递归算法，

如何实现快速排序

快速排序算法的实现步骤:

1. 从列表或数组中选择一个元素，称为基准值。基准值通常是数组的中间元素。

2. 重新排序列表，使所有值小于基准值的元素位于基准值之前，所有值大于基准值的元素位于基准值之后(相等的元素可以从两个方向排列)。这也称为分区。分区后，基准值就到了它的最终位置。

3.递归地将上述步骤应用于值较小的元素的子列表，并分别应用于值较大的元素的子列表。如果数组只包含一个元素或零个元素，则该数组是有序的。

import java.util.Arrays;

/**
 * Test class to sort array of integers using Quicksort algorithm in Java.
 * @author Javin Paul
 */
public class QuickSortDemo{

    public static void main(String args[]) {

        // unsorted integer array
        int[] unsorted = {6, 5, 3, 1, 8, 7, 2, 4};
        System.out.println("Unsorted array :" + Arrays.toString(unsorted));

        QuickSort algorithm = new QuickSort();

        // sorting integer array using quicksort algorithm
        algorithm.sort(unsorted);

        // printing sorted array
        System.out.println("Sorted array :" + Arrays.toString(unsorted));

    }

}

/**
 * Java Program sort numbers using QuickSort Algorithm. QuickSort is a divide
 * and conquer algorithm, which divides the original list, sort it and then
 * merge it to create sorted output.
 *
 * @author Javin Paul
 */
class QuickSort {

    private int input[];
    private int length;

    public void sort(int[] numbers) {

        if (numbers == null || numbers.length == 0) {
            return;
        }
        this.input = numbers;
        length = numbers.length;
        quickSort(0, length - 1);
    }

    /*
     * This method implements in-place quicksort algorithm recursively.
     */
    private void quickSort(int low, int high) {
        int i = low;
        int j = high;

        // pivot is middle index
        int pivot = input[low + (high - low) / 2];

        // Divide into two arrays
        while (i <= j) {
            /**
             * As shown in above image, In each iteration, we will identify a
             * number from left side which is greater then the pivot value, and
             * a number from right side which is less then the pivot value. Once
             * search is complete, we can swap both numbers.
             */
            while (input[i] < pivot) {
                i++;
            }
            while (input[j] > pivot) {
                j--;
            }
            if (i <= j) {
                swap(i, j);
                // move index to next position on both sides
                i++;
                j--;
            }
        }

        // calls quickSort() method recursively
        if (low < j) {
            quickSort(low, j);
        }

        if (i < high) {
            quickSort(i, high);
        }
    }

    private void swap(int i, int j) {
        int temp = input[i];
        input[i] = input[j];
        input[j] = temp;
    }
}

Output :

Unsorted array :[6, 5, 3, 1, 8, 7, 2, 4]

Sorted array :[1, 2, 3, 4, 5, 6, 7, 8]

文章来源地址https://www.toymoban.com/news/detail-429855.html

到了这里，关于如何使用快速排序算法对整数数组进行就地排序？的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！