关于

快速排序算法是面试中最常问到的算法,
可是网上都是不考虑重复数据的,
这里我尝试增加了重复数据的逻辑,
供大家参考.

记忆

首先推荐"算法动画图解"这款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)