一、基本操作

1、数组的使用

?一般情况下如果不是题目要求，则不需要使用结构体包起来，直接使用数组就行
传参时只需传数组名、数组中元素个数

void f(int A[],int n){

}

2、任意位置插入一个元素

void insert(int A[],int &n,int index,int data){
    //在数组A的index处（下标为index）插入值为data的元素
    //n为数组元素个数，注意这里使用引用，插入元素后数组元素个数增加

    for(int i=n;i>index;i--){   //index及其后元素往后移
        A[i]=A[i-1];
    }
    A[index]=data;    //插入
    n++;              //元素个数加一
}

3、任意位置删除一个元素

viod del(int a[],int &n,int index){
    //删除数组a中的index处的元素，index为数组下标
    //n为数组元素个数

    for(int i=index;i<n-1;i++){
        a[i]=a[i-1];
    }
    n--;
}

4、查找元素（顺序查找）

int find(int a[],int n,int data){
    //在数组a中查找值为data的元素的位置，若查找失败，返回-1

    for(int i=0;i<n;i++){    
        if(a[i]==data)
            return i;
    return -1;
}

5、数组中元素逆置

viod reverse(int a[],int left,int right){
    //将数组a中[left,right]的部分元素逆置
    
    int i=left,j=right;   //双指针法
    while(i!=j){
        swap(a[i],a[j]);
        i++,j--;
    }
}

6、两个有序数组合并

int* merge(int a[],int m,int b[],int n){
    //合并有序数组a，b   
    
    int i=0,j=0,k=0;
    int *c=new int[n+m]; 
    
    while(i<m && j<n){    //两个数组都未遍历完毕
        if(a[i]<=b[j])
            c[k++]=a[i++];
        else
            c[k++]=b[j++];
    }
    while(i<m)
        c[k++]=a[i++];
    while(j<n)
        c[k++]=b[j++];

    return c;
}

二、模板整理及技巧总结

1、快速排序

????????快速排序如第一趟确定的值是首尾元素，则第二趟只能确定一个数；如第一趟确定的是中间元素，则第二趟会确定两个元素，在递归实现中表示为，左右分别要递归一次，得出两个值。

viod quicksort(int a[],int low,int high){
    //快速排序，时间复杂度为O(nlogn),空间复杂度为O(logn)
    
    if(low>=high)
        return;   //递归终止
    
    int i=low,j=high;
    int temp=a[low];    //枢轴元素，不考虑优化
    while(i<j){
        while(i<j && a[j]>=temp)
            j--;             //j从后往前移动，直到找到小于枢轴的元素
        while(i<j && a[i]<=temp)
            i++;             //i从前往后移动，直到找到大于枢轴的元素
        
        swap(a[i],a[j]);
    }
    swap(a[low],a[i]);       //将枢轴元素放到中间
    quicksort(a,low,i-1);    //递归对左半段进行排序
    quicksort(a,i+1,high);   //递归对右半段进行排序

void QSort(int A[], L, R) {    //快速排序
    if (L >= R) return;    //当前数组长度 <= 1，返回
    随机选择数组中一元素和A[L]互换    //快排优化，使得基准元素的选取随机
    int key = A[L], i = L, j = R;
    while (i < j) {
        while (i < j && key < A[j]) j--;
        while (i < j && A[i] <= key) i++;
        if (i < j) swap (A[i], A[j]);    //交换A[i]和A[j]
    }
    swap (A[i], A[L]);
    Qsort (A, L, i - 1);    //递归处理左区间
    Qsort (A, i + 1, R);    //递归处理右区间
}

2、折半查找【仅适用于有序的顺序表】

int Binary_Search (int A[], L, R, key) {

    //二分查找，要求数组A中元素升序 
	//若数组A中存在值为key的元素，则返回该元素的下标
	//若数组A中不存在值为key的元素，则返回第一个大于该元素的下标
	//若数组A中所有元素均小于key，则返回数组元素个数

    int mid;
    while (L < R) {           //L >= R时，范围错误
        if (A[mid] == key) 
            return mid;       //查找成功，返回数组下标
        mid = (L + R) / 2;    //选择中间数，向下取整
        if (key <= A[mid]) R = mid;    //更新范围
        else L = mid + 1;
    }
    else return -1;    //查找失败，返回-1
}

3、归并排序

int *B=new int[n];  //辅助数组B

//数组A[low....mid]和A[mid+1....high]各自有序，将两个部分合并
void merge(int A[],int low,int mid,int high){
    int i,j,k;
    for(k=low;k<=high;k++)
        B[k]=A[k];       //将A中所有元素复制到B中
    for(i=low,j=mid+1,k=i;i<=mid && j<=high;k++){
        if(B[i]<=B[j])
            A[k]=B[i++];   //较小者复制到A中
        else
            A[k]=B[j++];
    }
    while(i<=mid)   A[k++]=B[i++];
    while(j<=high)  A[k++]=B[j++];
}

void mergesort(int A[],int low,int high){
    if(low<high){
        int mid=(low+high)/2;  //从中间划分
        mergesort(A,low,mid);
        mergesort(A,mid+1,high);
        merge(A,low,mid,high);
    }
}

4、总结数组做题流程——暴力——优化方向

5、掌握时间、空间复杂度的分析

三、习题练习

????????从顺序表中删除具有最小值的元素（假设唯一）并由函数返回被删元素的值。空出的位置由最后一个元素填补，若顺序表为空，则显示出错信息并退出运行。

bool Del_Min(int A[],int n,&value){
    if(!n) return false;     //数组长度为0
    int data=INT_MAX,idx;    //INT_MAX为int类型的最大值
    for(int i=0;i<n;i++){
        data=min(data,a[i]);
        idx=i;
    }
    a[idx]=a[n-1];           //用数组中最后一个元素替换
    value=data;
    return true;
}

????????本题也可用函数返回值返回，两者的区别是，函数返回值只能返回一个值，而参数返回（引用传参）可以返回多个值。