이 글은 빠른 정렬을 구현하기 위한 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 != '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; }위 내용은 모두의 학습에 도움이 되기를 바랍니다. . 더 많은 관련 내용은 PHP 중국어 홈페이지를 참고해주세요! #🎜 🎜#
관련 추천:
#🎜🎜 #
위 내용은 JavaScript에서 빠른 정렬을 구현하기 위한 알고리즘 아이디어의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!