Scalaクイックソートアルゴリズム

一、ソースコード

def sort(ls: List[Int]): List[Int] = {  
      ls match {  
            case Nil => Nil  //      ，     
            case base :: tail => {  //     
                    val (left, right) = tail.partition(_ < base) //                            
                    sort(left) ::: base :: sort(right)  //         ——sort(       )+  +sort(       )
            }  
     }
}

二、アルゴリズムの核心
1)クイックソート比較の基準として要素を事前に選択します.基准より大きい数を右に、基准より小さい数を左に、一度に大きい、小さいの2种类に分けます.
2)各クラスは,1つの基準を選択することによって再びサイズの分類を行う.左右にデータがないまで.
三、再帰的な解釈
再帰を理解する鍵は、まずそれを受け入れることにある.「sort関数は入力したリストをソートできる」と事前に示唆した.
この暗示に従ってsort関数の体内に入り,2つの状況に分けた.
1)伝達されたものがNilであればNilに戻る--そう、sortがNilをソートする.
2)Nilでない場合、sortはリストlsを2つの部分leftとrightに分解し、実際には最初のtailもある.次に、並べ替えられたleft+ヘッダbase+で並べ替えられたrightのリストを返します.もちろんsortメソッドはその承諾を実現し,返されるリストはシーケンス化されている.
クイックソートを理解したのは幸いではありませんが、その後、このヒントを飛び出して、なぜ2)のsortがソートを完了できるのかを説得する必要があります(この場合、内部の自己呼び出しを別の関数と見なす必要があります).
合理的な解釈はsortがリストに入ることができることです
左右の2つの部分に分割し、1つの分割関数を使用してNilになるまで分割を続けます.ここでの分割関数はsortであり,この解釈の重点はソートではなく「分割」にある.すなわち,1)は受け入れられるので,2)から1)に移行してsortがソートを完了できるようにする.
これは私の迅速なソートに対する理解で、後でいつの間にか証明になって、もちろんこれは証明ではありません.私の目的は、迅速なソートにおける再帰的な考えを伝えることです.