JavaScript实现部分排序算法冒泡选择插入快排希尔

冒泡排序

// 外层遍历：由 len- 1 到 1;  i--
        // 内层遍历：0<j<i;  j++
        // 定义一个 flag 做代码优化
        function bubbleSort(arr){
            var len = arr.length;
            var flag = true;
            var tmp;
            for(var i=len-1; i>0; i--){for(var j=0; j<i; j++){if(arr[j]>arr[j+1]){tmp = arr[j];
                        arr[j] = arr[j+1];
                        arr[j+1] = tmp;
                        flag = false;
                    }    
                }
                if(flag) return arr;
            }
            return arr;
        }

选择排序

        // 外层排序：0 到 arr.length-1
        // 内层排序：i+1<=j<arr.length;
        // 当在内循环中出现一个数 arr[j]，比左边默认排好序的数 arr[minIndex] 还要小，则 minIndex = j; 遍历完成后，minIndex 此时就是未排序数组中最小值的下标；执行调换
        function selectSort(arr){
            var tmp;
            for(var i=0; i<arr.length; i++){
                var minIndex = i;
                for(var j=i+1; j<arr.length; j++){if(arr[j]<arr[minIndex]){minIndex = j;}
                }
                if(minIndex !== i){tmp = arr[i];
                    arr[i] = arr[minIndex];
                    arr[minIndex] = tmp;
                }
            }
            return arr;
        }

插入排序

// 外层循环：由 1 到 arr.length-1;
        // 内层循环：取 arr[i] 当左边默认排好序的数组中的数比 arr[i] 大时，将它们左移
        function insertSort(arr){for(var i=1; i<arr.length; i++){var tmp=arr[i];
                var j=i;
                while(j>0 && arr[j]<arr[j-1]){arr[j] = arr[j-1];
                    --j;
                }
                arr[j] = tmp;
            }
            return arr;
        }

快速排序

// 注意：需要加上 if(arr.length <=1) return arr;
        // 否则会导致栈溢出
        function quickSort(arr){if(arr.length <=1) return arr;
            var num = Math.floor(arr.length/2);
            var numValue = arr.splice(num,1);
            var left = [];
            var right = [];
            for(var i=0; i<arr.length; i++){if(arr[i]<numValue){left.push(arr[i]);
                }else{right.push(arr[i]);
                }
            }
            return quickSort(left).concat(numValue,quickSort(right));
        }

希尔排序

// 先定义一个 gap
        // 保证 gap>0
        // 然后类似插入排序算法
        function shellSort(arr){

            var len = arr.length;
            var gap = Math.floor(len/2);

            while(gap>0){for(var i=gap; i<len; i++){var tmp = arr[i];
                    var j = i;
                    while(j>gap-1 && tmp < arr[j-gap]){arr[j] = arr[j-gap];
                        j-=gap;
                    }
                    arr[j] = tmp;
                }
                gap = Math.floor(gap/2)
            }
            return arr;
        }