常用排序算法收集

2015年6月21日20:04:11 发表评论 已收录

关于排序的算法有很多种,这里做一个排序算法的收集,以供参考。

No.1:选择排序

//     选择排序(Selection Sort)与冒泡排序类似,也是依次对相邻的数进行两两比较。不同之处在于,它不是每比较一次就调换位置,
//     而是一轮比较完毕,找到最大值(或最小值)之后,将其放在正确的位置,其他数的位置不变。
//
//        以对数组[3, 2, 4, 5, 1] 进行从小到大排序为例,步骤如下:
//
//            1.假定第一位的“3”是最小值。
//
//            2.最小值“3”与第二位的“2”进行比较,2小于3,所以新的最小值是第二位的“2”。
//
//            3.最小值“2”与第三位的“4”进行比较,2小于4,最小值不变。
//
//            4.最小值“2”与第四位的“5”进行比较,2小于5,最小值不变。
//
//            5.最小值“2”与第五位的“1”进行比较,1小于2,所以新的最小值是第五位的“1”。
//
//            6.第五位的“1”与第一位的“3”互换位置,数组变为[1, 2, 4, 5, 3]。


            function selectionSort(arr){

                for(var i = 0; i < arr.length; i ++){
                    //将当前位置设置为最小值
                    var min = i;

                    //检查数组其余位是否更小
                    for(var j = i+1; j < arr.length; j ++){
                        if(arr[min] > arr[j]){//当当前位置的值大于比较的这个位置的值时,将这个位置的值记录下来
                            min = j;
                        }
                    }
                    //如果当前位置不是最小值,那么交换位置,将其换为最小值
                    if(i != min){
                        var temp = arr[i];
                        arr[i] =  arr[min];
                        arr[min] = temp;
                    }
                }
                return arr;
            }
            var arr1 = [3,2,4,5,1];
            var newArr = selectionSort(arr1);
            console.log(newArr);

No.2:插入排序:

//        插入排序(insertion sort)比前面两种排序方法都更有效率。它将数组分成“已排序”和“未排序”两部分,一开始的时候,
//        “已排序”的部分只有一个元素,然后将它后面一个元素从“未排序”部分插入“已排序”部分,从而“已排序”部分增加一个元素,
//        “未排序”部分减少一个元素。以此类推,完成全部排序。
//
//        以对数组[3, 2, 4, 5, 1] 进行从小到大排序为例,步骤如下:
            /*
            *
            * 1.将数组分成[3]和[2, 4, 5, 1]两部分,前者是已排序的,后者是未排序的。

              2.取出未排序部分的第一个元素“2”,与已排序部分最后一个元素“3”比较,因为2小于3,所以2排在3前面,整个数组变成[2, 3]和[4, 5, 1]两部分。

              3.取出未排序部分的第一个元素“4”,与已排序部分最后一个元素“3”比较,因为4大于3,所以4排在3后面,整个数组变成[2, 3, 4]和[5, 1]两部分。

              4.取出未排序部分的第一个元素“5”,与已排序部分最后一个元素“4”比较,因为5大于4,所以5排在4后面,整个数组变成[2, 3, 4, 5]和[1]两部分。

              5.取出未排序部分的第一个元素“1”,与已排序部分最后一个元素“5”比较,因为1小于5,所以再与前一个元素“4”比较;因为1小于4,
              再与前一个元素“3”比较;因为1小于3,再与前一个元素“2”比较;因为小于1小于2,所以“1”排在2的前面,整个数组变成[1, 2, 3, 4, 5]。
            *
            *
            * */

            function insertTionSort(arr){

                var value;//当前比较的值
                var i;//i:未排序部分的当前位置,
                var j;//j:已排序部分的当前位置

                for(i = 0; i < arr.length; i ++){
                    value = arr[i];//储存当前位置的值
                    //当已排序部分的当前元素大于value,就将元素向后移一位,再将前一位与value进行比较
                    for(j = i - 1; j > -1 && arr[j] > value; j --){
                        arr[j + 1] = arr[j];
                    }
                    arr[j + 1] = value;
                }
                return arr;
            }




            var arr1 = [3,2,4,5,1];
            var newArr = insertTionSort(arr1);
            console.log(newArr);

