집 >웹 프론트엔드 >JS 튜토리얼 >JavaScript에서 빠른 정렬을 구현하기 위한 알고리즘 아이디어

JavaScript에서 빠른 정렬을 구현하기 위한 알고리즘 아이디어

不言원래의: 2018-07-11 09:16:391281검색

이 글은 빠른 정렬을 구현하기 위한 JavaScript에 대한 알고리즘 아이디어를 주로 소개합니다. 이제는 도움이 필요한 친구들이 참고할 수 있도록 공유합니다.

현재 common 정렬 알고리즘은 7~8개 정도 있는데, 그 중 "Quicksort"가 가장 널리 사용되고 더 빠릅니다. 1960년 튜링상 수상자 Tony Hall(C.A.R. Hoare)이 제안했습니다.

"빠른 정렬"의 아이디어는 매우 간단합니다. 전체 정렬 프로세스에는 세 단계만 필요합니다.

　(1) 데이터 세트에서 요소를 다음과 같이 선택합니다. "pivot" )

　(2) "base"보다 작은 모든 요소는 "base"의 왼쪽으로 이동되고 "base"보다 큰 모든 요소는 "base"의 오른쪽으로 이동됩니다. #🎜🎜. #

　(3) 모든 하위 집합에 요소가 하나만 남을 때까지 "기준선"의 왼쪽과 오른쪽에 있는 두 하위 집합에 대해 첫 번째와 두 번째 단계를 반복합니다. #예를 들어, 이제 데이터 세트 {85, 24, 63, 45, 17, 31, 96, 50}이 있습니다.

　단계는 중간값을 선택하는 것입니다. 요소 45를 "기준선"으로 사용합니다. (기준값은 임의로 선택할 수 있지만 중간값을 선택하면 이해하기 쉽습니다.) 요소는 "기준선"과 비교됩니다. 두 개의 하위 집합을 형성하려면 하나는 "45보다 작음"이고 다른 하나는 "45보다 크거나 같음"입니다. 모든 하위 집합에 요소가 하나만 남을 때까지 하위 집합에 대해 첫 번째와 두 번째 단계가 반복됩니다.

# 🎜🎜#

이전 단계에 따라 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));
};

. 위 애니메이션을 구현하세요:

#🎜 🎜#

알고리즘 아이디어: #🎜🎜 #

"피벗"이라는 요소를 선택합니다. 더 작은 값은 베이스 앞에 배치되고, 베이스보다 큰 값을 가진 모든 요소는 베이스 뒤에 배치됩니다(같은 숫자는 양쪽으로 갈 수 있음). 이 파티션이 종료된 후 베이스는 중앙에 있습니다. 이것을 파티션(파티션) 작업이라고 합니다.

기본 값보다 작은 요소의 하위 배열을 반복적으로 정렬합니다. 기본 값;

#🎜 🎜#

구현 코드:

function quickSort(arr, left, right) { 
　　var len = arr.length,
　　partitionIndex,
　　left = typeof left != &#39;number&#39; ? 0 : left,
　　right = typeof right != &#39;number&#39; ? 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;
}

위 내용은 모두의 학습에 도움이 되기를 바랍니다. . 더 많은 관련 내용은 PHP 중국어 홈페이지를 참고해주세요! #🎜 🎜#

JavaScript에서 빠른 정렬을 구현하기 위한 알고리즘 아이디어

관련 기사