基本原理
核心思想
每次排序都会选一个基准数，小于基准数的放在左子序列，大于等于基准数的放在右子序列。
原始序列：{13, 15, 8, 54, 23}
step1：随机选一个基准数15，则其左子序列{13, 8}，右子序列{54, 23}
step2.1：序列{13, 8}随机选一个基准数8，则其左子序列{}，右子序列{13}
step2.2：序列{54, 23}随机选一个基准数23，则其左子序列{}，右子序列{54}
当子序列包含的元素个数小于等于1时停止循环，排序工作已经完成
编码思路
1、如何将待排序序列重新组合成“左子序列 + 基准数 + 右子序列”？
随机从待排序序列中选一个基准数，然后 for 循环遍历待排序序列，如果当前元素的值小于基准数，就将该元素放在左子序列。那究竟是放在左子序列的哪个位置上？这肯定涉及到元素交换，所以要维护一个索引 i，如果当前元素的值小于基准数，就和索引 i 位置上的元素互换位置。
待排序序列：{13, 67, 25, 18, 45, 23, 35, 30}，固定选最后一个元素即30为基准数，索引 i 初始值为0，索引 j 为 for 循环遍历当前元素所在的索引。
step1：遍历第一个元素13，比基准数30小，与索引 i 元素互换位置，然后 i++、j++
step2：遍历第二个元素67，比基准数30大，i 保持不变、j++
step3：遍历第三个元素25，比基准数30小，与索引 i 元素互换位置，然后 i++、j++
step4：遍历第四个元素18，比基准数30小，与索引 i 元素互换位置，然后 i++、j++
step5：遍历第五个元素45，比基准数30大，i 保持不变、j++
step6：遍历第六个元素23，比基准数30小，与索引 i 元素互换位置，然后 i++、j++
step7：遍历第七个元素35，比基准数30大，i 保持不变、j++
step8：遍历到基准数时，p 与 i 元素互换
最终结果：索引 i 元素值为30，左子序列小于基准数30，右子序列大于等于基准数30。
序列{13, 15, 8, 54, 23, 25, 17, 11, 78, 89, 67, 56, 54, 34, 97, 15}经过第一轮排序后就变成
{13, 8, 11, 15, 23, 25, 17, 15, 78, 89, 67, 56, 54, 34, 97, 54}，其中基准数15所在的索引是3。
比基准数15（索引为3）小的都在左子序列，符合预期。
package main
import “fmt”
func main() {
data := []int{13, 15, 8, 54, 23, 25, 17, 11, 78, 89, 67, 56, 54, 34, 97, 15}
fmt.Printf(“before sort:%v\n”, data)
sort(data)
// after sort:[13 8 11 15 23 25 17 15 78 89 67 56 54 34 97 54]
fmt.Printf(“after sort:%v\n”, data)
}
func sort(data []int) {
if len(data) <= 1 {
return
}
i := 0
for j := 0; j <= len(data)–1; j++ {
if data[j] < data[len(data)–1] {
temp := data[i]
data[i] = data[j]
data[j] = temp
i++
}
}
temp := data[len(data)–1]
data[len(data)–1] = data[i]
data[i] = temp
// i value:3
fmt.Printf(“i value:%v\n”, i)
}
2、代码实现中固定选最后一个元素为基准数，那如何实现随机选一个元素为基准数？
思路：rand.Seed 在 “0-len(data)-1”之间随机产生一个值，然后将该位置上的元素和最后一个元素交换位置。
package main
import (
“fmt”
“math/rand”
“time”
)
func main() {
data := []int{13, 15, 8, 54, 23, 25, 17, 11, 78, 89, 67, 56, 54, 34, 97, 15}
fmt.Printf(“before sort:%v\n”, data)
random(data)
sort(data)
// after sort:[13 15 8 15 23 25 17 11 34 54 67 56 54 78 97 89]
fmt.Printf(“after sort:%v\n”, data)
}
func sort(data []int) {
if len(data) <= 1 {
return
}
i := 0
for j := 0; j <= len(data)–1; j++ {
if data[j] < data[len(data)–1] {
temp := data[i]
data[i] = data[j]
data[j] = temp
i++
}
}
temp := data[len(data)–1]
data[len(data)–1] = data[i]
data[i] = temp
// i value:9
fmt.Printf(“i value:%v\n”, i)
}
func random(data []int) {
rand.Seed(time.Now().UnixNano())
p := rand.Intn(len(data) – 1)
fmt.Printf(“random value:%v\n”, p)
temp := data[len(data)–1]
data[len(data)–1] = data[p]
data[p] = temp
}
代码实现
package main
import (
“fmt”
“math/rand”
“time”
)
func main() {
data := []int{13, 15, 8, 54, 23, 25, 17, 11, 78, 89, 67, 56, 54, 34, 97, 15}
fmt.Printf(“before sort:%v\n”, data)
quickSort(data, 0, len(data)–1)
fmt.Printf(“after sort:%v\n”, data)
}
func randomizedPartition(data []int, low, high int) int {
rand.Seed(time.Now().UnixNano())
p := rand.Intn(high–low) + low
temp := data[high]
data[high] = data[p]
data[p] = temp
return partition(data, low, high)
}
func partition(data []int, low, high int) int {
pivot := data[high]
i := low
for j := low; j < high; j++ {
if data[j] <= pivot {
temp := data[i]
data[i] = data[j]
data[j] = temp
i++
}
}
data[high] = data[i]
data[i] = pivot
return i
}
func quickSort(data []int, low, high int) {
if high > low {
p := randomizedPartition(data, low, high)
// quickSort(data, low, p) incorrect, will cause stack overflow
quickSort(data, low, p–1)
quickSort(data, p+1, high)
}
}
时间复杂度
平均时间复杂度：O( nlog2nnlog_{2}n )
最好时间复杂度：O( nlog2nnlog_{2}n )
最坏时间复杂度：O( n2n^{2} )，选的基准数只能将序列分为一个元素与其他元素两部分，这时的快速排序退化为冒泡排序
最坏时间复杂度
（1）分区函数每次选取的基准数为序列最小元素。
（2）分区函数每次选取的基准数为序列最大元素。
具体案例：序列已经正序或逆序排好，选的基准数每次都是序列第一个元素或最后一个元素。
稳定性
排序算法的稳定性概念
大小相同的两个值在排序之前和排序之后的先后顺序不变
序列{13, 67, 25, 67,18}，排序之后能保证原序列第一个67一定在原序列第二个67的前面，就是稳定的排序算法。
排序算法稳定性的作用
A{V1:500, V2:300}、B{V1:400, V2:300}、C{V1:300, V2:200}
需求：先按V1降序排序，再按V2降序排序
预期排序结果：A{V1:500, V2:300}、B{V1:400, V2:300}、C{V1:300, V2:200}
使用快速排序算法进行排序（先说结论，快速排序是不稳定的）
先按V1降序排序：A{V1:500, V2:300}、B{V1:400, V2:300}、C{V1:300, V2:200}
再按V2降序排序，有两种可能结果，因为A和B的V2值相等。
第一种：A{V1:500, V2:300}、B{V1:400, V2:300}、C{V1:300, V2:200}
第二种：B{V1:400, V2:300}、A{V1:500, V2:300}、C{V1:300, V2:200}
快速排序算法是不稳定的
待排序序列：{15, 13, 15}，选最后一个元素即15为基准数，索引 i 初始值为0，索引 j 为 for 循环遍历当前元素所在的索引。
step1：遍历第一个元素15，大于等于基准数15，i 保持不变、j++
step2：遍历第一个元素13，比基准数15小，与索引 i 元素互换位置，然后 i++、j++
step3：遍历到基准数时，p 与 i 元素互换
最终结果：大小相同的两个元素15在排序之前和排序之后的先后顺序已经发生变化
暂无评论内容