做有态度的前端团队

网易FEG前端团队

总结数组排序和去重的几个方法

本月工作之余琢磨了一下排序算法,没弄明白的暂时就不写了,写写可以理解的几种,最后也顺便总结下去重。不对的地方,多多指教哈~

排序

1、数组的sort()方法

数组自带了一个sort()方法,用于对数组的元素进行排序。如果调用该方法时没有使用参数,默认将按照字符编码的顺序进行排序。比如:

var arr1 = [1, 2, 4, 22, 12, 5];
var arr2 = ['A', 'a', 'J', 'j'];

console.log(arr1.sort()) //[ 1, 12, 2, 22, 4, 5 ] 
console.log(arr2.sort()) //[ 'A', 'J', 'a', 'j' ] ,对应的ASCII值大的排后面

如果想按照数字大小排序,可以这么写:

var arr = [1, 2, 4, 22, 12, 5];
arr.sort(function(a, b) {
    return a - b;//如果返回b -a ,排序结果为降序
})
console.log(arr) //[ 1, 2, 4, 5, 12, 22 ]   

sort()方法接受一个参数,里面是个比较函数,a大于b时,返回的是正数,说明a大于b;a等于b时,返回0,两者相等;a小于b时,返回负数,说明a比b小。

2、冒泡排序

function bubbleSort(arr) {

    var len = arr.length,
        temp;
    for (var i = 0; i < len - 1; i++) {
        for (var j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }

    }
    return arr;
}

思路就是从第一个数开始,arr[0]arr[1]比较,比较过后,较小的数排前面,较大的数排后面,然后arr[1]arr[2]比较...以此类推...每次经过一次外循环后,最大的数排到了后面,最后剩下一个数就不用排了,因此外循环数为len-1,已排好的数,内循环的时候就不算在内了,因此内循环次数为len - 1 - i。下面举个简单的例子推敲一下,数组[4,1,7,2]的排序过程如下:

i = 0;进行第一次外循环,然后进入内循环,j = 0; j < 3 ; j++;,比较arr[0]>arr[1],条件成立,交换位置,此时,数组为[1,4,7,2],继续内循环,比较arr[1]>arr[2],条件不成立,数组不做改变,继续比较arr[2]>arr[3],条件成立,交换位置[1,4,2,7],第一次外循环到此结束,结果为[1,4,2,7]

