空间复杂度 O(n)

    1. <body>
    2. <h3>原始数据</h3>
    3. <div id="originData"></div>
    4. <h3>排序结果</h3>
    5. <div id="result"></div>
    7. <script>
    8.     let originDataDiv = document.querySelector('#originData')
    9.     let string = '5,4,2,3,1'
    10.     originDataDiv.innerHTML = string
    12.     let array = string.split(',')
    13.     let resultString = directInsertSort(array)
    15.     let result = document.querySelector('#result')
    16.     result.innerHTML = resultString.join(',')
    18.     function directInsertSort(array) {
    19.         let index
    20.         let resultArray = []
    21.         let value
    22.         for (let i = 0; i < array.length; i++) {
    23.             if (resultArray.length === 0) {
    24.                 resultArray[0] = array[i]
    25.             } else {
    26.                 value = array[i]
    27.                 index = resultArray.length - 1
    28.                 while (resultArray[index] > value && index >= 0) {
    29.                     resultArray[index + 1] = resultArray[index]
    30.                     index--
    31.                 }
    32.                 resultArray[index + 1] = value
    33.             }
    34.         }
    35.         return resultArray
    36.     }
    37. </script>
    38. </body>

    改写去重

    1. function directInsertSort(arr){
    2.     let a = []
    3.     let value 
    4.     let index
    5.     if(arr.length===0) return a
    6.     for(let i = 0;i<arr.length;i++){
    7.         if(a.length===0){
    8.             a[0] = arr[0]
    9.         }else{
    10.             value = arr[i]
    11.             index = a.length - 1
    12.             while(a[index]>value&&index>=0){
    13.                 a[index+1] = a[index]
    14.                 index--
    15.             }
    16.             if(a[index]===value){
    17.                 console.log(a)
    18.                 a[index+1] = a[index+2]
    19.                 console.log('index'+index)
    20.                 a.splice(index+1,1)
    21.                 console.log(a);
    22.             }else{
    23.                 a[index+1] = value
    24.             }
    25.         }
    26.     }
    27.     return a
    28. }

    空间复杂度 O(1)