美文网首页
排序算法总结

排序算法总结

作者: 靳刘杰 | 来源:发表于2017-02-25 11:28 被阅读0次

    1.直接插入排序

    原理:

    将待排序的一个元素插入到已排好序的数组中,插入过程的原理是:记录下待插入的元素的值,然后在已排好序的数组中,从后往前,将比这个数字大的元素往后移一个位置,依次循环,最终,空出来一个位置,就是待插入元素该放的位置

    javascript算法实现

    function InsertSort(arr) {
            for (var i = 1; i < arr.length; i++) {
                var x = arr[i]
                var j = i - 1;
                while(arr[j] > x && j > -1){
                    arr[j+1] = arr[j];
                    j--;
                }
                arr[j+1] = x;
            }
            console.log(arr);
        }
    

    算法分析

    插入排序是稳定的(如何遇见相同的值,这个值是不会往前移动一位的)
    插入排序的事件复杂度是O(n*n)

    2.简单选择排序

    原理:

    从整个数组中遍历一遍,选择其中最小的一个值。然后,将这个值放在第一个位置上,第二次遍历,从待排序的数组中选择最小的一个放在第二个位置上,依次循环n-1次,最终得到排好序的数组

    javascript算法实现

    // 选择排序
        function select(arr){
            for (var i = 0;i < arr.length-1;i++) {
                var min = arr[i];
                var minIndex = i;
                var temp;
                for (var j = i + 1;j < arr.length;j++) {
                    if (arr[j] < min) {
                        min = arr[j];
                        minIndex = j;
                    }
                }
                if (minIndex != i) {
                    temp = arr[minIndex];
                    arr[minIndex] = arr[i];
                    arr[i] = temp;
                }
            }
            console.log(arr);
        }
    

    算法分析

    通常该算法被认为是不稳定的,但是可以改进使之变成稳定的,
    同时,也可以经过改进,使得其时间复杂度降低
    上述算法的事件复杂度是O(n*n)

    3.冒泡排序

    原理:

    在要排序的一组数中,对当前还未排好序的范围内的全部数,自上而下对相邻的两个数依次进行比较和调整,让较大的数往下沉,较小的往上冒。即:每当两相邻的数比较后发现它们的排序与排序要求相反时,就将它们互换。

    javascript算法实现

    // 冒泡排序
        function mao(arr){
            var temp;
            for (var i = arr.length - 1; i > 0; i--) {
                for (var j = 0; j < i; j++){
                    if (arr[j] > arr[j+1]) {
                        temp = arr[j];
                        arr[j] = arr[j+1];
                        arr[j+1] = temp;
                    }
                }
            }
            console.log(arr);
        }
    

    算法分析

    冒泡排序是稳定的
    冒泡排序的时间复杂度是O(n*n)

    大神写的总结链接:http://blog.csdn.net/hguisu/article/details/7776068

    相关文章

      网友评论

          本文标题:排序算法总结

          本文链接:https://www.haomeiwen.com/subject/neigwttx.html