09月29, 2017

常见排序算法

常见排序算法

排序算法说明

对于评述算法优劣术语的说明

  • 稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面; 不稳定:如果a原本在b的前面,而a=b,排序之后a可能会出现在b的后面;

  • 内排序:所有排序操作都在内存中完成; 外排序:由于数据太大,因此把数据放在磁盘中,而排序通过磁盘和内存的数据传输才能进行;

  • 时间复杂度: 一个算法执行所耗费的时间。 空间复杂度: 运行完一个程序所需内存的大小

    排序算法图片总结(图片来源于网络):

    排序算法总结

冒泡排序

冒泡排序图解

冒泡排序

冒泡排序算法

// 冒泡排序
        var sort = {
            bubbleSort(arr) {
                var length = arr.length;
                for (var i = 0; i < length; i++) { //正序
                    for (var j = 0; j < length - 1 - i; j++) { //正序   每次一排序都会把最重的沉下去,并且最后一项是不需要比对的,说明后面的都是排序号好的,所以 j< length - 1 - i;
                        if (arr[j] > arr[j + 1]) {
                            arr[j] = arr[j] + arr[j + 1];
                            arr[j + 1] = arr[j] - arr[j + 1];
                            arr[j] = arr[j] - arr[j + 1];
                        }
                    }
                }
                return arr;
            },
            bubbleSort2(arr) { //改进版,记录下最后一次排序的位置,这个时候最后一次交换的位置以后的都是已经排序好的,所以下一次循环不需要后面的部分。
                var i = arr.length - 1; //初始时,最后位置保持不变
                while (i > 0) {
                    var pos = 0; //每趟开始时,无记录交换
                    for (var j = 0; j < i; j++)
                        if (arr[j] > arr[j + 1]) {
                            pos = j; //记录交换的位置
                            arr[j] = arr[j] + arr[j + 1];
                            arr[j + 1] = arr[j] - arr[j + 1];
                            arr[j] = arr[j] - arr[j + 1];
                        }
                    i = pos; //为下一趟排序作准备
                }
                return arr;
            },
            bubbleSort3(arr) { //双向冒泡排序 
                var len = arr.length - 1;
                var i = 0;
                for (i = 0; i < len; len--) { // 最重的也放在了最后面,所以len--
                    for (var j = len; j > i; j--) { //第一轮, 先将最小的数据冒泡到前面
                        if (arr[j - 1] > arr[j]) {
                            arr[j] = arr[j] + arr[j - 1];
                            arr[j - 1] = arr[j] - arr[j - 1];
                            arr[j] = arr[j] - arr[j - 1];
                        }
                    }
                    i++; // 上一轮已经将最轻的放在前面了,所以现在直接从i++开始
                    for (j = i; j < len; j++) { //第二轮, 将最大的数据冒泡到后面
                        if (arr[j] > arr[j + 1]) {
                            arr[j] = arr[j] + arr[j + 1];
                            arr[j + 1] = arr[j] - arr[j + 1];
                            arr[j] = arr[j] - arr[j + 1];
                        }
                    }
                }
                return arr;
            }
        }

        sort.bubbleSort3([9, 2, 6, 1, 11, 5, 4, 8]);
        /*
            单向排序
            待排序数组      [9, 2, 6, 1, 11, 5, 4, 8]
            第一趟排序结果: [2, 6, 1, 9, 5, 4, 8, 11]
            第二趟排序结果: [2, 1, 6, 5, 4, 8, 9, 11]
            第三趟排序结果: [1, 2, 5, 4, 6, 8, 9, 11]
            第四趟排序结果: [1, 2, 4, 5, 6, 8, 9, 11]

            双向排序
            待排序数组      [9, 2, 6, 1, 11, 5, 4, 8]
            第一趟排序结果: [1, 9, 2, 6, 4, 11, 5, 8]
            第二趟排序结果: [1, 2, 6, 4, 9, 5, 8, 11]
            第三趟排序结果: [1, 2, 4, 6, 5, 9, 8, 11]
            第四趟排序结果: [1, 2, 4, 5, 6, 8, 9, 11]
        */

冒泡排序分析

算法复杂度:

  • 平均时间复杂度 O(n²)
  • 最好情况 O(n)
  • 最坏情况 O(n²)
  • 空间复杂度 O(1)

冒泡排序是最容易实现的排序, 最坏的情况是每次都需要交换, 共需遍历并交换将近n²/2次, 时间复杂度为O(n²). 最佳的情况是内循环遍历一次后发现排序是对的, 因此退出循环, 时间复杂度为O(n). 平均来讲, 时间复杂度为O(n²). 由于冒泡排序中只有缓存的temp变量需要内存空间, 因此空间复杂度为常量O(1).

选择排序

选择排序图解

alt

选择排序算法

function selectSort(arr) {
            var length = arr.length;
            var min;
            for (var i = 0; i < length - 1; i++) {
                min = i;
                for (var j = i + 1; j < length; j++) {
                    if (arr[j] < arr[min]) {
                        min = j;
                    }
                }
                if (i != min) {
                    arr[min] = arr[min] + arr[i];
                    arr[i] = arr[min] - arr[i];
                    arr[min] = arr[min] - arr[i];
                }
            }
            return arr;
        }
/*
            待排序数组      [9, 2, 6, 1, 11, 5, 4, 8]
            第一趟排序结果: [1, 2, 6, 9 , 11, 5, 4, 8]
            第二趟排序结果: [1, 2, 6, 9 , 11, 5, 4, 8]
            第三趟排序结果: [1, 2, 4, 9, 11, 5, 6, 8]
            第四趟排序结果: [1, 2, 4, 5, 11, 9, 6, 8 ]
            第五趟排序结果: [1, 2, 4, 5, 6, 9, 11, 8 ]
            第六趟排序结果: [1, 2, 4, 5, 6, 8, 11, 9 ]
            第七趟排序结果: [1, 2, 4, 5, 6, 8, 9, 11 ]
*/

选择排序分析

算法复杂度

  • 最佳情况:T(n) = O(n²)
  • 最差情况:T(n) = O(n²)
  • 平均情况:T(n) = O(n²)
  • 空间复杂度 O(1)

算法不稳定,但是也不会花费额外空间。已经拍好序的也得花n²来判断。

本文链接:http://blog.wxink.xyz/post/sort.html

-- EOF --

Comments