Explication détaillée du tri par comparaison et du tri rapide

Le tri rapide (tri rapide en abrégé) est souvent testé dans les questions d'examen écrit en raison de sa grande efficacité (O(nlogn) moyen).

La première étape pour un tri rapide est de sélectionner une "base", qui servira à comparer et échanger avec d'autres numéros. Le choix de cette "base" affectera l'efficacité du tri rapide, mais si vous choisissez la base pour le plaisir de choisir la base, cela mettra la charrue avant les boeufs. Par exemple, pour trouver la base optimale, vous devez trouver la médiane dans toute la séquence à trier, mais trouver la médiane est en réalité très coûteux. Le choix de la base porte généralement sur le premier objet, l'objet du milieu ou le dernier objet de la séquence à trier. Cet article prend comme exemple la sélection du premier élément pour faire une brève analyse et mise en œuvre du tri rapide.

En prenant comme exemple la colonne à trier {6, 5, 3, 1, 7, 2, 4}, sélectionnez le premier élément 6 comme base.

Après avoir sélectionné la base, vous devez comparer et échanger avec les éléments du tableau. Comment comparer et avec qui comparer ? La deuxième étape du tri rapide consiste à définir une "sentinelle" sur le premier élément et le dernier élément du tableau.

Après avoir sélectionné la base et réglé la sentinelle, l'étape suivante consiste à lancer la comparaison Placer la base avec la. la dernière sentinelle j est comparée en premier, et si elle est supérieure à la sentinelle j, elle est échangée avec la sentinelle i+1.

A ce moment, la base n'est plus comparée à la sentinelle j, mais à la sentinelle i. Si la base est supérieure à la sentinelle i, la sentinelle recule jusqu'à ce qu'elle le soit. supérieur à la base. Jusqu'à présent, la sentinelle j-1 est échangée en même temps.

Répétez les étapes ci-dessus et comparez la base avec sentinelle j.

Le résultat final montre que la position de la sentinelle i = la position de la sentinelle j A ce moment, la valeur de base est attribuée à cette position.

De cette façon, les nombres du côté gauche de la base 6 sont tous plus petits que lui, et les nombres du côté droit sont tous supérieurs à lui. pour effectuer les mêmes étapes sur les tableaux gauche et droit pour sélectionner la base et définir Sentinel, le tri peut être terminé à la fin.

　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)

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!