No.3:合并排序

        /*
        * 前面三种排序算法只有教学价值,因为效率低,很少实际使用。合并排序(Merge sort)则是一种被广泛使用的排序方法。

         它的基本思想是,将两个已经排序的数组合并,要比从头开始排序所有元素来得快。因此,可以将数组拆开,分成n个只有一个元素的数组,然后不断地两两合并,直到全部排序完成。

         以对数组[3, 2, 4, 5, 1] 进行从小到大排序为例,步骤如下:
         1.将数组分成[3, 2, 4]和[5, 1]两部分。

         2.将[3, 2, 4]分成[3, 2]和[4]两部分。

         3.将[3, 2]分成[3]和[2]两部分,然后合并成[2, 3]。

         4.将[2, 3]和[4]合并成[2, 3, 4]。

         5.将[5, 1]分成[5]和[1]两部分,然后合并成[1, 5]。

         6.将[2, 3, 4]和[1, 5]合并成[1, 2, 3, 4, 5]。
        * */

        function merge(left,right){
            var result = [];
            var il = 0;
            var ir = 0;
            while(il < left.length && ir < right.length){
                if(left[il] < right[ir]){
                    result.push(left[il++]);
                } else {
                    result.push(right[ir++]);
                }
            }
            return result.concat(left.slice(il)).concat(right.slice(ir));
        }
        function mergeSort(myArray){
            if(myArray.length < 2){
                return myArray;
            }
            var middle = Math.floor(myArray.length / 2),
                    left    = myArray.slice(0, middle),
                    right   = myArray.slice(middle),
                    params = merge(mergeSort(left), mergeSort(right));

            // 在返回的数组头部,添加两个元素,第一个是0,第二个是返回的数组长度
            params.unshift(0, myArray.length);

            // splice用来替换数组元素,它接受多个参数,
            // 第一个是开始替换的位置,第二个是需要替换的个数,后面就是所有新加入的元素。
            // 因为splice不接受数组作为参数,所以采用apply的写法。
            // 这一句的意思就是原来的myArray数组替换成排序后的myArray
            myArray.splice.apply(myArray, params);

            // 返回排序后的数组
            return myArray;
        }
        var arr1 = [3,2,4,5,1];
        var newArr = mergeSort(arr1);
        console.log(newArr);

No.4:快速排序

       /*
        * 快速排序:
         快速排序(quick sort)是公认最快的排序算法之一,有着广泛的应用。

         它的基本思想很简单:先确定一个“支点”(pivot),将所有小于“支点”的值都放在该点的左侧,大于“支点”的值都放在该点的右侧,然后对左右两侧不断重复这个过程,直到所有排序完成。

         具体做法是:

         1.确定“支点”(pivot)。虽然数组中任意一个值都能作为“支点”,但通常是取数组的中间值。

         2.建立两端的指针。左侧的指针指向数组的第一个元素,右侧的指针指向数组的最后一个元素。

         3.左侧指针的当前值与“支点”进行比较,如果小于“支点”则指针向后移动一位,否则指针停在原地。

         4.右侧指针的当前值与“支点”进行比较,如果大于“支点”则指针向前移动一位,否则指针停在原地。

         5.左侧指针的位置与右侧指针的位置进行比较,如果前者大于等于后者,则本次排序结束;否则,左侧指针的值与右侧指针的值相交换。

         6.对左右两侧重复第2至5步。

         以对数组[3, 2, 4, 5, 1] 进行从小到大排序为例,步骤如下:

         1.选择中间值“4”作为“支点”。

         2.第一个元素3小于4,左侧指针向后移动一位;第二个元素2小于4,左侧指针向后移动一位;第三个元素4等于4,左侧指针停在这个位置(数组的第2位)。

         3.倒数第一个元素1小于4,右侧指针停在这个位置(数组的第4位)。

         4.左侧指针的位置(2)小于右侧指针的位置(4),两个位置的值互换,数组变成[3, 2, 1, 5, 4]。

         5.左侧指针向后移动一位,第四个元素5大于4,左侧指针停在这个位置(数组的第3位)。

         6.右侧指针向前移动一位,第四个元素5大于4,右侧指针移动向前移动一位,第三个元素1小于4,右侧指针停在这个位置(数组的第3位)。

         7.左侧指针的位置(3)大于右侧指针的位置(2),本次排序结束。

         8.对 [3, 2, 1]和[5, 4]两部分各自不断重复上述步骤,直到排序完成。

         算法实现
        *
        * */

        //首先部署一个swap函数,用于互换两个位置的值。
        function swap(myArray, firstIndex, secondIndex){
            var temp = myArray[firstIndex];
            myArray[firstIndex] = myArray[secondIndex];
            myArray[secondIndex] = temp;
        }

        //然后,部署一个partition函数,用于完成一轮排序。
        function partition(myArray, left, right) {

            var pivot   = myArray[Math.floor((right + left) / 2)],
                    i       = left,
                    j       = right;


            while (i <= j) {

                while (myArray[i] < pivot) {
                    i++;
                }

                while (myArray[j] > pivot) {
                    j--;
                }

                if (i <= j) {
                    swap(myArray, i, j);
                    i++;
                    j--;
                }
            }

            return i;
        }

//接下来,就是递归上面的过程,完成整个排序。
    function quickSort(myArray, left, right) {

        if (myArray.length < 2) return myArray;

        left = (typeof left !== "number" ? 0 : left);

        right = (typeof right !== "number" ? myArray.length - 1 : right);

        var index  = partition(myArray, left, right);

        if (left < index - 1) {
            quickSort(myArray, left, index - 1);
        }

        if (index < right) {
            quickSort(myArray, index, right);
        }

        return myArray;

    }
    var arr1 = [3,2,4,5,1];
    var newArr = quickSort(arr1);
    console.log(newArr);

 

weinxin
我的微信
爱生活、爱学习的小伙伴可以通过扫一扫二维码添加我的个人微信一起交流!