JavaScriptは挿入ソートを実現します.

1412 ワード

一、並べ替えの紹介を挿入する:
私達が地主と闘うことを想像して、段階を触って、手の札はすべて小さい時から大きい順に並べます.カードを触るたびに、彼を適当な位置に挿入します.後ろの位置のカードより小さくて、前の位置のカードより大きいです.
このような並べ替え方法は、挿入順序です.1つの配列aにおいて、私たちは昇順順序を達成したいです.もしa[0]からa[k]に対して順を並べたと仮定して、a[k+1]の値を適切な位置に入れる必要があります.
(簡便なために、ここではkの取値範囲については説明しません.配列のある位置を表しています.)
1、まず、a[k+1]の値をa[k]と比較し、a[k]以下であれば両者の値を交換し、等しいか大きいかは交換する必要がない.交換したとすると、a[k]は元のa[k+1]の値であり、新しいa[k]の値は前の位置の値より小さい可能性があるので、a[k]とa[k-1]を再度比較して、これらを類推する必要がある.ある位置a[p](pは0からkの間の数)の値がa[p-1]の値より小さくないことが分かり、比較が終了し、a[k+1]の値が適切な位置a[p]に入れられました.またはa[k+1]の値が前の値よりも小さくなり、一歩ずつ交換した後、a[0]はもとのa[k+1]の値が格納されました.これでも秩序化されます.
2、a[k+1]の後a[k+2]からa[a.length-1]までの各要素は順次同じ操作を行い、最終的には秩序のある配列を得る.
二、JavaScriptは挿入順序を実現する.
 function insertion_sort(arr) { 
            var temp;
            for (var i = 1; i < arr.length; i++) {
                for (var j = i-1; j >=0; j--) {
                    if (arr[j+1]=arr[j]) {
                        break;
                    }
                }
            }
            return arr;
        }
        var a=[11,2,3,445,7,32,71,8,94];
        console.log(insertion_sort(a));
        var b=[94,11];
        console.log(insertion_sort(b));
説明:1、arr[j+1]の値が前の値より小さくないことが発見されると、内部層の循環が終了し、breakはこの機能を実現する.
2、内層循環用arr[j+1]の理由:初期時a[j](a[i-1])はa[i]の前の位置を表し、循環に入るとa[i+1]の位置を表し、a[i]とa[i-1]の初めての比較を実現した.jが初めて減少するにつれて、実際にa[i-1]とa[i-2]の位置を比較した.