Idées algorithmiques pour implémenter le tri rapide en JavaScript

Cet article présente principalement les idées algorithmiques sur JavaScript pour implémenter un tri rapide. Il a une certaine valeur de référence. Maintenant, je le partage avec vous. Les amis dans le besoin peuvent s'y référer

Actuellement, le tri le plus courant. L'algorithme est probablement Il en existe sept ou huit types, parmi lesquels le « tri rapide » est le plus largement utilisé et le plus rapide. Il a été proposé par Tony Hall (C. A. R. Hoare), lauréat du prix Turing, en 1960.

L'idée du tri rapide est très simple. L'ensemble du processus de tri ne nécessite que trois étapes :

(1) Dans l'ensemble de données, sélectionnez un élément comme "pivot". 🎜 >

(2) Tous les éléments plus petits que "base" sont déplacés vers la gauche de "base" ; tous les éléments plus grands que "base" sont déplacés vers la droite de "base"

(3). ) Pour les deux sous-ensembles à gauche et à droite de la "ligne de base", répétez les première et deuxième étapes jusqu'à ce qu'il ne reste plus qu'un seul élément dans tous les sous-ensembles

Par exemple, il existe maintenant un ensemble de données {85 ,. 24, 63, 45, 17, 31, 96, 50}, comment les trier ?

La première étape consiste à sélectionner l'élément du milieu 45 comme "base" (la valeur de base peut être arbitraire. Choisissez, mais il est plus facile de comprendre de choisir la valeur médiane)

La deuxième étape consiste à comparer chaque élément avec la "ligne de base" afin de former deux sous-ensembles, l'un est "inférieur à 45", et l'autre "supérieur ou égal à 45".

La troisième étape consiste à répéter la première et la deuxième étapes pour les deux sous-ensembles jusqu'à ce qu'il n'y en ait qu'un seul. élément restant dans tous les sous-ensembles Jusqu'à présent

Suivez les étapes précédentes et définissez une fonction quickSort :

var quickSort = function(arr) { //参数是一个数组
　　if (arr.length <= 1) { return arr; } //检查数组的元素个数，如果小于等于1，就返回。
　　var pivotIndex = Math.floor(arr.length / 2); //选择"基准"（pivot），并将其与原数组分离，再定义两个空数组，用来存放一左一右的两个子集。
　　var pivot = arr.splice(pivotIndex, 1)[0];
　　var left = [];
　　var right = [];
　　for (var i = 0; i < arr.length; i++){ //开始遍历数组，小于"基准"的元素放入左边的子集，大于基准的元素放入右边的子集。
　　　　if (arr[i] < pivot) {
　　　　　　left.push(arr[i]);
　　　　} else {
　　　　　　right.push(arr[i]);
　　　　}
　　}
　　return quickSort(left).concat([pivot], quickSort(right));
};

Pour implémenter l'animation ci-dessus :

Idée d'algorithme :

1. Sélectionnez un élément de la séquence, appelé le "pivot" ;

   <🎜 ; >

Réorganisez le tableau de sorte que tous les éléments plus petits que la valeur de base soient placés devant la ligne de base et que tous les éléments plus grands que la valeur de base soient placés derrière la ligne de base (le même nombre peut aller de chaque côté) . Une fois cette partition terminée, la ligne de base sera placée au milieu du tableau. C'est ce qu'on appelle une opération de partition
trie de manière récursive le sous-tableau d'éléments plus petits que la valeur de base. le sous-tableau d'éléments supérieur à la valeur de base ;
Code d'implémentation :

Ce qui précède est l'intégralité du contenu de cet article. J'espère qu'il sera utile. à l'étude de tout le monde. Pour plus de contenu connexe, veuillez faire attention au site Web PHP chinois

function quickSort(arr, left, right) { 
　　var len = arr.length,
　　partitionIndex,
　　left = typeof left != 'number' ? 0 : left,
　　right = typeof right != 'number' ? len - 1 : right;
 
 
　　if (left < right) {
　　partitionIndex = partition(arr, left, right);
　　quickSort(arr, left, partitionIndex-1);
　　quickSort(arr, partitionIndex+1, right);
　　}
　　return arr;
}
function partition(arr, left ,right) { // 分区操作
　　var pivot = left,                // 设定基准值（pivot）
　　　　index = pivot + 1;
　　for (var i = index; i <= right; i++) {
　　　　if (arr[i] < arr[pivot]) {
　　　　　　swap(arr, i, index);
　　　　　　index++;
　　　　}
　　}
　　swap(arr, pivot, index - 1);
　　 return index-1;
}
 
function swap(arr, i, j) {
　　var temp = arr[i];
　　arr[i] = arr[j];
　　arr[j] = temp;
}
function partition2(arr, low, high) {
　　let pivot = arr[low];
　　while (low < high) {
　　　　while (low < high && arr[high] > pivot) {
　　　　--high;
　　　　}
　　　　arr[low] = arr[high];
　　　　while (low < high && arr[low] <= pivot) {
　　　　++low;
　　　　}
　　　　arr[high] = arr[low];
　　}
　　arr[low] = pivot;
　　return low;
}
 
function quickSort2(arr, low, high) {
　　if (low < high) {
　　let pivot = partition2(arr, low, high);
　　quickSort2(arr, low, pivot - 1);
　　quickSort2(arr, pivot + 1, high);
　　}
　　return arr;
}

Recommandations associées :

Comment trier aléatoirement les tableaux js

js déplace n'importe quel élément vers une position spécifiée

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!