ただし、これはソートアルゴリズムに関するものではなく、文字列比較方法に関するものです。 ここではすべてが簡単なように思えます-最初から最初の異なるキャラクターを比較してください。 そして、行に数字があれば？ 次に、このソート（ 辞書式 ）はシーケンス['file2'、 'file10'、 'file1']を['file1'、 'file10'、 'file2']に変換します。 しかし、人はテキストを読むときに数字を知覚し、同じシーケンスが直観的に順序付けられ、次のようになります：['file1'、 'file2'、 'file10']。 このようなソートは、自然ソートと呼ばれます。
カットの下-
ソートアルゴリズム自体は記述しませんが、組み込みのArray.sort（）メソッドを使用します。 したがって、「メイン関数」は次のようになります。
function naturalSort(stringArray) {
var arr = stringArray;
// ...
return arr.sort(compareStrings) //
}
文字列を比較するためにcompareStrings（）関数を記述することは残っています。 これはさまざまな方法で行うことができますが、私は次のアプローチを採用しました：行内のテキストから数値を分離し、結果の配列を同じインデックスを持つ行（または数値）の最初の違いに移動します。 splitString（）関数（それについては少し後で）は行を分離し、比較自体は次のようになります。
function compareStrings(str1, str2) {
//
var compare = function (a, b) {
return (a < b) ? -1 : (a > b) ? 1 : 0;
};
// ; splitString()
var parts1 = splitString(str1);
var parts2 = splitString(str2);
//
var minLength = Math.min(parts1.length, parts2.length);
for ( var i = 0; i < minLength; i++) {
//
}
//
// , "", , ""
return compare(parts1.length, parts2.length);
}
ただし、このアプローチではすべてがスムーズではありません：比較する必要があるほとんどの行は最初の文字とは異なります。つまり、splitString（）は多くの不要な作業を行います。 ただし、これは遅延計算を使用して修正できます。splitString（）は既製の配列ではなく、next（）およびcount（）メソッドを持つイテレータオブジェクトを返します。 JavaScriptのクロージャーのおかげで、実装はそれほど大きくありませんでした。
（投稿の最後にUPD ）
function splitString(str) {
var from = 0; // slice()
var index = 0; //
var count = 0; //
var splitter = {}; //
//
splitter.count = function () {
return count;
}
//
splitter.next = function () {
// - null
if (index === str.length) {
return null ;
}
//
while (++index) {
var currentIsDigit = isDigit(str.charAt(index - 1)); // isDigit()
var nextChar = str.charAt(index);
var currentIsLast = (index === str.length);
// - ,
// ( / )
var isBorder = currentIsLast ||
xor(currentIsDigit, isDigit(nextChar)); // xor()
if (isBorder) {
var part = str.slice(from, index);
from = index;
count++;
return {
IsNumber: currentIsDigit,
Value: currentIsDigit ? Number(part) : part
};
} // end if
} // end while
}; // end next()
return splitter;
}
補助関数-xor（）およびisDigit（）を作成します。
function xor(a, b) {
return a ? !b : b;
}
function isDigit(chr) {
var charCode = function (ch) {
return ch.charCodeAt(0);
};
var code = charCode(chr);
return (code >= charCode( '0' )) && (code <= charCode( '9' ));
}
次に、文字列比較関数compareStrings（）に戻ります。 イテレータの導入により、一般的なロジックはあまり変更されていません。
（投稿の最後にUPD ）
function compareStrings(str1, str2) {
//
var compare = function (a, b) {
return (a < b) ? -1 : (a > b) ? 1 : 0;
};
//
var splitter1 = splitString(str1);
var splitter2 = splitString(str2);
//
while ( true ) {
var first = splitter1.next();
var second = splitter2.next();
// ...
if ( null !== first && null !== second) {
// ( )
if (xor(first.IsNumber, second.IsNumber)) {
// ""
return first.IsNumber ? -1 : 1;
//
} else {
var comp = compare(first.Value, second.Value);
if (comp != 0) {
return comp;
}
} // end if
// ... - ""
} else {
return compare(splitter1.count(), splitter2.count());
}
} // end while
}
最後に、ソート関数を作成し、すべてをまとめてコードを「櫛」にします。
（投稿の最後にUPD ）
function naturalSort(stringArray) {
// ""
var xor = function (a, b) {
return a ? !b : b;
};
// ,
var isDigit = function (chr) {
var charCode = function (ch) {
return ch.charCodeAt(0);
};
var code = charCode(chr);
return (code >= charCode( '0' )) && (code <= charCode( '9' ));
};
//
var splitString = function (str) {
var from = 0; // slice()
var index = 0; //
var count = 0; //
var splitter = {}; //
//
splitter.count = function () {
return count;
}
//
splitter.next = function () {
// - null
if (index === str.length) {
return null ;
}
//
while (++index) {
var currentIsDigit = isDigit(str.charAt(index - 1));
var nextChar = str.charAt(index);
var currentIsLast = (index === str.length);
// - ,
// ( / )
var isBorder = currentIsLast ||
xor(currentIsDigit, isDigit(nextChar));
if (isBorder) {
var part = str.slice(from, index);
from = index;
count++;
return {
IsNumber: currentIsDigit,
Value: currentIsDigit ? Number(part) : part
};
} // end if
} // end while
}; // end next()
return splitter;
};
// ""
var compareStrings = function (str1, str2) {
//
var compare = function (a, b) {
return (a < b) ? -1 : (a > b) ? 1 : 0;
};
//
var splitter1 = splitString(str1);
var splitter2 = splitString(str2);
//
while ( true ) {
var first = splitter1.next();
var second = splitter2.next();
// ...
if ( null !== first && null !== second) {
// ( )
if (xor(first.IsNumber, second.IsNumber)) {
// ""
return first.IsNumber ? -1 : 1;
//
} else {
var comp = compare(first.Value, second.Value);
if (comp != 0) {
return comp;
}
} // end if
// ... - ""
} else {
return compare(splitter1.count(), splitter2.count());
}
} // end while
}
//
var arr = stringArray;
return arr.sort(compareStrings);
}
見つかったバグ、コードのヒント、提案に感謝します。 誰かが興味を持っていて、多分役に立つことを願っています。
UPD：
コメントの中で、 Alex_At_Netは改行の結果をキャッシュするのがいいだろうと述べ、すぐに行を断片に分割し、既成のフラグメントセットをソートすることを提案しました。 その結果、スクリプトの改訂版と拡張版が登場しました。 オプションの抽出パラメータがソート機能に追加されました-任意のオブジェクトを文字列に変換する機能：任意のオブジェクトの配列をソートできるようになりました。 入力配列はすぐにスプリッターの配列に変換されますが、分割自体は、インデックスによってフラグメントにアクセスする場合にのみ、適切な場所に1回だけ発生します。 next（）メソッドの代わりに、スプリッターには、インデックス（by index）によってフラグメントを返すpart（i）メソッドがあります。 コードはもう少し「くし」と「オブジェクト化」されています。 すべて次のようになります。
function naturalSort(array, extractor) {
"use strict" ;
//
var splitters = array.map(makeSplitter);
//
var sorted = splitters.sort(compareSplitters);
//
return sorted.map( function (splitter) {
return splitter.item;
});
//
function makeSplitter(item) {
return new Splitter(item);
}
//
// ""
function Splitter(item) {
var index = 0; //
var from = 0; //
var parts = []; //
var completed = false ; //
//
this .item = item;
// -
var key = ( typeof (extractor) === 'function' ) ?
extractor(item) :
item;
this .key = key;
//
this .count = function () {
return parts.length;
};
// ( parts[])
this .part = function (i) {
while (parts.length <= i && !completed) {
next(); //
}
return (i < parts.length) ? parts[i] : null ;
};
//
function next() {
//
if (index < key.length) {
//
while (++index) {
var currentIsDigit = isDigit(key.charAt(index - 1));
var nextChar = key.charAt(index);
var currentIsLast = (index === key.length);
// - ,
// ( / )
var isBorder = currentIsLast ||
xor(currentIsDigit, isDigit(nextChar));
if (isBorder) {
// parts[]
var partStr = key.slice(from, index);
parts.push( new Part(partStr, currentIsDigit));
from = index;
break ;
} // end if
} // end while
//
} else {
completed = true ;
} // end if
} // end next
//
function Part(text, isNumber) {
this .isNumber = isNumber;
this .value = isNumber ? Number(text) : text;
}
}
//
function compareSplitters(sp1, sp2) {
var i = 0;
do {
var first = sp1.part(i);
var second = sp2.part(i);
// ...
if ( null !== first && null !== second) {
// ( )
if (xor(first.isNumber, second.isNumber)) {
// ""
return first.isNumber ? -1 : 1;
//
} else {
var comp = compare(first.value, second.value);
if (comp != 0) {
return comp;
}
} // end if
// ... - ""
} else {
return compare(sp1.count(), sp2.count());
}
} while (++i);
//
function compare(a, b) {
return (a < b) ? -1 : (a > b) ? 1 : 0;
};
};
// ""
function xor(a, b) {
return a ? !b : b;
};
// :
function isDigit(chr) {
var code = charCode(chr);
return (code >= charCode( '0' )) && (code <= charCode( '9' ));
function charCode(ch) {
return ch.charCodeAt(0);
};
};
}
コメント付き
コメントなし
PS：
function thanks() {
alert( 'C PoiSoN Source Code Highlighter' );
};
* This source code was highlighted with Source Code Highlighter .