插入排序 - 处理空列表

我想实现插入排序使用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

插入排序 - 处理空列表

回答

相关问题