JS实现各种排序算法

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title></title>
</head>
<body>
    <script>
        var arr1 = [10, 8, 1, 4, 9, 2, -1, -2, 0];  
        var arr2 = [10, 8, 1, 4, 9, 2, -1, -2, 0];  
        var arr3 = [10, 8, 1, 4, 9, 2, -1, -2, 0];  
        var arr4 = [10, 8, 1, 4, 9, 2, -1, -2, 0];  
        var arr5 = [10, 8, 1, 4, 9, 2, -1, -2, 0];  
        var arr6 = [10, 8, 1, 4, 9, 2, -1, -2, 0];  
        var arr7 = [10, 8, 1, 4, 9, 2, -1, -2, 0];  
        /*
         * 冒泡排序
         * 时间复杂度n的平方
         *
         */
        function bubbleSort(arr) {
                      var i,j,exchange=1;
                      var n=arr.length;
                      for(i = 0;i < n-1 && exchange;i++) {
                             exchange=0;
                             for(j=n-2; j>=i ;j--){
                                        if(arr[j]>arr[j+1]){
                                                    var temp=arr[j+1];
                                                    arr[j+1]=arr[j];
                                                    arr[j]=temp;
                                                    exchange=1;
                             }
                       }
                       if(exchange==0){
                                 break;
                       }
            }
            return arr;
        }
        /*
         * 选择排序
         * 时间复杂度n的平方
         *
         */
        function selectSort(arr) {
            for(var i = 0;i < arr.length - 1;i++) {
                var minIndex = i;
                for(var j = i;j < arr.length;j++) {
                    if(arr[minIndex] > arr[j]) {
                        minIndex = j;
                    }
                }
                if(minIndex != i) {
                    var temp = arr[i];
                    arr[i] = arr[minIndex];
                    arr[minIndex] = temp;
                }
                }
                   return arr;
               }
        /*
         * 插入排序
         * 构造有序区与无序区
         * 左边是有序区
         * 右边是无序区
         * 接下来几步:
         * 1. 保存要被插入的数
         * 2. 保存有序区的最大的数的下标
         * 3. 开始移动
         * 4. 插入
         *
         */
        function insertSort(arr) {
            for(var i = 1;i < arr.length;i++) {
                if(arr[i - 1] > arr[i]) {
                    var guard = arr[i];
                    var j = i - 1;
                    while(j >= 0 && arr[j] > guard) {
                        arr[j + 1] = arr[j];
                        j--;
                    }
                    arr[j + 1] = guard;
                }
            }
            return arr;
        }
        /*
         * 快速排序
         * 快速排序的思想是分治法
                 “快速排序”的思想很简单，整个排序过程只需要三步：
　              （1）首先选一个轴值（即比较的基准）
　　            （2）通过一趟排序将待排序的记录分割成独立的两部分，前一部分的关键码均小于
                      或等于轴值，后一部分的关键码均大于或等于轴值。轴值元素则排在这两部分中间。
                      实际实现是：建立两个数组，分别存储左边和右边的数组
　              （3）利用递归，分别对这两部分重复上述方法。
         *
         */
        function quickSort(arr) {
            if(arr.length <= 1) {
                return arr;   //如果数组只有一个数，就直接返回；
            }
            var pivotIndex = Math.floor(arr.length / 2); //选取轴值位置：找到中间
//数的索引值，如果是浮点数，则向下取整
            var pivot = arr.splice(pivotIndex, 1)[0];//找到中间数的值
            var leftArr = [];
            var rightArr = [];
            for(var i = 0;i < arr.length;i++) {
                if(arr[i] > pivot) {
                    rightArr.push(arr[i]); //基准点的右边的数传到右边数组
                } else {
                    leftArr.push(arr[i]); //基准点的左边的数传到左边数组
                }
            }
                        //递归
            return quickSort(leftArr).concat(pivot,quickSort(rightArr));
        }

        console.log("冒泡排序:" + bubbleSort(arr1));
        console.log("选择排序:" + selectSort(arr2));
        console.log("插入排序:" + insertSort(arr3));
               alert(quickSort([32,45,37,16,2,87]));//弹出“2,16,32,37,45,87”
    </script>
</body>
</html>
Seasons123 / blog-FE

JS实现各种排序算法 #63
