网站的域名技巧和空间选择,紧急紧急626969,上海网页制作步骤,阿里云 wordpress 响应时间前天给大家分享了归并排序#xff0c;但是它不是原地排序算法#xff0c;需要消耗额外的内存空间#xff0c;今天给大家分享的是江湖无人不知无人不晓的快排--快速排序。快排是小生接触开发学会的第一个排序算法快速排序原理快排也用到了分治思想。快排的核心思…前天给大家分享了归并排序但是它不是原地排序算法需要消耗额外的内存空间今天给大家分享的是江湖无人不知无人不晓的快排--快速排序。快排是小生接触开发学会的第一个排序算法快速排序原理快排也用到了分治思想。快排的核心思想是如果要排序的数组中下标从 p 到 r 之间的一组数据我们选择 p 到 r 之间的任意一个数据作为分区点 pivot。我们遍历p 到 r 之间的数据将小于 pivot 的放到左边将大于 pivot 的放到右边将 pivot 放到中间。经过这一步之后数组 p 到 r 之间的数据就被分成了三个部分前面 p 到 q-1 之间都是小于 pivot 的中间是 pivot ,后面的 q1 到 r 之间都是大于 pivot 的。如下图根据分治、递归的处理思想我们可以用递归排序从下标 p 到 q-1 之间的数据和下标从 q1 到 r 之间的数据直到区间缩小为1就说明所有的数据都有序了。快排不需要归并那样做合并也不需要额外的存储空间在时间复杂度一样的情况下有着比归并更好的空间复杂度表现。快排首先找到分区点一般我们会将数组第一个或最后一个元素作为 pivot我们以最后一个作为分区点 pivot然后通过两个变量 i 和 j 作为下标来循环数组当下标 j 对应数据小于 pivot 时交换 i 和 j 对应数据并且将 i往前移动一位否则 i 不动下标 j 始终是往前移动的 j 到达终点后将 pivot 如下标 i 对应数据交换这样最终将 pivot 置于数组中间[0...i-1]区间的数据都比 pivot 小[i1...j] 之间的数据都比 pivot 大我们以递归的方式循环处理最终整个数组都会变成有序的如下图因为分区的过程涉及交换操作如果数组中有两个相同的元素比如序列 7 95736 经过第一次分区操作之后两个 7的相对先后顺序会改变。所以快速排序并不是一个稳定的排序算法。代码示例Go语言package mainimport fmtfunc main() { arr : []int{8, 3, 4, 5, 9, 2, 1} QuickSort(arr) fmt.Println(arr)}func QuickSort(arr []int) { separateSort(arr, 0, len(arr)-1)}func separateSort(arr []int, start, end int) { if start end { return } i : partition(arr, start, end) separateSort(arr, start, i-1) separateSort(arr, i1, end)}func partition(arr []int, start, end int) int { pivot : arr[end] var i start for j : start; j end; j { if arr[j] pivot { if !(i j) { arr[i], arr[j] arr[j], arr[i] } i } } arr[i], arr[end] arr[end], arr[i] return i}PHP示例function quick_sort($nums){ if (count($nums) 1) { return $nums; } quick_sort_c($nums, 0, count($nums) - 1); return $nums;}function quick_sort_c($nums, $p, $r){ if ($p $r) { return; } $q partition($nums, $p, $r); quick_sort_c($nums, $p, $q - 1); quick_sort_c($nums, $q 1, $r);}// 寻找pivotfunction partition($nums, $p, $r){ $pivot $nums[$r]; $i $p; for ($j $p; $j $r; $j) { // 原理将比$pivot小的数丢到[$p...$i-1]中剩下的[$i..$j]区间都是比$pivot大的 if ($nums[$j] $pivot) { $temp $nums[$i]; $nums[$i] $nums[$j]; $nums[$j] $temp; $i; } } // 最后将 $pivot 放到中间并返回 $i $temp $nums[$i]; $nums[$i] $pivot; $nums[$r] $temp; return $i; } $nums [4, 5, 6, 3, 2, 1]; $nums quick_sort($nums); print_r($nums);JS示例const swap (arr, i, j) { const temp arr[i] arr[i] arr[j] arr[j] temp}// 获取 pivot 交换完后的indexconst partition (arr, pivot, left, right) { const pivotVal arr[pivot] let startIndex left for (let i left; i right; i) { if (arr[i] pivotVal) { swap(arr, i, startIndex) startIndex } } swap(arr, startIndex, pivot) return startIndex}const quickSort (arr, left, right) { if (left right) { let pivot right let partitionIndex partition(arr, pivot, left, right) quickSort(arr, left, partitionIndex - 1 left ? left : partitionIndex - 1) quickSort(arr, partitionIndex 1 right ? right : partitionIndex 1, right) }}性能分析最后我们看下快速排序的性能和稳定性时间复杂度是O(nlogn)同样要优于冒泡和插入排序空间复杂度不需要额外的空间存放排序的数据是原地排序算法稳定性涉及数据交换可能破坏原来相等元素的位置排序所以是不稳定的排序算法
