Java言語で実装されたクイックソートアルゴリズム

Java 言語に基づくクイック ソート アルゴリズムの実装方法

クイック ソートは、大量のデータをソートするためによく使用される効率的なソート アルゴリズムです。この記事では、Java言語に基づくクイックソートアルゴリズムの実装方法と具体的なコード例を紹介します。

クイックソートの基本的な考え方は、ソート対象のデータを独立した2つの部分に分割することです。たとえば、1つの要素を基準値として、その値より小さい要素を左側に配置し、値より大きい要素は左側、右側に配置されます。次に、シーケンス全体がソートされるまで、これら 2 つの部分を別々にすばやくソートします。

まず、データを分割する Partition 関数を実装する必要があります。この関数は、ピボットを選択する (通常はシーケンス内の最初の要素を選択する) ことによってシーケンス全体を 2 つの部分に分割し、ピボットの位置を返します。具体的なコードは次のとおりです。

public class QuickSort {
    public int partition(int[] array, int low, int high) {
        int pivot = array[low]; // 选择第一个元素作为Pivot
        while (low < high) {
            while (low < high && array[high] >= pivot) {
                high--;
            }
            array[low] = array[high]; // 将小于Pivot的元素移到左边

            while (low < high && array[low] <= pivot) {
                low++;
            }
            array[high] = array[low]; // 将大于Pivot的元素移到右边
        }
        array[low] = pivot; // 将Pivot放到正确的位置
        return low; // 返回Pivot的位置
    }
}

次に、シーケンス全体を並べ替える QuickSort 関数を実装する必要があります。具体的なコードは次のとおりです。

public class QuickSort {
    // ... 上面的代码省略 ...

    public void quickSort(int[] array, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(array, low, high); // 划分序列
            quickSort(array, low, pivotIndex - 1); // 对左边序列进行快速排序
            quickSort(array, pivotIndex + 1, high); // 对右边序列进行快速排序
        }
    }
}

最後に、QuickSort クラスを使用して整数配列を並べ替えることができます。具体的なコードは次のとおりです。

public class Main {
    public static void main(String[] args) {
        int[] array = {5, 2, 6, 3, 1, 4}; // 待排序的数组

        QuickSort quickSort = new QuickSort();
        quickSort.quickSort(array, 0, array.length - 1); // 对数组进行快速排序

        System.out.print("排序结果：");
        for (int i : array) {
            System.out.print(i + " ");
        }
    }
}

上記は、Java 言語に基づいたクイック ソート アルゴリズムを実装するメソッドです。 Partition 関数と QuickSort 関数を実装すると、整数配列をすばやく並べ替えることができます。このアルゴリズムの時間計算量は O(nlogn) で、非常に効率的な並べ替えアルゴリズムです。

以上がJava言語で実装されたクイックソートアルゴリズムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。