從無序到有序
我們可以看到在無需向量的演算法中，所需要的演算法時間復雜度都不是特別理想，因此我們引入了排序演算法，將無需向量整理成為有序向量，本節中，你將體驗到“秩序”的力量，并見證一個非常高效，厲害的演算法，
文章目錄
- 從無序到有序
- 有序的好處
- 有序性甄別
- 唯一化
- 查找
- 二分查找
- 歸并排序
- 總結
有序的好處
如果你的士兵按照一定的順序排列好，你對他們進行點名、布置小隊任務什么的，當然會比亂排的要方便，對向量中的元素也是如此，當它們按照從小到大的順序排列好，你會發現很多演算法都要方便不少，
有序性甄別
前面我們提到，無需向量和有序向量的操作介面是不一樣的，所以在確定要使用什么介面之前，我們要對向量進行一個甄別，判斷他們是不是已經有序，
該演算法與氣泡排序演算法原理相同：
template<typename T>
int Vector1<T>::disordered() const
{
int n;
for (int i = 1; i < _size; i++)
{
if (_elem[i-1]>_elem[i])
{
n++;
}
}
return n;
}
唯一化
向量操作演算法中，最令我震撼和佩服的一個，
在有序向量中，我們可能會遇到值相等的元素相鄰地進行排列，我們會想要將這些重復的元素洗掉，然而在有序向量中，把這些重復元素洗掉將比在無需向量中容易，
對于無需向量中的唯一化演算法我將不再贅述，我們直接來看更為高效的這一種：
這幅圖片很直觀地展示出了我們將要采取的策略——很粗暴很直接：直接忽略那些重復的元素，把和當前元素互異的元素直接拿到當前元素的后面，
這真的是一種非常高明的演算法，我們需要消耗時間復雜度的只有把所有元素全部遍歷一遍而已！所需的時間復雜度僅僅為O(n)！相對于之前的O(n^2)可以說是優化了很多了！
下面來看看具體代碼：
template<typename T>
int Vector1<T>::uniquify()
{
Rank i = 0, j = 0;
while (++i<_size)
{
if (!_elem[j]==_elem[i])
{
_elem[++j] = _elem[i];
}
}
_size = ++j;
shrink();
return i - j;
}
下面對這段代碼進行一個簡單的說明：
我們從初始位置開始(記為j)，先把后面的每個元素與之進行比較，由于向量是有序的，所以假設后面的N個元素都和該元素相等，這些元素我們都直接略過，直到掃描到位置i，碰到了第一個和j位置不一樣的元素，此時我們的計數標i不用動，把i這個位置的元素直接拉到前面去，位置就為j+1了，然后以j+1作為比較元素，i繼續往后掃描，這樣一趟下來，就只需要O(n)復雜度啦，
查找
在有序向量中，我們有兩種查找演算法：二分查找和Fibnacci查找.
二分查找
二分查找我們采用最傳統的分而治之的思想
template<typename T>
Rank Vector1<T>::binSearch(T* A, T const& e, Rank low, Rank high)
{
while (1<high-low) //當子區間長度減少到1之前一直進行
{
Rank middle = (high - low) >> 1; //計算區間中點
(e < A[middle]) ? high = middle : low = middle; //進行比較并確立新的區間端點
}
return (e == A[low] ? low : -1); //查找失敗回傳-1
}
整個演算法的時間復雜度還是O(logn)，
歸并排序
template<typename T>
void Vector1<T>::merge(Rank low, Rank middle, Rank high)
{
T* A = _elem + low;
int 1b = middle - low;
T* B = new T[1b];
for (Rank i = 0; i < 1b; B[i] = A[i++]);
int lc = high - middle;
T* C = _elem + middle;
//以上都是構建、復制向量的程序
for (int i = 0,j=0,k=0; (j<1b)||(k<lc);)
{
if ((j < 1b) && (!(k < 1c) || (B[j] <= C[k])))
{
A[i++] = B[j++];
}
if ((k < 1c) && (!(j < 1b) || (C[k] < B[j])))
{
A[i++] = C[k++];
}
}
}
采用的也是最經典的分治策略：先分組復制陣列，得到前后子向量B和C，然后將這兩者中的小者續至A末尾，
不難得出時間復雜度為O(n)，
總結
向量到這里就結束了，我們得到了向量的模板類，在今后的學習路程中我們還會用到我們得到的向量模板類去構建別的資料結構，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/277108.html
標籤：區塊鏈