[알고리즘] 빠 른, 선택, 삽입, 힐, 병합, 쌓 기 정렬

(1) 빠 른 정렬

    

-      ：
1. pivot：  

-   
1.        pivot    
2.      pivot   ，     
3.      pivot   ，     
4.    pivot         ，       ，         ，   
5.         ，               

-   ：
const arr = [1, 4, 3, 5, 2]

function quickSort (arr) {

  if (arr.length <= 1) { //        ，   len<1 ，                
    return arr
  }

  const len = arr.length
  const pivot = Math.floor (Math.random() * len) 
  //       
  //         len-1，     ，Math.random [0, 1)，      

  let left = []
  let middle = []
  let right = []
  for (let i = 0; i < len; i++) { //    i < len    i <= len   
    if (arr[i] < arr[pivot]) {
      left.push (arr[i])
    } else if (arr[i] > arr[pivot]) {
      right.push (arr[i])
    } else if (arr[i] === arr[pivot]) {
      middle.push (arr[i])
    }
  }

  return quickSort (left).concat(middle, quickSort (right)) //       
}

const res = quickSort(arr)
console.log(res)

https://juejin.im/post/5966f57051882568b20dc3e1
https://juejin.im/post/5c8532ec6fb9a049a42fdd81#heading-7
정렬 선택 selection - sort

     selection-sort

  ：
1.          （min），    （  Y）       （j），   j < min，     ，  Y    
2.        ，       ，       （min）      （Y）     ，      

  ：
const arr = [1, 4, 3, 2]

function select_sort (arr) {
  for (let i = 0; i < arr.length; i++) { //     
    let min = i //           
    for (let j = i + 1; j < arr.length; j ++) { //        ，                  
      if (arr[j] < arr[min]) { //               
        min = j //             ，   ，          
      }
    }
    const temp = arr[i] //            ，         
    arr[i] = arr[min]
    arr[min] = temp
  }
  return arr
}

const res = select_sort (arr)
console.log (res)

https://juejin.im/post/5c6aaac351882562654abdac#heading-1
https://juejin.im/post/5c98ac16e51d451512498b19
정렬 삽입 insert - sort

     insert-sort

  ：
1.          ，      ，       
2.          1
3.                ，            ，               ，          
4.               ，           j>=0 &&     <            
5.            ，j+1                            
6.       

  ：
const arr = [1, 4, 3, 2]

function insert_sort(arr) {
  for (let i = 1; i < arr.length; i++) { //               ，   ，   1  ，           
    const cache = arr[i] //     
    let j = i - 1 //         

    while (j >= 0 && arr[j] > cache) { //           ， cache        
      arr[j+1] = arr[j]
      j--
    }

    arr[j+1] = cache //         j+1
  }
  return arr
}
const res = insert_sort(arr)
console.log(res)

https://juejin.im/post/5cd91ceb6fb9a0325031d1db
https://juejin.im/post/5ab62ec36fb9a028cf326c49
힐 정렬 셸 sort

     shell sort


  ：
1.              
2.           gap，（       gap  ，            ）
3.     ：       gap    ，         
4.   ：
                  ，              ，        ，
             ，     1 ，      
(   ：gap        1，                      )


        ：（                ）
1.     
  - [[a],  [b]] = [[b], [a]]           
2.        ：
  -            ，         ，          
  -        ，        
  -        ，                 
  -           ，                  ，         
  -        ，                    
  -       
2.       ：
const arr = [1, 4, 6, 3, 5, 2]
function insert_sort(arr) {
  for (let i = 1; i < arr.length; i++) { //      ，           ， 1  ，          
    const temp = arr[i] //         ，                
    let j = i - 1
    for (; j >= 0 && arr[j] > temp; j--) { //     ，      ，            ，        
      arr[j+1] = arr[j] //     
    }
    arr[j+1] = temp //      ，          temp，         ，      
  }
  return arr
}
const res = insert_sort(arr)
console.log(res, 'res')




