数组和字符串的操作方法(数组和字符串都是什么类型)

导语：掌握算法-数据结构模式-数组和字符串

大体是啥？

从概念上来说，数组就是将给定类型对象们映射到一组[0, n-1]范围内的一组整数上，这里n是对象们的个数。数组的查找和插入是很快的，这使得数组适合很多应用。数组操作最常见的错误就是读最有一个数组元素的下一个元素，常常带来灾难性的后果。

没啥好说的了，举个例子吧！

问题： 编写函数，函数的参数有两个，一个是数组A， 另一个是数组A的某个索引i，这个函数的功能是从新排序数组A，使得所有比A[i]小的数都排在前面，然后是和A[i]一样大的，最后是比A[i]大的，算法的空间复杂度应该是O(1)，时间复杂度是O(|A|)。

这个问题怎么解决呢？

在这里我们假设需要维护四个数组：

smaller: 放所有比A[i]小的数。equal:放所有与A[i]一样大的数。larger:放所有比A[i]一样的数。unclassified:未被分类的数组，这里我们指向原数组。

思想很简单，遍历数组，然后挨个比较，分别往里扔就完了，最后拼在一起完事。

但在实际中我们要是这么写，虽然可以但是有点傻，下面是实际的代码：

include <vector>using std::cout;using std::endl;using std::vector;using std::swap;template <typename T>void dutch_flag_partition(vector<T> &A, const int &pivot_index){    T pivot = A[pivot_index];    int smaller = 0, equal = 0, larger = A.size() - 1;    while(equal <= larger){        if(A[equal] < pivot){            swap(A[smaller++], A[equal++]);        }        else if(A[equal] == pivot)        {            ++equal;        }        else{            swap(A[equal], A[larger--]);        }    }}int main(){    vector<int> vect = {1,2,5,1,2,7,8,9,11,23,1,2,4,6};    cout << ;    for(const auto &item : vect){        cout << item << ;    }     cout << endl;    dutch_flag_partition<int>(vect, 6);    cout << ;    for(const auto &item : vect){        cout << item << ;    }     cout << endl;}

这里是测试结果：

从代码中我们可以看到，现实中，我们并没有真的去创建四个四个数组，而是在原有的数组空间里操作，用数组的索引虚拟了一个4个空间，从代码中我们可以看到：

首先我们把A[i]定义成pivot然后初始化了4个空间索引的初始值分别为smaller = 0, equal(unclassfified)=0, larger=A.size()-1;然后我们进入循环便利，比较的逻辑如下：如果比pivot小，先交换位置，smaller索引+1,如果比pivot大，先交换位置，larger的索引-1,如果一下大，直接下一个。

本文内容由快快网络小莉创作整理编辑！