Skynet

          ---------- ---------- 我的新 blog : liukaiyi.cublog.cn ---------- ----------

            BlogJava :: 首頁 :: 聯系 :: 聚合  :: 管理
            112 Posts :: 1 Stories :: 49 Comments :: 0 Trackbacks

          # 快排 和 分治 很像 都是分而治之 ,但他們卻是 相反的 方式排序 :
          分治 是想拆分完成后,合并以有序的小段進行 排序 ,而快排是直接由原始的“拆分”來排序


          #encoding=utf-8
          #
          從 大 到 小
          def partition(A,p,r):
              tmp
          =A[p]
              
          while True :
                  
          while p+1<and A[p] > tmp : p+=1
                  
          while r-1>and A[r] <= tmp : r-=1    
              
          if A[p]<=A[r]: A[p],A[r]=A[r],A[p]
              
          if r-1<=p : return p


          def quickSort(A,p,r):
              
          if p<r:
                  q
          =partition(A,p,r)
                  quickSort(A,p,q)
                  quickSort(A,q
          +1,r)

          A
          =[9,61,7,14,-1,7,667,3,6,8]
          print A
          quickSort(A,0,len(A)
          -1)
          print A
          # 結果
          [667, 61, 14, 9, 8, 7, 7, 6, 3, -1]



          圖解:
          一次迭代過程描述 (從小到大):
          1. 以 A[0] 為切分點 用臨時變量 記錄 這里是 切分點 = [5]
          2. 分別起 2枚指針 [切分起左,右]
          3. 分別向中間 靠攏 , 當左指針指向值大于 切分點 停止 左 , 右指針指向值 小于 切分點 停止 右 。
          4. 判斷 是否是  停止點 上 左值 小于 右值 是:交換兩指針值 !

          第一次迭代后 : 
            以初始分隔 [5]  就已經切分好了 小于 5 的左 ,大于等于5 的右




          整理 www.aygfsteel.com/Good-Game
          posted on 2009-12-03 17:11 劉凱毅 閱讀(1686) 評論(0)  編輯  收藏 所屬分類: python算法/函數
          主站蜘蛛池模板: 拉萨市| 蒙阴县| 平度市| 栾川县| 桂东县| 汉阴县| 右玉县| 信宜市| 荥经县| 疏勒县| 简阳市| 凭祥市| 绥中县| 佛教| 西吉县| 大新县| 舒兰市| 廉江市| 西乌珠穆沁旗| 额敏县| 洪湖市| 都安| 蓬莱市| 金阳县| 伊春市| 隆安县| 彰化县| 新泰市| 龙里县| 囊谦县| 清河县| 七台河市| 望城县| 达孜县| 吉首市| 湖南省| 株洲县| 莲花县| 霍林郭勒市| 巴东县| 新干县|