[数据结构与算法]数据结构_排序_基本操作的c++实现

/*-----------------------Sort--------------排序------------*/

//直接插入排序(不带哨兵)
void InsertSort(int A[],int n){
    int i,j,temp;
    for(i=1;i<n;i++)
    if(A[i]<A[i-1]){
        temp=A[i];
        for(j=i-1;j>=0&&A[j]>temp;--j)
            A[j+1]=A[j];
        A[j+1]=temp;
    }
}


//冒泡排序
//交换
void swap(int &a, int &b){
    int temp=a;
    a=b;
    b=temp;
}
//冒泡排序
void BubbleSort(int A[], int n){

    for(int i=0;i<n-1;i++){
        bool flag=false;                    //表示本趟冒泡是否发生交换的标志
        for(int j=n-1;j>i;j--)           //一趟冒泡过程
            if(A[j-1]>A[j]){            //若为逆序
                swap(A[j-1],A[j]);      //交换
                flag=true;
            }
        if(flag==false)
            return;
    }                   //本趟遍历后没有发生交换，说明表已经有序，直接退出！
}

//快速排序
//用一个元素将待排序序列划分成左右两个部分
int Partition(int A[],int low,int high){
    int pivot=A[low];       //第一个元素作为枢轴
    while(low<high){        //用low、high搜索枢轴的最终位置
        while(low<high&&A[high]>=pivot) --high;
        A[low]=A[high];        //比枢轴小的元素移动到左端
        while(low<high&&A[low]<=pivot) ++low;
        A[high]=A[low];        //比枢轴大的元素移动到右端
    }
    A[low]=pivot;         //枢轴元素存放到最终位置
    return low;          //返回存放枢轴的最终位置
}
//快速排序
void QuickSort(int A[],int low, int high){
    if(low<high){             //递归跳出的条件
        int pivotpos=Partition(A,low,high);
        QuickSort(A,low,pivotpos-1);
        QuickSort(A,pivotpos+1,high);
    }
}


//堆排序
//建立大根堆
void HeadAdjust(int A[],int k,int len);
void BuildMaxHeap(int A[],int len){
    for(int i=len/2;i>0;i--)                 //从后往前调整所有非终端结点
        HeadAdjust(A,i,len);
}
//将以k为根的子树调整为大根堆
void HeadAdjust(int A[],int k,int len){
    A[0]=A[k];
    for(int i=2*k;i<=len;i*=2){     //沿key较大的子结点向下筛选
        if(i<len&&A[i]<A[i+1])
            i++;
        if(A[0]>=A[i])
            break;
        else{
            A[k]=A[i];
            k=i;
        }
    }
    A[k]=A[0];
}
//堆排序的完整逻辑
void HeapSort(int A[],int len){
    BuildMaxHeap(A,len);           //初始建堆
    for(int i=len;i>1;i--){     //n-1趟的交换和建堆过程
        swap(A[i],A[1]);        //堆顶元素和堆底元素交换
        HeadAdjust(A,1,i-1);    //把剩余的待排序元素整理成堆
    }
}


//归并排序
int *B=(int *)malloc(n*sizeof(int));         //辅助数组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++];
    }//for
    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);  //归并
    }
}