1.3 額外的內(nèi)存使用

1.4 數(shù)據(jù)類型

在創(chuàng)建自己的數(shù)據(jù)類型時，我們只要實現(xiàn)Comparable接口就夠保證用例代碼可以將其排序。

要做到這一點，我們只需要實現(xiàn)一個comparaTo()方法來定義目標類型對象的自然次序。

總之，comparaTo()實現(xiàn)了我們的主鍵抽象——它給出了實現(xiàn)了Comparable()接口的任意數(shù)據(jù)類型的對象的大小順序的定義

二 選擇排序

運行時間和輸入無關

數(shù)據(jù)移動是最少的，交換次數(shù)和數(shù)組的大小是線性關系

三 插入排序

運行時間取決于輸入中元素的初始順序

插入排序?qū)τ谀承╊愋偷姆请S機數(shù)組很有效，它的運行時間是線性的

1.5 比較兩種排序算法

1.實現(xiàn)并調(diào)試它們

2.分析它們的基本性質(zhì)

3.對它們的相對性能作出猜想

4.用實驗驗證我們的猜想

1.6 希爾排序