艾融軟件 - 線上面試題
排序算法的時間復雜度
O(n^2）：冒泡，選擇，插入
O(logn）：折半插入排序
O(nlogn)：希爾，歸并，快速，堆
O(n+k)：桶，計數，基數
（K表示桶的個數）
聚合函數
什么是聚合函數？ 聚合函數作用于一組數據，并對一組數據返回一個值。
聚合函數：AVG() SUM() MAX() MIN() COUNT()
相關知識點
排序算法的穩定性
在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩定的；否則稱為不穩定的。
穩定的排序：冒泡排序、直接插入排序、折半插入排序、歸并排序
不穩定的排序：堆排序、快速排序、希爾排序、直接選擇排序
排序算法的時間復雜度
1）一重循環的時間復雜度為O（n），兩重循環的時間復雜度為O（n^2）， 三重循環的時間復雜度為 O（n^3），依次類推；
2）二分的時間復雜度為O（logn）；
3）一個循環里套一個二分的時間復雜度為O（nlogn）。
排序算法的思想
- 冒泡排序：需要進行n-1輪排序，第i輪排序中將從第0個元素到第n-i-1個元素進行兩兩比較將該輪排序中的最大值一步一步移動都最后的位置。
- 插入排序： 先假定序列中第0個元素是有序的，從序列中第1個元素開始遍歷，將遍歷取出的元素與其前面已經排好序的元素進行比較將其插入到有序序列中的合適位置。
- 快速排序：先從序列中挑出第一個元素作為后期比較的基準。將所有比基準小的元素擺放在基準的左邊，所有比基準大的元素擺放在基準的右邊，所有和基準相同的元素擺放在基準的任一邊。在這個分區結束之后，該基準就處于序列的中間位置。遞歸地把左分區的元素和右分區的元素再進行排序。
- 選擇排序：就是不斷地從未排序的元素中選擇最大（或最小）的元素放入已排好序的元素集合中，直到未排序中僅剩一個元素為止，一般假定第一個元素是最小值
- 希爾排序：先讓數組中任意間隔為 h 的元素有序，剛開始 h 的大小可以是 h = n / 2,接著讓 h = n / 4，讓 h 一直縮小，當 h = 1 時，也就是此時數組中任意間隔為1的元素有序，此時的數組就是有序的了
- 歸并排序：將一個大的無序數組有序，我們可以把大的數組分成兩個，然后對這兩個數組分別進行排序，之后在把這兩個數組合并成一個有序的數組
- 堆排序：把堆頂的元素與最后一個元素交換，交換之后破壞了堆的特性，我們再把堆中剩余的元素再次構成一個大頂堆，然后再把堆頂元素與最后第二個元素交換….如此往復下去，等到剩余的元素只有一個的時候，此時的數組就是有序的了
- 基數排序：先以個位數的大小來對數據進行排序，接著以十位數的大小來多數進行排序，接著以百位數的大小進行排序
- 計數排序：就是把數組元素作為數組的下標，然后用一個臨時數組統計該元素出現的次數，例如 temp[i] = m, 表示元素 i 一共出現了 m 次。最后再把臨時數組統計的數據從小到大匯總起來，此時匯總起來是數據是有序的。
- 桶排序：把最大值和最小值之間的數進行瓜分，例如分成 10 個區間，10個區間對應10個桶，我們把各元素放到對應區間的桶中去，再對每個桶中的數進行排序，最后將桶進行匯總排序。
)
)
