【排序】快速排序 àì夳堔傛蜴生んèń 2022-12-13 04:41 155阅读 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
还没有评论,来说两句吧...