2.1 初級(jí)排序算法

• • 2.1.1 選擇排序
  • 2.1.2 插入排序
  • 2.1.3 選擇、插入排序比較
  • 2.1.4 希爾排序
  • 2.1.5 其他
  • • 數(shù)據(jù)類型
    • 幾種典型的部分有序數(shù)組
    • 插入排序中的哨兵

2.1.1 選擇排序

1.思想
不斷地選擇剩余元素之中的最小者

2.1.2 插入排序

1.思想
插入已經(jīng)有序的數(shù)組中的適當(dāng)位置，其余元素在插入之前都向右移一位

2.最優(yōu)適用情況

• 部分有序的數(shù)組；
• 小規(guī)模數(shù)組

2.1.3 選擇、插入排序比較

測(cè)試數(shù)組比較/次數(shù)交換/次數(shù)

選擇排序	長度為N	N2/2	N
插入排序	長度為N且主鍵不重復(fù)	最壞：N2/2 最好：N2/2	最壞：N-1 最好：0

比較兩種排序算法：sortCompare()

2.1.4 希爾排序

1.思想
使數(shù)組中任意間隔為h的元素有序的

2.最優(yōu)適用情況

• 中等大小的數(shù)組；
• 需要解決一個(gè)排序問題而又沒有系統(tǒng)排序函數(shù)可用，可先用希爾，再考慮是否值得用其他替代

2.1.5 其他

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

實(shí)現(xiàn)Comparable()接口

幾種典型的部分有序數(shù)組

• 數(shù)組中的每個(gè)元素距離他的最終位置都不遠(yuǎn)
• 一個(gè)有序的大數(shù)組接一個(gè)小數(shù)組
• 數(shù)組中只有幾個(gè)元素的位置不正確

插入排序中的哨兵

插入排序的實(shí)現(xiàn)中先找出最小的元素將其置于數(shù)組的最左邊，這樣就能去掉內(nèi)循環(huán)的判斷條件j>o，這是一種常見的規(guī)避邊界測(cè)試的方法，能夠省略判斷條件的元素通常被稱為哨兵

總結(jié)

以上是生活随笔為你收集整理的《算法》学习笔记2.1 初级排序算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。