插入排序 - 處理空列表

我想實現插入排序使用stl和向量。我想出了這個解決方案迄今：插入排序 - 處理空列表

void insertionSort(vector<int> &v, int splitIndex); 

int main() { 

    //vector<int> x = {55,33,99,11,22,44}; 
    //vector<int> x = {55}; 
    //vector<int> x = {55,11}; 
    vector<int> x; 

    insertionSort(x, 0); 

    printVector(x); 

    return 0; } 

void insertionSort(vector<int> &v, int splitIndex) { 

    vector<int>::iterator right = v.begin() + splitIndex + 1; 

    if(right == v.end()) 
     return; 

    vector<int>::iterator left = v.begin() + splitIndex; 

    while(*right < *left && right != v.begin()) { 
     iter_swap(right, left); 
     right--; 
     left--; 
    } 

    insertionSort(v, splitIndex+1); }

它的工作在所有情況下，除了空載體的情況下，因爲「正確」的指針將指向矢量限制之外。我知道它可以通過在開頭添加一個條件是固定的：

if(v.size() < 2) return;

但我不喜歡那朵條件將爲每個遞歸調用執行。

請指教。謝謝。

來源

2017-02-26 Heidar

我想你可以簡單地檢查是否'splitIndex +1 JustRufus

在你嘗試[看看這裏的實現]之後（http://stackoverflow.com/questions/24650626/how-to-implement-classic-sorting-algorithms-in-modern-c） – PaulMcKenzie

一般這種說法

vector<int>::iterator right = v.begin() + splitIndex + 1;

，會導致不確定的行爲，特別是當VEC tor是空的。

這個循環

while(*right < *left && right != v.begin()) { 
    iter_swap(right, left); 
    right--; 
    left--; 
}

也可以有未定義的行爲，因爲比較提領迭代器*right < *left之前，應先確保right != v.begin()。否則，迭代器left將超出向量的迭代器的有效範圍。

我的建議如下函數定義

#include <iostream> 
#include <vector> 
#include <iterator> 
#include <algorithm> 

void insertionSort(std::vector<int> &v, std::vector<int>::size_type i = 0) 
{ 
    if (i < v.size()) 
    { 
     auto right = std::next(v.begin(), i); 
     auto left = right; 

     for (; right != v.begin() && *right < *--left; --right) 
     { 
      std::iter_swap(right, left); 
     } 

     insertionSort(v, i + 1); 
    } 
} 


int main() 
{ 
    std::vector<int> v0; 
    std::vector<int> v1 = { 55 }; 
    std::vector<int> v2 = { 55, 11 }; 
    std::vector<int> v3 = { 55, 33, 99, 11, 22, 44 }; 

    insertionSort(v0); 

    std::cout << "v0:"; 
    for (int x : v0) std::cout << ' ' << x; 
    std::cout << std::endl; 

    insertionSort(v1); 

    std::cout << "v1:"; 
    for (int x : v1) std::cout << ' ' << x; 
    std::cout << std::endl; 

    insertionSort(v2); 

    std::cout << "v2:"; 
    for (int x : v2) std::cout << ' ' << x; 
    std::cout << std::endl; 

    insertionSort(v3); 

    std::cout << "v3:"; 
    for (int x : v3) std::cout << ' ' << x; 
    std::cout << std::endl; 

    return 0; 
}

程序輸出是

v0: 
v1: 55 
v2: 11 55 
v3: 11 22 33 44 55 99

來源

2017-02-26 13:58:10

非常感謝！真的有幫助 – Heidar

@ HeidarMostafa根本沒有。不用謝。 –

如果你將創建一個啓動方法，這將檢查數組的大小，且僅當大於2，將調用原始的方法：

insertionSort(x);

將被實現爲：

void insertionSort(vector &v){ 
    if(v.size() < 2) return; 
    insertionSort(v, 0); 
}

來源

2017-02-26 12:57:33 yairo

插入排序 - 處理空列表

回答

相關問題