排序算法总结JavaScript实现

前言： 查找和排序算法是算法的入门知识， 其中的经典思想可以用于很多算法中。排序算法有：冒泡排序、选择排序、快速排序、归并排序、插入排序、堆排序、基数排序、桶排序等。

 

 

一。冒泡排序 【稳定、简单】

 

　　冒泡排序是最简单的排序之一了，但也是最慢的排序算法之一，其大体思想就是通过与相邻元素的比较和交换来把小的数交换到最前面。这个过程类似于水泡向上升一样，因此而得名。

　　举个栗子：对3,2,6,8,1这个无序序列进行冒泡排序。首先从后向前冒泡，1和8比较，把1交换到前面，序列变成3,2,6,1,8。同理1和6交换，变成3,2,1,6,8。2和1交换，得到3,1,2,6,8。再1和3交换，变成1,3,2,6,8，这样一次冒泡就完了，把最小的数1排到最前面了。对剩下的序列依次冒泡就会得到一个有序序列。冒泡排序的时间复杂度为O(n^2)。

function bubbleSort (arr) {
    if (arr == null || arr == undefined || arr.length === 0) {
        return;
    }
    for (var i = 0; i < arr.length - 1; i++) {
        for (var j = arr.length - 1; j > i; j--) {
            if (arr[j] < arr[j-1]) {
                var temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp;
            }
        }
        
    }
    return arr
    }
var res = bubbleSort([3,2,6,8,1])
console.log(res); // [1, 2, 3, 6, 8]

 

二。直接选择排序（选择排序）【不稳定、简单】

选择排序是通过对整体的选择,在一次排序后把最小的元素放到最前面

举个栗子，对5,3,8,6,4这个无序序列进行简单选择排序，首先要选择5以外的最小数来和5交换，也就是选择3和5交换，一次排序后就变成了3,5,8,6,4.对剩下的序列一次进行选择和交换，最终就会得到一个有序序列。其实选择排序可以看成冒泡排序的优化，因为其目的相同，只是选择排序只有在确定了最小数的前提下才进行交换，大大减少了交换的次数。选择排序的时间复杂度为O(n^2)

上js代码。。。

    function selectSort(arr) {
        if (arr == null || arr.length === 0) {
            return;
        }
        var minIndex = 0, temp;
        for(var i=0; i<arr.length-1; i++) {  //只需要比较 n-1 次
            minIndex = i;
            for(var j = i+1; j<arr.length; j++) { // 从i+1开始比较,因为minIndex默认为1, i就没必要比较了
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
                // console.log(arr)
            }
        }
        return arr;
    }

    var arr = [5,3,8,6,4];
    var res = selectSort(arr);
    console.log(res); // [3, 4, 5, 6, 8]

将每次排序后的数组打印到控制台，可以看到：

三。插入排序【稳定、简单】

 每次选择一个元素K插入到之前已排好序的部分A[1…i]中，插入过程中K依次由后向前与A[1…i]中的元素进行比较。若发现发现A[x]>=K,则将K插入到A[x]的后面，插入前需要移动元素。

贴代码如下。。。

function insertionSort(arr) {
        if (arr == null || arr.length === 0) {
            return;
        }
        var temp,j;
        for (var i = 1; i<arr.length; i++) {
            temp = arr[i];
            j = i - 1;
            while (j>=0 && arr[j] > temp) {
                arr[j+1] = arr[j];
                j--;
            }
            arr[j+1] = temp;
            console.log(arr)
        }
        return arr;
 }

 var arr = [1,8,2,3,6,0];
 var res = insertionSort(arr);
 console.log(res); // [3, 4, 5, 6, 8]

在控制台打出的排序过程如下：

代码解释：插入排序有两个循环。外循环将数组元素挨个移动,而内循环则对外循环中选中的元素及 它后面的那个元素进行比较。如果外循环中选中的元素比内循环中选中的元素小,那么数 组元素会向右移动,为内循环中的这个元素腾出位置

 前三种排序方式的比较：

选择排序和插入排序要比冒泡排序快，插入排序是这三种算法中最快的 

四。希尔排序【不稳定、较复杂】

希尔排序是在插入排序的基础上做了很大改善的一种高级排序算法，它会首先比较距离较远的元素

五。快速排序 【不稳定、较复杂】

 

快速排序是比较和交换小数和大数

举个栗子: