js实现一冒泡，插入，快排算法

软件设计

2017-04-27

关注关注

#排序算法中：

不稳定：快速排序，选择排序，堆排序，希尔排序（快选堆希）

稳定：插入排序，冒泡排序，归并排序，基数排序（插冒归基）

算法的稳定性判断：排序前2个相等的数在序列中的前后位置顺序与排序后它们两个的前后位置顺序相同

冒泡排序（应用于数据规模很小时）

<!DOCTYPE html>
<html>
<head>
    <meta charset="utf-8">
    <title>冒泡</title>
</head>
<body>
<script type="text/javascript">
    var arr = [9, 2, 4, 1, 8];
    function bubbleSort(arr) {
        var i = arr.length;
        var j;
        var temp;
        while (i > 0) {
            for (j = 0; j < i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
            i--;
        }
        return arr;
    }
    var arrSorted = bubbleSort(arr);
    console.log(arrSorted);
    alert(arrSorted);
</script>
</body>
</html>

#数组外循环次数就为数组长度。每一次外循环在内循环两两比较后，得到一个最大的值排到数组尾部。

插入排序

<!DOCTYPE html>
<html>
<head>
    <meta charset="utf-8"/>
    <title>直接插入</title>
    <body>
      <script type="text/javascript" >
        var arr=[5,2,4,6,1,3];
        function insertSort(){
            var key;
            var i;
            for(var j=1;j<arr.length;j++){
                key=arr[j];
                i=j-1;
                while(i>-1&&arr[i]>key){
                    arr[i+1]=arr[i];
                    i=i-1;
                }
                arr[i+1]=key;
                }
            return arr;
            }
        var newsort = insertSort(arr);
        console.log(newsort);
        alert(newsort);
    </script>
</body>
</html>

快速排序

<!DOCTYPE html>
<html>
<head>
    <meta charset="utf-8">
    <title>快排</title>
</head>
<body>
<script type="text/javascript">
    var arr = [90,9,12,6,30,60,36,32,40];
      function quickSort(arr){
        if (arr.length <= 1) { return arr; }
         var pivotIndex = Math.floor(arr.length / 2); //取基值的下标
         var pivot = arr.splice(pivotIndex, 1)[0];    //删除基值后的第一个值，并返回该值
         var left = [];  //定义一个左数组
         var right = [];
         for (var i = 0; i < arr.length; i++){
           if (arr[i] < pivot) {
              left.push(arr[i]); //左边数组
            } else {
              right.push(arr[i]);
             }
         }
        return quickSort(left).concat([pivot], quickSort(right));
      }
        //concat() 方法用于连接两个或多个数组,该方法不会改变现有的数组，而仅仅会返回被连接数组的一个副本。
    var newsort = quickSort(arr);
    console.log(newsort);
    alert(newsort);
</script>
</body>
</html>

#分组，找一个基准，小的数放左边，大的数放右边，依次分组直到数组元素为一

冒泡算法 js