關(guān)于

快速排序算法是面試中最常問到的算法,
可是網(wǎng)上都是不考慮重復(fù)數(shù)據(jù)的,
這里我嘗試增加了重復(fù)數(shù)據(jù)的邏輯,
供大家參考.

記憶

首先推薦"算法動畫圖解"這款A(yù)pp

(官網(wǎng)網(wǎng)址http://algorithm.wiki),
感謝作者的無私奉獻(xiàn),可以讓我們可以通過動畫的形式更加牢固的記憶這一個算法.
這個軟件在下面可以切換為中文版本.

代碼主干

前置條件:從左向右 數(shù)字變大,以最右邊為描點

1)不考慮重復(fù)

子排序{
  while{
      ->左指針右移
      ->右指針左移
      ->交換左右內(nèi)容
  }
->交換描點和中間內(nèi)容
    將數(shù)組變成左右兩個,并分別子排序
->將數(shù)組去掉描點繼續(xù)排序
}

2)考慮重復(fù)

  while{
  ...
  相同時,將內(nèi)容遷移到end
  ...
}

->更多的內(nèi)容從末尾轉(zhuǎn)換到中間 
    ...
->去掉更多結(jié)尾描點

---------------------------------------------------源碼如下-----------------------------------------------------

    @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源碼中排序一部分用快速排序,一部分用合并排序
時間復(fù)雜度 平均 最壞
快速排序算法 O(Nlog2N) O(N2)
合并排序 O(Nlog2N) O(N*log2N)