【排序】快速排序

àì夳堔傛蜴生んèń 2022-12-13 04:41 207阅读 0赞

#### 快速排序 ####

[快速排序][Link 1]和冒泡排序都是是交换排序中的一种。

#### 基本思想 ####

1，在数列中找准一个基准点`pivot`。  
    2，将比基准点小的所有值放在基准点的左边，将比基准点大的放在基准点的右边【相等的可以任意放置】。  
    3，对左边的子数列和右边的子数列，重复1到3的步骤。分而治之，是的递归来了。

#### 代码 ####

var sort = (arr, low, high) => { 
    	  if (!arr || arr.length === 1) return arr
    	  // 重要的边界条件
    	  if (low > high) return  
    	  let pivotKeyIndex = getPartitionIndex(arr, low, high)
    	  sort(arr, low, pivotKeyIndex - 1)
    	  sort(arr, pivotKeyIndex + 1, high)
    	  return arr
    	}
    	
    	var getPartitionIndex = (arr, low, high) => { 
    	  let key = arr[low]
    	  while(low < high) { 
    	    // high开始的已经大于key，不需要移动，只需要继续往前
    	    while ( arr[high] >= key && low < high) high--
    	    arr[low] = arr[high]  
    	    // low处的值已经小于key，不需要移动，只需要继续往后
    	    while (arr[low] < key && low < high)  low++
    		arr[high] = arr[low]
    	  }
    	  // pivotKey放到中间index，此时左边全是比pivotKey小，右边比他大
    	  arr[low] = key
    	  return low
    	}
    	console.log(sort([5,2,4,6,1,3], 0, 5))
    	console.log(sort([9,8,6,10,2,7,20], 0, 6))
    	console.log(sort([9,8,6,10,2,7,20,2], 0, 7)) // 重复的情况

`getPartitionIndex`方法可以改进一下

var getPartitionIndex = (arr, low, high) => { 
      let key = arr[low]
      while(low < high) { 
        // high开始的已经大于key，不需要移动，只需要继续往前
        while ( arr[high] >= key && low < high) high--
    
        // method 1
        // arr[low] = arr[high] 
        
        // method 2
        if (low < high) { 
          arr[low] = arr[high]
          low++
        }
    
        // method wrong
        // if (arr[high] < key) { 
          // low++
        // }
        // low处的值已经小于key，不需要移动，只需要继续往后
        while (arr[low] < key && low < high)  low++
    
        // method 1
        // arr[high] = arr[low]
    
        // method 2
        if (low < high) { 
          arr[high] = arr[low]
          high--
        }
    
        // method wrong
        // if (arr[low] > key) { 
          // high--
          // console.log(arr, '>')
        // }
      }
      arr[low] = key
      return low
    }

资料： [王卓老师-快速排序][-]

[Link 1]: https://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F
[-]: https://www.bilibili.com/video/av38482542