3.       ：
-                  ，      ，      ，       ，  gap     
-    gap   ，      arr.length / 2
const arr = [1, 4, 6, 3, 5, 2]

function shell_sort(arr) {
  let gap = Math.floor(arr.length / 2) //      gap，          
  for (; gap >= 1; gap = Math.floor(gap/2)) { 
  //          ，     ，    0  （     ）
  //   ：gap      1，               
    for (let i = gap; i < arr.length; i++) { 
    //     ， gap  
    //  gap  ，  gap + gap     arr.length  
      const temp = arr[i]
      let j = i - gap
      //      i-gap      ，   j >= 0
      for (; j >= 0 && arr[j] > temp; j = j-gap) {
          arr[j + gap] = arr[j]
      }
      arr[j+gap] = temp
//    for     ：
// for(; j >= 0; j = j - gap) {
//   if (arr[j] > temp) {
//       arr[j+gap] = arr[j]
//   } else {
//     break
//   }
// }     
    }
  }
  return arr
}
const res = shell_sort(arr)
console.log(res)

도해https://www.jianshu.com/p/fe5ccc63d523
https://juejin.im/post/5ab62ec36fb9a028cf326c49#heading-23
병합 정렬 merge - sort

     merge-sort

  ：
1.              ，            1
2.                  ，    ，          ，    

  ：
const arr = [1, 4, 2, 5, 3]

//     
function merge_sort (arr) {
  if (arr.length <= 1) return arr //               0    1

  let mid = Math.floor(arr.length / 2), //         
    left = arr.slice(0, mid), //     
    right = arr.slice(mid) //     

  return merge(merge_sort(left), merge_sort(right)) //   
}

//   
function merge(left, right) {
  let result = []
  
  //   ：left   right           ，          
  //                  ，       
  //             
  while (left.length && right.length) {
    result.push(left[0] < right[0] ? left.shift() : right.shift())
  }
  //          ，            ，                
  //      while         ，       result  
  //           
  result = result.concat(left.length ? left : right)
  return result
}

const res = merge_sort(arr)
console.log(res)

https://juejin.im/post/5c9cf808f265da611846c015#heading-15
더미 정렬

    heap-sort

    ：
1.    
  -    (i)   (   2i)，(   2i+1)   
2.  
  -     -         
  -     -          
3.      
 -            ，           ，     

4.             ？
  -                
    -                     ，          
    -         n，             n/2
    -     ：
      1.          ：                 
      2.             ，        （       n,      n/2  ）
      3.         ，      ，     
  
  -           ，             
    1.        ，            
    2.                      ，          
    3.       ，     (      )，      
    -                   

//   
function heapSort(arr) {
  var arr_length = arr.length
  if (arr_length <= 1) return arr
  // 1.     
  //          
  //            ，                  
  for (var middle = Math.floor(arr_length / 2); middle >= 0; middle--) maxHeapify(arr, middle, arr_length)
  // 2.   ，      
  for (var j = arr_length; j >= 1; j--) {
    // 2.1.                 
    swap(arr, 0, j - 1)
    // 2.2.            
    maxHeapify(arr, 0, j - 2)
  }
  return arr
}
//     
function maxHeapify(arr, middle_index, length) {
  // 1.            
  var largest_index = middle_index
  // 2.         
  var left_index = 2 * middle_index + 1,
    right_index = 2 * middle_index + 2
  // 3.          
  //           ，          ，           
  //     
  if (left_index <= length && arr[left_index] > arr[largest_index]) largest_index = left_index
  //     
  if (right_index <= length && arr[right_index] > arr[largest_index]) largest_index = right_index
  // 4.    largest_index      ，        ，    
  if (largest_index !== middle_index) {
    swap(arr, middle_index, largest_index)
    //                 ，            
    //                   ，    
    maxHeapify(arr, largest_index, length)
  }
}

https://juejin.im/post/5c9cf808f265da611846c015#heading-9