五、哈希表

1. 哈希算法

將數據通過哈希算法映射成一個鍵值，存取都在同一位置實現數據的高效存儲和查找

將時間復雜度盡可能降低至O(1)

2. 哈希碰撞

多個數據通過哈希算法得到的鍵值相同，稱為產生哈希碰撞

3. 哈希表

構建哈希表存放0-100之間的數據

將0 - 100之間的數據的個位作為鍵值

4. 哈希表的相關操作

1. 插入元素

2. 遍歷輸出哈希表

3. 查找元素’

4. 銷毀哈希表

主函數：

結果：

六、排序和查找算法

建立和輸出被排序元素10000個

1. 冒泡排序

1.?時間復雜度為O(n^2)

2. 穩定的排序算法

3.?耗時:190 - 210ms

4. 運行原理：相鄰的兩個元素比較，大的向后走，小的向前走

2. 選擇排序

1.?時間復雜度為O(n^2)

2. 不穩定的排序算法

3.?耗時:120 - 130ms

4. 運行原理：從前到后找最小值與前面的元素交換

3. 插入排序

1.?時間復雜度為O(n^2)。若數組有序，時間復雜度降低至O(n)

2. 穩定的排序算法

3.?耗時:70ms - 80ms

4. 運行原理

將數組中的每個元素插入到有序數列中

先將要插入的元素取出

依次和前面元素比較，比元素大的向后走，直到前一個元素比要插入的元素小，或者到達有序數列開頭停止

最后插入被取出的元素

4. 希爾排序

1.?時間復雜度為O(nlogn)

2. 不穩定的排序算法

3.?耗時: 5 - 10ms

4. 運行原理

通過選擇不同的步長，將數組拆分成若干個小的數組實現插入排序

若干個小的數組稱為有序數列后，使得數組中的數據大致有序

最后再對整體完成一個插入排序

5. 快速排序

1.?時間復雜度為O(nlogn)

2. 不穩定的排序算法

3.?耗時:4 - 10ms

4. 運行原理

選擇左邊的作為鍵值，從后面找一個比鍵值小的放前面，從前面找一個比鍵值大的放后面

左右兩邊有元素則遞歸調用快速排序

??

6. 折半查找 -- 二分查找