比較ソートとクイックソートの詳細説明

クイックソート（略してクイックソート）は、その効率性（平均O(nlogn)）の高さから筆記試験問題でよく試される。

素早い並べ替えの最初のステップは、他の数値との比較や交換に使用される「ベース」を選択することです。 この「拠点」の選択はクイックソートの効率を左右しますが、拠点を選ぶために拠点を選んでしまうと本末転倒です。たとえば、最適な塩基を見つけるには、並べ替える配列全体の中央値を見つける必要がありますが、中央値を見つけるのは実際には非常にコストがかかります。通常、ベースの選択は、ソートされるシーケンス内の最初のオブジェクト、中央のオブジェクト、または最後のオブジェクトです。この記事では、最初の要素の選択を例として、簡単な分析とクイック ソートの実装を説明します。

ソート対象の列 {6, 5, 3, 1, 7, 2, 4} を例として、最初の要素 6 をベースとして選択します。

ベースを選択した後、配列要素を比較して交換する必要があります。どのように比較するのか、誰と比較するのか? クイックソートの 2 番目のステップは、配列の最初の要素と最後の要素に「センチネル」を設定することです。

ベースを選択してセンチネルを設定したら、次のステップは比較を開始することです。最初にベースと最後のセンチネル j を比較し、それがセンチネル j より大きい場合は、それと交換します。同時にセンディネル i+1 。

このとき、ベースはセンチネル j ではなくセンチネル i と比較されます。ベースがセンチネル i より大きい場合、センチネルはベースより大きくなるまで後方に移動し、センチネル j-1 と比較されます。も同時に交換されます。

上記の手順を繰り返して、ベースをセンチネルjと比較します。

最終的な結果は、センチネル i の位置 = センチネル j の位置を示します。このとき、ベース値はこの位置に割り当てられます。

このように、基数 6 の左側の数値はすべてそれより小さく、右側の数値はすべてそれより大きくなります。次に、再帰を使用して左右で同じ手順を実行します。配列を使用してベースを選択し、セントリーを設定し、最後に並べ替えを完了します。

Java

 1 package com.algorithm.sort.quick; 2  3 import java.util.Arrays; 4  5 /** 6  * 快速排序 7  * Created by yulinfeng on 2017/6/26. 8  */ 9 public class Quick {10     public static void main(String[] args) {11         int[] nums = {6, 5, 3, 1, 7, 2, 4};12         nums = quickSort(nums, 0, nums.length - 1);13         System.out.println(Arrays.toString(nums));14     }15     16     /**17      * 快速排序18      * @param nums 待排序数组序列19      * @param left 数组第一个元素索引20      * @param right 数组最后一个元素索引21      * @return 排好序的数组序列22      */23     private static int[] quickSort(int[] nums, int left, int right) {24         if (left < right) {25             int temp = nums[left];    //基数26             int i = left;    //哨兵i27             int j = right;    //哨兵j28             while (i < j) {29                 while (i < j && nums[j] >= temp) {30                     j--;31                 }32                 if (i < j) {33                     nums[i] = nums[j];34                     i++;35                 }36                 while (i < j && nums[i] < temp) {37                     i++;38                 }39                 while (i < j) {40                     nums[j] = nums[i];41                     j--;42                 }43             }44             nums[i] = temp;45             quickSort(nums, left, i - 1);46             quickSort(nums, i + 1, right);47         }48         return nums;49     }50 }

Python3

 1 #快速排序 2 def quick_sort(nums, left, right): 3     if left < right: 4         temp = nums[left]    #基数 5         i = left    #哨兵i 6         j = right    #哨兵j 7         while i < j: 8             while i < j and nums[j] >= temp: 9                 j -= 110             if i < j:11                 nums[i] = nums[j]12                 i += 113             while i < j and nums[i] < temp:14                 i += 115             if i < j:16                 nums[j] = nums[i]17                 j -= 118         nums[i] = temp19         quick_sort(nums, left, i - 1)20         quick_sort(nums, i + 1, right)21     22     return nums23 24 nums = [6, 5, 3, 1, 7, 2, 4]25 nums = quick_sort(nums, 0, len(nums) - 1)26 print(nums)

以上が比較ソートとクイックソートの詳細説明の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。