프론트 엔드의 정렬 알고리즘 예제에 대한 자세한 설명

이번에는 프론트엔드 정렬 알고리즘의 예를 자세히 설명하겠습니다. 프론트엔드에서 정렬 알고리즘을 사용할 때 주의사항은 무엇인가요? .

서문

어제 Zhihu에서 Ruan Yifeng 선생님의 빠른 정렬 알고리즘에 대해 불평하는 기사를 보았습니다. 여기에 여담을 추가하고 싶습니다. 책이 없는 것보다 배움의 과정 그것이 바로 실수를 끊임없이 발견하고 바로잡는 과정입니다. 끊임없이 배우고, 실수를 수정하고 성장하므로 모두가 똑같습니다. 오해의 소지가 있는 사람이 아니라 더 강력한 사람이 JavaScript라면 어떨까요? 누구나 실수를 할 수 있기 때문에 우리도 더 많이 생각하고 회의적인 태도로 이를 받아들이고 이것이 최선의 해결책인지 항상 생각해야 합니다. 저는 이것이 컴퓨터로서 해야 할 일이라고 생각합니다. 전문적인 프론트엔드인데 아이디어의 다양한 정렬 알고리즘을 잘 구현하지 못해서 너무 부끄럽기 때문에 C 언어설명 + 중국어 책을 천천히 읽어보았습니다. Version.pdf>> 아래에는 제가 이해한 다양한 아이디어의 정렬 알고리즘을 요약해 놓았습니다. 잘못된 점이 있으면 지적해 주시기 바랍니다. 자신이 더 좋다고 생각하는 아이디어는 모두가 함께 배우고 발전하는 것이 가장 행복한 것 같아요~

1. 꼭 알아두어야 할 관련 개념

1.1 시간 복잡도

(1) 시간의 개념 복잡성

알고리즘의 시간 복잡도는 알고리즘의 실행 시간을 정성적으로 설명하는 함수입니다. 이 함수의 하위 항과 고차 항 계수를 제외하면 일반적으로 사용됩니다.
(2) 계산 method

• 일반적으로 알고리즘에서 기본 연산의 실행 횟수는 문제 크기 n의 함수이며, T(n)으로 표현됩니다. 보조 함수 f(n)이 있으면 n이 무한대에 접근합니다. , T(n)/f(n)의 극한값은 0이 아닌 상수이고 f(n)은 T(n)과 동일한 크기 차수의 함수이며 T(n) = O(로 표시됩니다. f(n)), 우리는 알고리즘의 점근적 시간 복잡도를 O(f(n))이라고 부릅니다. 이를 시간 복잡도라고 합니다.

• 분석: 언제든지 모듈 n이 증가함에 따라 알고리즘의 성장률은 다음과 같습니다. 실행 시간은 f(n)의 증가율에 비례하므로 f(n)이 작을수록 알고리즘의 시간 복잡도는 낮아지고, 알고리즘의 효율성은 높아집니다.

• 시간 복잡도를 계산할 때, 먼저 알고리즘의 기본 연산을 알아낸 다음 기본 연산의 실행 횟수를 계산하고 T(n)과 동일한 크기의 f(n)을 찾습니다(동일한 크기의 크기는 일반적으로 다음과 같습니다. 1 , log2n,n,nlog2n,n 제곱, n의 세제곱), T(n) / f(n)이 상수 c를 얻기 위한 극한을 찾으면 시간 복잡도 T(n) = O(f(n) )):

예:

for(i = 1; i T(n) = n^3 + n^2를 얻을 수 있으며, n^3이 T(n), f( n)=n^3; 그러면 T(n) / f(n) = 1 + 1/n 한계는 상수 1이므로 이 알고리즘의 시간 복잡도는 다음과 같습니다.<p style="text-align: left;"> T(n) = O(n^3) ;<br></p><p style="text-align: left;">참고: 편의상 N을 사용하겠습니다. 다음은 배열 요소의 수를 나타냅니다.<strong></strong></p>2. 정렬 알고리즘<h1 style="text-align: left;"></h1>2.1 <h2 style="text-align: left;">버블 정렬<a href="http://www.php.cn/code/12106.html" target="_blank"></a>
</h2>2.1.1 주요 아이디어:<h3 style="text-align: left;"></h3>의 주요 아이디어 버블 정렬은 길이가 n인 배열을 순회하는 것입니다. i는 n-1부터 1까지이며 배열의 첫 번째 i 요소의 최대값은 i 위치에 배치됩니다. 순회 프로세스는 큰 값(무거운)이 계속 가라앉고, 작은 값(가벼운 값)이 계속 떠오르므로 순회가 완료된 후 각 위치의 값이 해당 값보다 커집니다. 이전 값을 입력하고 정렬이 완료됩니다.<p style="text-align: left;"></p>2.1.2 시간 복잡도<h3 style="text-align: left;"></h3>최악의 경우 시간 복잡도: o(n^2);<p style="text-align: left;">최상의 경우 시간 복잡도: o(n^2);<br></p>2.1 .3 정렬 프로세스 그림:<h3 style="text-align: left;"></h3><p style="text-align: left;">다이어그램의 루프 종료는 내부 루프를 종료하는 것입니다<strong> </strong><br><img src="https://img.php.cn/upload/article/000/061/021/975255cd4031086ad718d4dc21df07d0-0.png" alt="프론트 엔드의 정렬 알고리즘 예제에 대한 자세한 설명" title="프론트 엔드의 정렬 알고리즘 예제에 대한 자세한 설명"></p><h3   style="max-width:90%">2.1.4 代码实现:</h3><h4 style="text-align: left;">冒泡排序-非递归实现</h4><pre class="brush:php;toolbar:false">function bubbleSort(arr) {
    for(var i = arr.length - 1; i > 1; i--) {
        for(var j=0; j  arr[j+1]) {
                var temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
    return arr;
}
var arr =  [34,8,64,51,32,21];
bubbleSort(arr);  // [8, 21, 32, 34, 51, 64]

冒泡排序-递归实现

function bubbleSort(arr, n) {
    if(n  arr[j+1]) {
                var temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
        return bubbleSort(arr, --n);
    }
}
var arr =  [34,8,64,51,32,21];
bubbleSort(arr, arr.length);  // [8, 21, 32, 34, 51, 64]

2.2 插入排序

2.2.1 主要思想:

插入排序有 n-1 趟排序组成,对于 i=1 到 i=n-1 趟,内层循环j从 i 到 1, 如果这其中有 j-1 位置上的元素大于 i 位置上的元素,就将该元素后移,知道条件不成立退出循环,这个时候大的值都被移动到后面了,j这个位置就是i位置上的元素应该在的位置.这样保证了每次循环i位置前的所有元素都是排好序的,新的循环就只需要 将 i 位置上的元素 和 j-1(也就是初始的 i-1) 位置上的元素作比较,如果大于则无需再往前比较,如果小于则继续往前比较后移.

2.2.2 时间复杂度

最坏情况下的时间复杂度: o(n^2);
最好情况下的时间复杂度: o(n);

2.2.3 프론트 엔드의 정렬 알고리즘 예제에 대한 자세한 설명:

图解中的出循环是退出内层循环

2.2.4 代码实现

插入排序-非递归实现

function insertSort(arr) {
    var n = arr.length,temp = 0;
    for(var i = 1; i  0 && arr[j-1] > temp; j--) {
            arr[j] = arr[j - 1];
        }
        arr[j] = temp;
    }
    return arr;
}
var arr =  [34,8,64,51,32,21];
insertSort(arr);  // [8, 21, 32, 34, 51, 64]

插入排序-递归实现

function insertSort(arr, n) {
    if(n > 0 && n  0 && arr[j - 1] > temp) {
            arr[j] = arr[j - 1];
            j--;
        }
        arr[j] = temp;
        i++;
        return insertSort(arr, i);
    }
    return arr;
}
var arr =  [34,8,64,51,32,21];
insertSort(arr, 1); // [8, 21, 32, 34, 51, 64]; // 这个函数的调用限定了第一次调用n的值只能传1

2.3 快速排序

顾名思义,快速排序是在实践中最快的已知排序算法,它的平均运行时间是O(Nlog₂N).快速排序的关键在于枢纽元的选取,有一种比较推荐的选取方法就是选取左端的值,右端的值,中间位置的值(L(left + right) / 2)这三个数的中位数.举例: 输入为8,1,4,9,6,3,5,2,7,0, 左边元素8, 右边元素0,中间位置上的元素L(0+9)/2是4位置上的元素是6,L在表示向下取整.
8,0,6的中位数,先排序0,6,8, 这三个数的中位数是6.

2.3.1 基本思想

通过一趟排序将要排序的部分分割成独立的两部分,其中一部分数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据进行快速排序,整个排序过程可以递归进行,依次达到整个数据变成有序序列.

2.3.2 实现步骤

第一步: 设置两个变量i,j,排序开始的时候: i=left,j=right-1,left和right分别表示要进行快速排序序列的起始索引和结束索引;
第二步: 从数组中随机选取一个元素,将其与arr[left]进行交换,即privot = arr[left],保证每一次的基准值都在序列的最左边;
第三步: 由j开始向前搜索,即由后开始向前搜索(j--),找到第一个小于privot 的值arr[j],将arr[i]与arr[j]互换;
第四步: 从i开始向后搜索,即由前开始向后搜索(i++),找到一个大于privot 的arr[i],将arr[i]与arr[j]互换;
第五步: 重复第三步和第四步,直到不满足i第六步: 重复第二步到第四步,依次对i位置左右两边的元素进行快速排序,直到left大于等于right为止.

2.3.3 时间复杂度:

平均情况下的时间复杂度: o(nlog₂n);
最好情况下的时间复杂度: o(n);

2.3.4 프론트 엔드의 정렬 알고리즘 예제에 대한 자세한 설명

2.3.5 代码实现:

快速排序-递归实现

function quickSort(arr, left, right) {
    if(left >= right) return;
    var i = left;
    var j = right - 1;
    var privot = arr[left];
    //console.log(privot);
    while(i = privot) j--;
        arr[i] = arr[j];
        while(i<j var quicksort><h4 style="text-align: left;">快速排序-非递归实现</h4>
<pre class="brush:php;toolbar:false">function mainProduce(arr, left, right) {
        var i = left, j = right - 1;
        var rendomIndex = Math.floor(Math.random() * (j - i)) + left;
        var temp = arr[left];arr[left] = arr[rendomIndex];arr[rendomIndex] = temp;
        var privot = arr[left];
        while(i = privot) j--;
            var temp = arr[i];arr[i] = arr[j];arr[j] = temp;
            while(i<j> left + 1) {
                s.push(left);s.push(mid);
            }
            if(mid  left + 1) {
                    s.push(left);s.push(mid);
                }
                if(mid <h2 style="text-align: left;">2.4 希尔排序</h2>
<h3 style="text-align: left;">2.4.1 主要思想</h3>
<p style="text-align: left;">希尔排序是把记录按照下标的一定增量分组,对每组使用插入排序;随着增量逐渐减少,分割的数组越来越大,当增量减至1,整个<a href="http://www.php.cn/code/54.html" target="_blank">数组排序</a>完成,算法终止.</p>
<h3 style="text-align: left;">2.4.2主要步骤</h3>
<p style="text-align: left;">第一步: 选取一个增量d,初始值是Math.floor(len/2);<br>第二步: 然后将数组中间隔为增量d的组成新的分组,然后对这个分组的元素排序,完成排序后,增量除以2得到新的增量;<br>第三步: 重复第二步,直到增量为1,间隔为1的元素组成的分组就是整个数组,然后再对整个数组进行插入排序,得到最后排序后数组.</p>
<p style="text-align: left;">希尔排序是不稳定的,它在不断地交换的过程中会改变原来相等的元素的顺序.</p>
<h3 style="text-align: left;">2.4.3 时间复杂度</h3>
<p style="text-align: left;">平均情况下的时间复杂度: o(nlog₂n);<br>最好情况下的时间复杂度: o(n);</p>
<h3 style="text-align: left;">2.4.4 프론트 엔드의 정렬 알고리즘 예제에 대한 자세한 설명</h3>
<p style="text-align: left;"><img src="https://img.php.cn/upload/article/000/061/021/2f13ca0ab50333d1dad5851595e7225d-3.jpg" alt="프론트 엔드의 정렬 알고리즘 예제에 대한 자세한 설명" title="프론트 엔드의 정렬 알고리즘 예제에 대한 자세한 설명"></p>
<p style="text-align: left;">图片源于自百度百科: 图片来源</p>
<h3 style="text-align: left;">2.4.5 代码实现:</h3>
<h4 style="text-align: left;">希尔排序-递归实现</h4>
<pre class="brush:php;toolbar:false">function shellSort(arr, increment) {
    var len = arr.length;
    if(increment > 0) {
        for(var i = increment; i = 0 && arr[j] > arr[j + increment]; j -= increment) {
                    var temp = arr[j];
                    arr[j] = arr[j + increment];
                    arr[j + increment] = temp;
            }
        }
        return shellSort(arr, Math.floor(increment/2));
    }
     return arr; 
}
var arr = [49,38,65,97,76,13,27,49,55,04];
shellSort(arr, Math.floor(arr.length / 2));

希尔排序-非递归实现

function shellSort(arr) {
        var len = arr.length;
        for(var increment = Math.floor(len / 2); increment > 0; increment = Math.floor(increment / 2)) {
                for(var i = increment; i = 0 && arr[j] > arr[j + increment]; j -= increment) {
                                var temp = arr[j];
                                arr[j] = arr[j + increment];
                                arr[j + increment] = temp;
                        }
                }
        }
        return arr;
}
var arr = [49,38,65,97,76,13,27,49,55,04];
shellSort(arr);

2.5 归并排序

2.5.1 主要思想

第一步: 将一个数组以中间值截取为为两个数组,分别将其排好序;
第二步: 申请一个空间,使其大小为两个已经排序的序列之和,该空间用来存放合并后的序列;
第三步: 设定两个指针,分别指向两个已排序序列的起始位置;
第四步: 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置.
重复第四步直到有一个某一指针超出序列尾;
将另一序列的所有元素复制到合并序列尾.
归并排序是稳定的,它在不会改变原来相等的元素的顺序.

2.5.2 时间复杂度

平均情况下的时间复杂度: O(nlog₂n);
最好情况下的时间复杂度: O(nlog₂n) ;

2.5.3 프론트 엔드의 정렬 알고리즘 예제에 대한 자세한 설명

2.5.4 代码实现:

归并排序-递归实现

var result = [];
function mergeArray(left, right) {
    result = [];
    while(left.length > 0 && right.length > 0) {
        if(left[0] <p>相信看了本文案例你已经掌握了方法，更多精彩请关注php中文网其它相关文章！</p><p>推荐阅读：</p><p><a href="http://www.php.cn/js-tutorial-398003.html" target="_blank">React结合TypeScript和Mobx步骤详解</a><br></p><p><a href="http://www.php.cn/js-tutorial-398045.html" target="_blank">react实现选中li高亮步骤详解</a><br></p>

위 내용은 프론트 엔드의 정렬 알고리즘 예제에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!