- 插入排序
- 冒泡排序
- 快速排序
- 数组去重复
- 从一个长度10万的数组中，随机取出100条数据（取出的数据不能重复）;
插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
操作步骤：首先选取数组的第一项即ary[0]，我们可以认为这个数是已经安排好序的，再取ary[1]项插入到已经排好序的元素中，此时只有ary[0]，我们比较ary[0]和ary[1]；大于ary[0]就放在后面，小于就插到ary[0]前面；要插入的元素依次为ary[1]至ary[ary.leng-1]项；插入到排序好的数组中的时候，插入每一项都需要从后面往前面遍历已经排序好的元素；
如果排序好的元素比插入的元素大，则把该元素往后挪一位，知道已经排序的元素小于等于要插入的元素（或者已经遍历完已经排好序的数组项），则把要插入的元素放在该位置+1的索引位置中（反向排的时候，需要放在数组的第0个位置），对每个插入的元素都执行上面的操作，最终数组就是排序好的；
有BUG的写法；
var ary=[11,2,31,45,6,78,37,33,21];
function insertSort(ary){
var temp;//定义一个临时变量，保存要插入的值；
for(var i= 1,len=ary.length;i<len;i++){
if(ary[i]<ary[i-1]){
temp=ary[i];
ary[i]=ary[i-1];
ary[i-1]=temp;
}
}
return ary;
}
var newAry=insertSort(ary);
console.log(newAry);//[2, 11, 31, 6, 45, 37, 33, 21, 78]
因为只把小的数往前移动了一次；这里需要用到while循环，把6移动2后面；
var ary=[11,2,31,45,6,78,37,33,21];
function insertSort(ary){
var temp;//定义一个临时变量，保存要插入的值；
for(var i= 1,len=ary.length;i<len;i++){
if(ary[i]<ary[i-1]){
temp=ary[i];//需要插入的值；
var pIndex=i-1;//需要插入值的前一个索引；
while(temp<ary[pIndex]&&pIndex>=0){
ary[pIndex+1]=ary[pIndex];//相当于ary[i]=ary[i-1];
ary[pIndex]=temp;//相当于ary[i-1]=temp;完成一波交换；
pIndex--;//准备下一波交换；
}
}
}
return ary;
}
var newAry=insertSort(ary);
console.log(newAry);//[2, 6, 11, 21, 31, 33, 37, 45, 78]
基本思想：就是把数据像泡泡一样网上冒，让体积最轻的泡泡浮在最上面，然后按照重量往下依次排列；
冒泡排序的操作原理：
var ary=[11,2,31,45,6,78,37,33,21];
用循环的方式，循环数组的长度，然后比较数组的数据
- 第一次循环把ary的最大值放在ary[ary.length-1]的位置；
- ary[0]>ary[1],如果是true，说明第一项比第二项大，交换ary[0]和ary[1]的位置；如果是false则不改变位置；
- ary[1]>ary[2],如果是true，说明第二项比第三项大，交换ary[1]和ary[2]的位置；如果是false则不改变位置；（此时的ary[1]肯定比ary[0]大的，因为开始的时候已经把ary[0]和ary[1]比较了）
- ……
- ary[ary.length-2]>ary[ary.length-1];比较到这个时候，ary[ary.length-1]的位置肯定是最大的数据了；
- 第二次循环，把倒数第二大的数据，放在数组的ary[ary.length-2]位置;
- 备注：第二次循环的时候，只需要比较到ary[ary.length-2]的位置就可以了，因为ary[ary.length-1]已经是最大值了，无需再次比较；
注意：交换位置的时候，需要一个中间变量来协助，假设让a和b进行数据交换； var temp=a;a=b;b=temp; 这样就可以把a和b的数据交换好了；
var ary=[11,2,31,45,6,78,37,33,21];
function sortAry(ary){
var aryLen=ary.length;//获取数组的长度；有aryLen个数在排序；
var temp=null;//临时变量，交换数据中用的
for(var i= 0,iLen=aryLen-1;i<iLen;i++){//外层循环n-1次；
for(var j= 0,jLen=aryLen-1-i;j<jLen;j++){//每次循环完，都能从剩下的数组中找出个最大的数组放在aryLen-1-i的位置；
if(ary[j]>ary[j+1]){
temp=ary[j];
ary[j]=ary[j+1];
ary[j+1]=temp;
}
}
}
return ary;
}
var newAry=sortAry(ary);
console.log(newAry);//[2, 6, 11, 21, 31, 33, 37, 45, 78]
避免无效循环的方法；
var ary=[11,2,31,45,6,78,37,33,21];
function sortAry(ary){
var aryLen=ary.length;//获取数组的长度；有aryLen个数在排序；
var temp=null;//临时变量，交换数据中用的
var flag=false;//设置标志位，初始化为false
for(var i= 0,iLen=aryLen-1;i<iLen;i++){//外层循环n-1次；
for(var j= 0,jLen=aryLen-1-i;j<jLen;j++){//每次循环完，都能从剩下的数组中找出个最大的数组放在aryLen-1-i的位置；
if(ary[j]>ary[j+1]){
temp=ary[j];
ary[j]=ary[j+1];
ary[j+1]=temp;
flag=true;//如果交换好了，做个标记，避免无效的循环；
}
}
if(!!flag){//只要交换了位置，flag的值就重新设置为false了；
flag=false;
}else{//如果没有交换，说明数组已经排好序了，可以结束循环了；
break;
}
}
return ary;
}
var newAry=sortAry(ary);
console.log(newAry);//[2, 6, 11, 21, 31, 33, 37, 45, 78]
冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
算法步骤：
- 1）比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 2）对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
- 3）针对所有的元素重复以上的步骤，除了最后一个。
- 4）持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
基本思想：首先从数组ary选取一个基准点（通常我们取中间项作为基准点），然后遍历数组，把小于基准项放到基准点左边集合，把大于基准项放在基准点右边集合；然后对左边和右边两个集合分别再重复前面的操作；（直到每个集合就剩下一个元素的时候），其实就是一个递归的思想；
操作步骤：
var ary=[11,2,31,45,6,78,37,33,21];
依旧拿上边这个数组做例子，，我们确定一个基准点，
var ary=[11,2,31,45,6,78,37,33,21];
var pivot=ary[Math.floor(ary.length/2)];
console.log(pivot);//6
然后我们循环数据中的剩余项，把小于6的放在数组left中，把大于等于56的数组项放在数组right中，第一轮操作结束后left=[2],right=[11,31,45,78,37,33,21]
然后对left重复以上的操作，直到left和right仅剩一项或者空时候结束，最终返回left+pivot+right;
var ary=[11,2,31,45,6,78,37,33,21];
function quickSort(ary){
var aryLen=ary.length;//获取ary的长度；
if(aryLen<=1){//如果ary小于等于1的长度，就直接返回了;这一步非常重要，是判断是否循环完的标志；
return ary;
}
var pINdex=Math.floor(ary.length/2);//基准项的所引值
var pivot=ary.splice(pINdex,1);//删除基准项，并把基准项赋值给pivot；
var left=[],right=[];
for(var i= 0,len=ary.length;i<len;i++){
if(ary[i]<pivot[0]){
left.push(ary[i]);
}else{
right.push(ary[i])
}
}
return quickSort(left).concat(pivot,quickSort(right));
}
var newAry=quickSort(ary);
console.log(newAry);//[2, 6, 11, 21, 31, 33, 37, 45, 78]
-
第一种方法：每一次拿出数组中的当前项和后面的所有项进行比较，如果相同的话，删除即可；
var ary=[1,2,34,56,6,7,45,3,2,2,12,4,9,8,6,7,4]; function deleteRepeat(ary){ for(var i= 0,len=ary.length-1;i<len;i++){//比较length-1次； var temp=ary[i]; for(var j=i+1;j<ary.length;j++){ if(temp==ary[j]){ ary.splice(j,1); j--;//删除以后需要把j重置下，避免数组塌陷； } } } return ary; } var newAry=deleteRepeat(ary); console.log(newAry);
这种处理方法，处理少量数据的时候没有问题的，但是做很多数组的时候，性能就是一个很大的问题了，双重循环毕竟还是有优化的空间的，通常用第二种方法；
第二种方法：利用对象的属性名和属性值不能重复的原理，把数组中每一项的值当作对象的属性名属性值进行储存，在每一次储存之前进行判断，如果对象中已经存在这一项，我们就删除数组中这项，不存在我们就把这一项储存到我们的新的对象中，（注意对象在这里只是一个临时储存的作用），在处理完成后最好置为null；养成好习惯 ；
var ary=[1,2,34,56,6,7,45,3,2,2,12,4,9,8,6,7,4];
function deleteRepeat(ary){
var obj={};
for(var i= 0,len=ary.length;i<len;i++){
var temp=ary[i];
if(obj[temp]==temp&&temp!=undefined){
ary.splice(i,1);
i--;
continue;
}
obj[temp]=temp;
}
obj=null;
return ary;
}
var newAry=deleteRepeat(ary);
console.log(newAry);
原理：随机获取100个索引，每一次获取的时候，都把对应的项获取，为了避免数组中的项重复，每获取一个就把原有数组中的这一项删除；
为了方便掩饰从20个里取5个随机数；
第一种比较耗性能的写法；
var ary=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20];
function selectOption(ary,optionNumber){
var targetAry=[];
if(!optionNumber){
console.log("请指定需要删选的数量!");
}
for(var i=0;i<optionNumber;i++){
var ran=Math.round(Math.random()*(ary.length-1));//获取0-数组最大索引的一个随机数；
targetAry.push(ary[ran]);//按照获取的随机索引，把对应的值取出来，放到新书组中；
ary.splice(ran,1);//数组中实现删除的时候比较耗性能，为了牵扯到数组长度的改变，数组被删除的项，后面所有数据都前进一位；
}
return targetAry;
}
var newAry=selectOption(ary,2);
console.log(newAry);
确定在代码后面已经说明，这种的比较耗性能；
var ary=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20];
function selectOption(ary,optionNumber){
var targetAry=[];
if(!optionNumber){
console.log("请指定需要删选的数量!");
}
for(var i=0;i<optionNumber;i++){
var ran=Math.round(Math.random()*(ary.length-1));//获取0-数组最大索引的一个随机数；
targetAry.push(ary[ran]);//按照获取的随机索引，把对应的值取出来，放到新书组中；
ary[ran]=ary[ary.length-1];//把数组最后一项放到当前要删除索引的这一项；
ary.length=ary.length-1;//删除最后一项；
}
return targetAry;
}
var newAry=selectOption(ary,10);
console.log(newAry);
这种的写法，是操作数组的常用处理方式；借助数组length可修改的性能；