JS写排序算法

发表于   |   分类于   |     |  

[TOC]

排序算法

冒泡排序

从一端开始将相邻的两个比较，大的往后移动，这样一轮比下来，最大数冒泡到最后了，对剩下的序类按此交换

选择排序

和冒泡排序类似，都是一轮排序后把最大的数放到最后。不同的是冒泡是没相邻两个比较，选择排序首先要遍历该数组，把最小的数字和第一个位置的数字交换，这样就把最小的数字放到了最左边。对剩下的序类也按次交换。

插入排序

和打扑克牌一样的道理，拿到一张牌找到一个合适的位置插入。
如序类5,3,8,6,4。第一张牌作为基准，然后第二张牌3要插入到5后面，那么就把从5开始后移一位，放入3，变成了3，5，8，6，4.然后拿到第三章牌8，它比前面排序好的数都大，不动。拿到第四张牌6的时候把它插到8前面。

1
2
3
4
5
6
7
8
9
10
11
function insertSort(arr){
  var temp;  //temp变量用于临时存储待插入元素
  for(var i=1; i<arr.length; i++){
     temp = arr[i];
      //从前往后查找插入位置
     for(var j=i; j>0&&arr[j-1]>temp; j--){
         arr[j]=arr[j-1]; //将大于temp的arr[j]元素后移
     }
      arr[j]=temp;
  }
}

快速排序

选择一个基准，序类中每个数都和这个基准比较，小的放在left数组，大的放在right数组。然后分别对基准左右两边的子序类进行相似的比较，依次递归。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var quickSort=function(arr){
if(arr.length<=1){
	return arr;
}
var left=[];
var right=[];
var index=Math.floor(arr.length/2);
indexValue=arr.splice(index,1)[0];
for(var i=0;i<arrNew.length-1;i++){
	if(arrNew[i]>arr[index]){
		left.push(arrNew[i]);
	}else{
		right.push(arrNew[i]);
	}
}
return quickSort(left).concat([indexValue],quickSort(right));
};

常规的快排：https://blog.csdn.net/morewindows/article/details/6684558
对挖坑填数进行总结
1．i =L; j = R; 将基准数挖出形成第一个坑a[i]。
2．j–由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。
3．i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。
4．再重复执行2，3二步，直到i==j，将基准数填入a[i]中。
一次快排下来，最初选择的基数两边分别是比它小和大的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/* 挖坑填数,即一次快排
    1.i=L;j=R;基准数选择X=arr[i]挖一个坑
    2.j-- 从后往前找到比X小的数填到坑arr[i]中，此时多出了一个坑arr[j]
    3.i++ 从前往后找到比X大的一个数填到arr[j]坑中
    4.重复2，3步骤知道i==j，将X基准数填入arr[i]中,返回此时基准数所在的位置index
*/
function ajustArray(arr,l,r){
    var X=arr[l];
    var i=l,j=r;
    while(i<j){
        //从后往前找比基数X小数，填到坑i处，且产生坑j
        while(i<j && arr[j]>=X){
            j--;
        }
        if(i<j){
            arr[i]=arr[j];
            i++;
        }
        
        //从前往后找比X大的数，填到坑j处
        while(i<j && arr[i]<X){
            i--;
        }
        if(i<j){
            arr[j]=arr[i];
            j--;
        }
    }
    
    //此时i==j，将X基准数填入arr[i]中，返回此时基准数所在的位置index
    arr[i]=X;
    return i;
}
    
function quickSort(arr,l,r){
    if(l<r){
        var index=ajustArray(arr,l,r);//一次快排
        quickSort(arr,l,index-1);//左边递归
        quickSort(arr,index+1,r);//右边递归
    }
}

判断两个链表是否相交并找出交点

如果两个链表相交那么尾部一定相等，假设第一个链表长度时L1，第二个长L2，交点不可能在长的L2-L1这段差值之间，所以先让较长的L2走完L2-L1这一段，然后两个链表同时走，判断什么时候相等

热评文章