経典の並べ替えのアルゴリズムのjavascriptは実現します.
31648 ワード
並べ替えの安定性:等しいいくつかの要素は並べ替えの後で、その相対的な順序は不変である.並べ替えアルゴリズムは安定しているという.順序付けアルゴリズムが安定であるかどうかは具体的なアルゴリズムによって決定され、不安定なアルゴリズムはある条件で安定なアルゴリズムに変わることができ、安定したアルゴリズムはある条件で不安定なアルゴリズムにも変化することができる.安定した並べ替えアルゴリズム:泡立ち並べ替え、並べ替え、並べ替え、並べ替え、基数並べ替え、統計的な順序付けが不安定な並べ替えアルゴリズム:並べ替え、高速の並べ替え、ヒルの並べ替え、積み上げの並べ替えを選択します.
内部並べ替え:元のデータ構造上の要素の値を直接交換して並べ替えを行います.
アルゴリズムは数値要素の並べ替えにのみ適用され、いくつかのアルゴリズムは負の整数ではなく、または0より大きい整数にのみ適用されます.jsでundefinedの不等式演算はfalseに戻ります.そのため、いくつかの比較操作が実行される前に変数に初値を与えていません.配列の境界をチェックしていません.他のプログラミング言語に翻訳する時は注意が必要です.
アルゴリズムの説明は下記@kunを参照してください.http://www.cnblogs.com/kkun/archive/2011/11/23/2260312.html
addr: http://www.cnblogs.com/ecalf/archive/2013/04/15/3022193.htmlauthor: ecalf
誤りと欠陥があるところを指摘してほしい.
内部並べ替え:元のデータ構造上の要素の値を直接交換して並べ替えを行います.
アルゴリズムは数値要素の並べ替えにのみ適用され、いくつかのアルゴリズムは負の整数ではなく、または0より大きい整数にのみ適用されます.jsでundefinedの不等式演算はfalseに戻ります.そのため、いくつかの比較操作が実行される前に変数に初値を与えていません.配列の境界をチェックしていません.他のプログラミング言語に翻訳する時は注意が必要です.
アルゴリズムの説明は下記@kunを参照してください.http://www.cnblogs.com/kkun/archive/2011/11/23/2260312.html
addr: http://www.cnblogs.com/ecalf/archive/2013/04/15/3022193.htmlauthor: ecalf
誤りと欠陥があるところを指摘してほしい.
//
function BubbleSort(arr){
var swaped;
for(var i=0,l=arr.length;i<l;i++){
swaped = false;
for(var j=l-1;j>=i+1;j--){
if(arr[j]<arr[j-1]){
arr[j] = [arr[j-1],arr[j-1]=arr[j]][0];
swaped = true;
}
}
if(!swaped){ break; }
}
return arr;
}//
function InsertSort(arr){
var temp;
for(var i=1,l=arr.length;i<l;i++){
temp = arr[i];
for(var j=i;j>0;j--){
if(arr[j-1]>temp){
arr[j] = arr[j-1];
}else{
break;
}
}
arr[j] = temp;
}
return arr;
}//
function SelectSort(arr){
for(var i=0,l=arr.length;i<l-1;i++){
for(var j=i+1;j<l;j++){
if(arr[j]<arr[i]){
arr[i] = [arr[j],arr[j]=arr[i]][0];
}
}
}
return arr;
}//
function QuickSort(arr){
if(arr.length<=1){ return arr; }
var self = arguments.callee;
var left = [],right = [],middle=[];
var mid = arr[Math.floor(arr.length/2)];
for(var i=0;i<arr.length;i++){
if(arr[i]<mid){
left.push(arr[i])
}else if(arr[i]>mid){
right.push(arr[i]);
}else{
middle.push(arr[i]);
}
}
return [].concat(self(left),middle,self(right));
}// (2 )
function MergeSort(arr){
if(arr.length<=1){ return arr;}
var self = arguments.callee;
var mid = Math.floor(arr.length/2);
var left = self(arr.slice(0,mid));
var right = self(arr.slice(mid));
var result = [];
while(left.length&&right.length){
if(left[left.length-1]<=right[0]){
result = result.concat(left);
left = [];
}else if(right[right.length-1]<left[0]){
result = result.concat(right);
right = [];
}else{
if(right[0]<left[0]){
result.push(right.shift());
}else{
result.push(left.shift());
}
}
}
result = result.concat(left,right);
return result;
}// ( 10 ),
function RadixSort(arr,scale){
scale = scale||10;
var max = Math.max.apply(Math,arr);
var remMask=1,buckets=[],radix;
while(max>remMask){
for(var i=0;i<arr.length;i++){
radix = Math.floor(arr[i]/remMask)%scale;
if(!buckets[radix]){
buckets[radix] = [];
}
buckets[radix].push(arr[i]);
}
arr = [];
for(var k=0;k<buckets.length;k++){
if(buckets[k]){
arr = arr.concat(buckets[k]);
}
}
remMask *= scale;
}
return arr;
}// , ,
function BucketSort(arr){
var buckets = [];
for(var i=0;i<arr.length;i++){
buckets[arr[i]] = arr[i];
}
arr = [];
for(var i=0;i<buckets.length;i++){
if(buckets[i]!==undefined){
arr.push(buckets[i]);
}
}
return arr;
}// ,
function PigeonholeSort(arr){
var tempArr = [];
for(var i=0,l=arr.length;i<l;i++){
tempArr[arr[i]] = (tempArr[arr[i]]+1)||1 ;
}
var result = [],count;
for(var k=0;k<tempArr.length;k++){
count = tempArr[k];
if(count){
for(var i=0;i<count;i++){
result.push(k);
}
}
}
return result;
}// , fences： ， 1 ,such as [5,3,1]
function ShellSort(arr,fences){
var half = Math.floor(arr.length/2);
while(fences.length){
var fence = fences.shift();
if(fence>half){ continue; }
var tempArr = [];
while(arr.length){//
for(var i=0;i<fence&&arr.length;i++){
tempArr[i] = tempArr[i]||[];
tempArr[i].push(arr.shift());
}
}
for(var i=0;i<tempArr.length;i++){
//
for(var k=1,l=tempArr[i].length;k<l;k++){
var temp = tempArr[i][k];
for(var j=k;j>0;j--){
if(tempArr[i][j-1]>temp){
tempArr[i][j] = tempArr[i][j-1];
}else{
break;
}
}
tempArr[i][j] = temp;
}
}
arr = [].concat.apply([],tempArr);
}
return arr;
}// (2 )
function HeapSort(arr){
var findRoot = function(arr,p,length){
p = p||0;
length = length||arr.length;
var self = arguments.callee;
var l = p*2+1;
var r = (p+1)*2;
var left,right;
if(l<length){
left = self(arr,l,length);
}
if(r<length){
right = self(arr,r,length);
}
if(left>arr[p]){
arr[p] = [left,arr[l]=arr[p]][0];
}
if(right>arr[p]){
arr[p] = [right,arr[r]=arr[p]][0];
}
return arr[p];
};
for(var i=arr.length;i>0;i--){
findRoot(arr,0,i);
arr[i-1] = [arr[0],arr[0]=arr[i-1]][0];
}
return arr;
}//
function OddevenSort(arr){
var swaped = true,k=0;
while(swaped){
if(k>0){
swaped = false;
}
for(var i=k;i<arr.length-1;i+=2){
if(arr[i]>arr[i+1]){
arr[i] = [arr[i+1],arr[i+1]=arr[i]][0];
swaped = true;
}
}
k = [1,0][k];
}
return arr;
}//
function CocktailSort(arr){
var swaped = true;
var l=0,r=arr.length-1;
while(swaped){
swaped = false;
for(var i=l;i<=r;i++){
if(arr[i]>arr[i+1]){
arr[i] = [arr[i+1],arr[i+1]=arr[i]][0];
swaped = true;
}
}
r--;
for(var i=r;i>l;i--){
if(arr[i]<arr[i-1]){
arr[i] = [arr[i-1],arr[i-1]=arr[i]][0];
swaped = true;
}
}
l--;
}
return arr;
}//
function GnomeSort(arr){
var i=1;
while(i<arr.length){
if(arr[i]<arr[i-1]){
arr[i] = [arr[i-1],arr[i-1]=arr[i]][0];
i = --i||1;
}else{
i++;
}
}
return arr;
}// ,
function BeadSort(arr){
var result = [];
var beads = [];
for(var i=0;i<arr.length;i++){
bead = arr[i];
while(bead){
bead--;
beads[bead] = (beads[bead]||0)+1;
}
}
for(var i=beads[0],l=i;i>0;i--){
for(var j=0;j<beads.length;j++){
if(i<=beads[j]){
result[l-i] = (result[l-i]||0)+1;
}
}
}
while(arr.length-result.length){
result.unshift(0);
}
return result;
}//
function CountingSort(arr){
var count = [];
for(var i=0;i<arr.length;i++){
count[i] = count[i]||0;
for(var j=i+1;j<arr.length;j++){
count[j] = count[j]||0;
if(arr[i]>arr[j]){
count[i]+=1;
}else{
count[j]+=1;
}
}
}
var result = [];
for(var c=0;c<count.length;c++){
result[count[c]] = arr[c];
}
return result;
}// ，
function CycleSort(arr){
var count = [];
for(var i=0;i<arr.length;i++){
count[i] = count[i]||0;
for(var j=i+1;j<arr.length;j++){
count[j] = count[j]||0;
if(arr[i]>arr[j]){
count[i]+=1;
}else{
count[j]+=1;
}
}
}
var temp,pos,cycleIndex;
for(var cycleStart=0;cycleStart<arr.length;cycleStart++){
if(count[cycleStart]==cycleStart){ continue; }
temp = arr[cycleStart];
pos = count[cycleStart];
do{
cycleIndex= pos ;
temp = [arr[pos],arr[pos]= temp][0];
pos = [count[pos ],count[pos ]=pos][0];
}while(cycleIndex!=cycleStart);
}
return arr;
}//
function CombSort(arr){
var step = arr.length, swaped = true;
while(swaped||step>1){
swaped = false;
if(step>1){
step = Math.floor(step/1.3);
}
step = step||1;
for(var i=0;i+step<arr.length;i++){
if(arr[i]>arr[i+step]){
arr[i] = [arr[i+step],arr[i+step]=arr[i]][0];
swaped = true;
}
}
}
return arr;
}//
function PatienceSort(arr){
var buckets = [],temp;
for(var i=0;i<arr.length;i++){
temp = arr[i];
for(var j=0;j<buckets.length;j++){
if(buckets[j][buckets[j].length-1]<=temp){
buckets[j].push(temp);
temp = null;
break;
}
}
if(temp!==null){
buckets.push([temp]);
}
}
arr = [].concat.apply([],buckets);
for(var i=buckets[0].length;i<arr.length;i++){
for(var j=i;j>0;j--){
if(arr[j]<arr[j-1]){
arr[j] = [arr[j-1],arr[j-1]=arr[j]][0];
}else{
break;
}
}
}
return arr;
}