美文网首页
快速排序算法

快速排序算法

作者: 嘉_佑 | 来源:发表于2019-05-31 17:36 被阅读0次

    关于

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

    记忆

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

    相关文章

      网友评论

          本文标题:快速排序算法

          本文链接:https://www.haomeiwen.com/subject/zcvgtctx.html