int Huafen(int A[],int L,int R){
int mid = A[L];
while(L < R){ //注意这里是while
while(A[R] >= mid && L < R)
R--;
A[L] = A[R];
while(A[L] <= mid && L < R);
L++;
A[R] = A[L]
}
A[L] = mid;// 易忘
return L;
}
void Qsort(int A[],int L,int R){
if(L >= R){
return ;//退出递归
}
int m = Huafen(A,L,R);
Qsort(A,L,m-1);
Qsort(A,m+1,R);
}
void merge (int a[],int b[]) {
int c[la+lb];//建立辅助数组C
int i = 0, j = 0, k = 0;
while(i < a.size() && j < b.size()){
if(a[i] < b[j]){
c[k] = a[i];
i++;
k++;
}
else {
c[k] = b[j];
j++;
k++;
}
}
//有一方被遍历完，退出循环
if(i < a.size()){ //数组a未被遍历完成，则后续元素时间赋值
c[k++] = a[i++];
}
else{
c[k++] = b[j++];
}
}
}
//时间：o(a.size()+b.size())
//空间：o(a.size()+b.size())
void reverse(int a[],int n){//n为数组a的长度
int t = 0;
for(int i = 0; i < n/2; i++){
a[i] = t;
a[i] = a[n-1-i];
a[n-1-i] = t;
}
return ;
}
void delete_x(int a[],int x){
for(int i = 0; i < a.size(); i++){
if(a[i] == x){
for(int j = i; j < a.size(); j++){
a[j] = a[j+1];
}
}
}
return ;
}
//进阶：时间n，空间1
void delete_x(int a[],int x){
int n = a.size();
int i = 0,k = 0;//k记录数组中值为x的个数
while(i < n){
if(a[i] == x){
k++;
}
else{//当前元素不等于x
a[i-k] = a[i];//
}
i++;
}
a.size() = a.size() - k;
}
//和上题思路基本一样，也可以用快排先排序再删除
bool delete_st(int a[],int s,int t){
if(s > t)
return false;
int(a.size() == 0){
return false;
}
int i = 0,k = 0;//k表示值在s与t之间元素的个数
while(i < a.size()){
if(a[i]>=s && a[i]<=t){
k++;
}
else {
a[i-k] = a[i]
}
i++;
}
a.size() = a.size() - k;
}
void delete_same(int a[]){
for(int i = 0,j = 1; j < a.size(); j++){
if(a[i] != a[j]){
i++;
a[i] = a[j];//不重复的元素保留，即元素固定不动
}
//else即遇到重复的元素，则j向后移一位，i不动，所以最后i的值就是数组中不重复元素的个数 - 1
}//for end
a.size() = i+1;//i是从0开始的
}
先部分逆置，再整体逆置
//例：数组(a1,a2,a3,b1,b2,b3) -> (b1,b2,b3,a1,a2,a3)
//设c[m+n]中存放数组a[m]和数组b[n]
void swap(int c[]){
reverse(c,0,m);
reverse(c,m,m+n);
reverse(c,0,m+n);
}
void reverse(int a[],int l,int r){//逆置函数:将数组a从a[l]~a[r]之间的元素逆置
int t = 0;
for(int i = l; i < (r-l)/2; i++){
t = a[i];
a[i] = a[r-i-1];
a[r-i-1] = t;
}
}