i = 1;进行第二次外循环,然后进入内循环,j = 0; j < 2 ; j++;比较arr[0]>arr[1],条件不成立,结果为[1,4,2,7],继续比较[arr[1]>arr[2],条件成立,交换位置,此时数组为[1,2,4,7]

i = 2;进行第三次外循环,arr[0]arr[1]比较之后,数组还是[1,2,4,7];排序到此结束。

从上面可以看出排序到第二轮就排好序,第三次多余的了。再举个例子,数组[1,3,2,4,5,6,7,8,9]按照这样排序,其实把3和2换了就完了,只需一轮就排好了,之后的循环没必要,所以还可以稍微优化一下。如果内循环在某次循环中没有执行交换,则说明此时数组已经排好序。增加一个flag标记,每次发生交换,就标记,如果某次循环完没有标记,则说明已经完成排序。

function bubbleSort(arr) {

    var len = arr.length,
        temp, flag;
    for (var i = 0; i < len - 1; i++) {
        flag = false;
        for (var j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                flag = true;
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        if (!flag) {
            break;
        }
    }
    return arr;
}

动态演示图:(来源网络)
image

另一种
function bubbleSort2(arr) {
    var len = arr.length,
        temp;
    for (var i = 0; i < len-1; i++) {
        for (var j = i + 1; j < len; j++) {
            if (arr[j] < arr[i]) { 
                temp = arr[j];    
                arr[j] = arr[i];
                arr[i] = temp;
            }
        }
    }
    return arr;
}

网上看到的一种,这个也算冒泡排序的一种?(疑问),先不管了,我说下思路,大概就是从第一个数开始,往后比较,遇到比自己小的元素就交换位置。经过第一轮外循环之后,最小的数排在了第一位;第二轮,第二个数和后面的数比较,完了后第二小的数排在了第二位...以此类推...最后排序得到从小到大的数组。这个倒是和下面要介绍的选择排序有点类似,只不过选择排序是找到最小值的下标,记录下来,最后才交换位置,而不是每次比较如果符合条件就马上交换。

3、选择排序

function selectionSort(arr) {
    var len = arr.length;
    var minIndex, temp;
    for (var i = 0; i < len - 1; i++) {
        minIndex = i;
        for (var j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {     //寻找最小的数
                minIndex = j;                 //将最小数的索引保存
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}

这个上文有提及到,就不细说啦...有兴趣的可以写个小例子演示一下这个过程...应该可以理解...

另一种
function selectSort2(arr) {
    if (arr.length <= 1) { 
        return arr;
    }
    var min = arr[0], //从第一个数开始
        minIndex = 0;
    for (var i = 1, len = arr.length; i < len; i++) {
        if (arr[i] < min) {
            min = arr[i]; //寻找最小的值
            minIndex = i; //将最小数的索引保存
        }
    }
    var prev = arr.splice(minIndex, 1); //从原数组删除这个最小值,并且保存起来,这里返回的是一个数组

    return prev.concat(selectSort2(arr)); //通过递归不断重复取最小值这个过程,最后拼接起来
}

这种感觉有点类似,姑且归到这一类吧。思路是不断从原数组分割出最小的值,最后拼接在一起。需要注意到的是,这种并不是原地排序,返回了一个排好序的新数组,而且由于用了splice(),原数组被破坏了,实际上不是最初的样子了。

3、快速排序

function quickSort(arr) {
    if (arr.length <= 1) { //递归结束的条件判断,没这步会导致内存溢出
        return arr;
    }
    var left = [],
        right = [],
        pivot = arr[0];  //用数组的第一个数作为基准值
    for (var i = 1, len = arr.length; i < len; i++) {
        if (arr[i] < pivot) { 
            left.push(arr[i]); //小于基准值就分配到left数组
        } else {
            right.push(arr[i]);//否则分到right数组
        }
    }
    return quickSort(left).concat(pivot, quickSort(right)); //递归重复这个过程,最后返回一个排好序的新数组。
}

这种方法采用的思想是分治思想,递归合并。过程分以下三个步骤:

  • 在数组中,选择一个数作为"基准"(pivot)。上面的这程序,我选了数组第一个数作为基准,当然你也可以这样Math.floor(arr.length / 2),取近似中间的那个值作为基准,不过写法会稍微不太一样,思路一样的。
  • 所有小于"基准"的数,都移到"基准"的左边;所有大于"基准"的数,都移到"基准"的右边。
  • 对"基准"左边和右边的两个数组,不断重复第一步和第二步,直到所有数组只剩下一个数为止。

结语: 数组排序暂时就写到这吧,只是简单地了解了下,时间复杂度,空间复杂度,稳定性等等这些东西甚至都没提及到,还有很多东西要学习,要花不少精力,不过偶尔了解下这些也挺好的...

去重

去重方法和思路也很多,这里就介绍两种吧。

方法一:

function unique1(arr) {

    var res = [],
        len = arr.length;
    for (var i = 0; i < len; i++) {
        if (res.indexOf(arr[i]) == -1) {
            res.push(arr[i]);
        }
    }
    return res;
}

思路:利用了数组的indexOf()方法,此方法的目的是寻找存入参数在数组中第一次出现的位置,如果结果返回-1,说明还不存在,于是就可以保存起来了。实现这个方法的时候会遍历数组直到找到目标为止,比较耗时,速度方面要比借助hash表来实现慢。下文即将介绍~

方法二:

function unique2(arr) {
    var res = [],
        hash = {},
        len = arr.length;
    for (var i = 0; i < len; i++) {
        if (!hash[arr[i]]) {//如果不存在
            hash[arr[i]] = true;//记录下来
            res.push(arr[i]);//保存起来
        }
    }
    return res;
}

思路:将数组中的值通过作为下标(key)的形式存入一个Object内,利用这个加以判断,最后达到去重目的。这里有必再写详细一点,因为最初的时候有点懵逼,一时没看懂,定义了一个对象hash={},然后判断的时候又是这样写hash[],让人感觉又有点像数组。。。其实很好理解的。先来看个小例子:

var hash = {
    "name": "xiaojiecong",
    "sex": "male"
};

console.log(hash.name);
console.log(hash.sex);

console.log(hash["name"]);
console.log(hash["sex"]);

其实想说明就是,有两种方式能得到对象字面量中的某个键名(key)的键值(value),第一种是用点连接,第二种是用中括号,所以看到上面hash[]这样写也不会觉得奇怪了。用点连接或中括号,这个也适用于元素操作属性这种场景,比如:

document.getElementsByTagName('div')[0].style.display = 'block';
document.getElementsByTagName('div')[0].style['display'] = 'block';
document.getElementsByTagName('input')[0].value ='123';
document.getElementsByTagName('input')[0]['value'] ='123';

这里解释太多,好像有点啰嗦了 - -!

其实没完的,我再写几行。。。

这种去重方法还有个要注意的地方哦,它是不区分这种情况的,比如:1和"1"。去重之后只会保留 1或"1",两者之一,在数组里谁在的位置靠前去重后就留下谁,但1和"1"显然不相等的,理应都保留的。出现这个问题的原因就是,无论是1还是"1",传进来都是hash["1"],这样看它们是相等的了。

如果需要考虑到这种情况,还要稍作修改。一般来说,无非是数字和字符串(像一些高级语言,数组其实只存一种数据类型的,JS数组允许存多种),这里其实就是加了一点东西,区分开来,如下:

function unique2(arr) {
    var res = [],
        hash = {},
        str = '',
        len = arr.length;
    for (var i = 0; i < len; i++) {
        if (typeof arr[i] != 'string') {
            str = '';
        } else {
            str = 'str';
        }
        if (!hash[arr[i] + str]) {
            hash[arr[i] + str] = true;
            res.push(arr[i]);
        }
    }
    return res;
}
var a = [1, "g", 5 , "1", 6, "g"];
console.log(unique2(a)); //[ 1, 'g', 5, '1', 6 ] 

总的来说,利用哈希表实现数组的去重要比方法一用indexOf()要快很多,就是多占用了一点内存,因为多了个Object,这就是所谓的空间换时间吧...

顺便贴下,组长写过的一个小例子以供参考,也用到了这个东西...

//随机取出不重复的若干个数字
function getRandom(len) {
    var ret = {};
    var result = [];
    while (len) {
        var number = Math.floor(Math.random() * 10);//这里是随机取0到9
        if (!ret[number]) {
            ret[number] = true;
            result.push(number);
            len -= 1;
        }
    }
    return result;
}

手机阅读请扫描下方二维码:

none
上一篇:CSS3的3D转换   下一篇:负margin小结

添加新评论

ali-40.gifali-41.gifali-42.gifali-43.gifali-44.gifali-45.gifali-46.gifali-47.gifali-48.gifali-49.gifali-50.gifali-51.gifali-52.gifali-53.gifali-54.gifali-55.gifali-56.gifali-57.gifali-58.gifali-59.gifali-60.gifali-61.gif