关于
快速排序算法是面试中最常问到的算法,
可是网上都是不考虑重复数据的,
这里我尝试增加了重复数据的逻辑,
供大家参考.
记忆
首先推荐"算法动画图解"这款App
(官网网址http://algorithm.wiki),
感谢作者的无私奉献,可以让我们可以通过动画的形式更加牢固的记忆这一个算法.
这个软件在下面可以切换为中文版本.
代码主干
前置条件:从左向右 数字变大,以最右边为描点
1)不考虑重复
子排序{
while{
->左指针右移
->右指针左移
->交换左右内容
}
->交换描点和中间内容
将数组变成左右两个,并分别子排序
->将数组去掉描点继续排序
}
2)考虑重复
while{
...
相同时,将内容迁移到end
...
}
->更多的内容从末尾转换到中间
...
->去掉更多结尾描点
---------------------------------------------------源码如下-----------------------------------------------------
@Test
fun testQuickSort2_() {
TenSortAlgorithm.quickSort2(TenSortAlgorithm.testArrWithEqual).print()
}
object TenSortAlgorithm {
var testArrWithEqual = intArrayOf(
3, 44, 38, 5, 47,
15, 36, 26, 27, 2,
46, 4, 19, 50, 48,
2, 38, 55, 44, 44,
44, 55)
fun quickSort2(arr: IntArray): IntArray {
quickSort2(arr, 0, arr.size - 1)
return arr
}
private fun quickSort2(arr: IntArray, start: Int, end: Int) {
if(start == end){
return
}
var startIndex = start
var endIndex = end - 1
var equalNum = 0
// compare
while (startIndex < endIndex) {
when {
(arr[startIndex] == arr[end]) -> {
equalNum++
val temp = arr[startIndex]
arr[startIndex] = arr[end - equalNum]
arr[end - equalNum] = temp
if (endIndex == end - equalNum) {
endIndex--
}
}
(arr[startIndex] < arr[end]) -> {
startIndex++
}
(arr[endIndex] == arr[end]) -> {
equalNum++
if (endIndex != end - equalNum) {
val temp = arr[endIndex]
arr[endIndex] = arr[end - equalNum]
arr[end - equalNum] = temp
}
endIndex--
}
(arr[endIndex] > arr[end]) -> {
endIndex--
}
else -> {
val temp = arr[startIndex]
arr[startIndex] = arr[endIndex]
arr[endIndex] = temp
}
}
}
// compare and next
if (arr[startIndex] > arr[end]) {
var endChangeIndex = 0
while (equalNum > -1) {
val temp = arr[endIndex]
arr[endIndex] = arr[end - endChangeIndex]
arr[end - endChangeIndex] = temp
equalNum--
endIndex++
endChangeIndex++
}
if (startIndex - start > 1)
quickSort2(arr, start, startIndex - 1)
if (end - endIndex > 0)
quickSort2(arr, endIndex, end)
} else {
endIndex = end
endIndex -= equalNum
if (endIndex - start > 1)
quickSort2(arr, start, endIndex - 1)
}
}
另:
java源码中排序一部分用快速排序,一部分用合并排序
时间复杂度 平均 最坏
快速排序算法 O(Nlog2N) O(N2)
合并排序 O(Nlog2N) O(N*log2N)
网友评论