核心算法 - 查找和排序 - 《数据结构算法》

冒泡排序

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;i++){
        bool falg=false;
        for(int j=n-1;j>i;j--){
            if(A[j-1]>A[j]){
                swap(A[j-1],A[j]);
                flag=true;
            }
        }
         if(falg==false)
                return;
    }
}

快速排序

int Partition(int A[],int low,int high){
    int pivot=A[low];
    while(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);
    }
}

堆排序（背背背）

//将以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 BuildMaxHeap(int A[],int len){
    for(int i=len/2;i>0;i--)//从后往前调整所有非终端结点
        HeadAdjust(A,i,len);
}
//堆排序
void HeapSort(int A[],int len){
    BuildMaxHeap(A,len);
    for(int i=len;i>1;i--){//n-1趟的交换和建堆过程
        swap(A[i],A[1]);
        HeapAdjust(A,1,i-1);
    }
}

折半查找算法（二分查找）

int Binary_Search(SqList L,ElemType key){
    int low=0,high=L.length-1,mid;
    while(low<=high){
        mid=(low+high)/2;
        if(L.data[mid]==key)
            return mid;
        else if(L.elem[mid]>key)
            high=mid-1;
        else
            low=mid+1;
    }
    return -1;
}
//递归
int Binary_Search(SqList L,ElemType key,int low,int high){
    if(low>high)
        return 0;
    if(low<=high){
        mid=(low+high)/2;
        if(L.data[mid]==key)
            return mid;
        else if(key<L.data[mid])
            return Binary_Search(L,key,low,mid-1);
        else
            return Binary_Searvh(L,key,mid+1,high);
    }
}

试着写一个算法判断二叉树是否为二叉排序树的算法

void JudgeBST(BiTree T,int &flag){
    if(T!=NULL&&flag){
        JudgeBST(T->lchild,flag);
        if(pre==NULL)
            pre=T;
        else if(pre->data<T->data)
            pre=T;
        else flag=0;
        JudgeBST(T->rchild,flag);//中序遍历
    }
}

编写算法，对 n 个关键字取整数值的记录序列进行整理，以使得所有关键字为负值的关键字排列在关键字为非负值的记录之前，要求：
（1）采用顺序存储结构，至多使用一个记录的辅助存储空间
（2）算法的时间复杂度为 O(n)

void process(int a[],int n){
    int low=0,high=n-1;
    while(low<high){
        while(low<high&&a[low]<0)
            ++low;
        while(low<high&&a[high]>0)
            --high;
        if(low<high){
            int temp=a[low];
            a[low]=a[high];
            a[high]=a[low];
            low++;
            high--;
        }
    }
}

设有一组初始记录关键字序列（K1，K2，…，Kn），要求设计一个算法能够在 O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于 Ki，右半部分的每个关键字均大于等于 Ki。

void process(int a[],int n,int w){
    int low=0,high=n-1,x=a[w];
    while(low<high){
        while(low<high&&a[low]<x)
            ++low;
        while(low<high&&a[high]>x)
            --high;
        if(low<high){
            int temp=a[low];
            a[low]=a[high];
            a[high]=a[low];
            low++;
            high--;
        }
    }
}

线性表（a1,a2,a3,…,an）中元素递增有序且按照顺序存储于计算机内。要求设计一个算法完成：（1）用最少的时间在表中查找数值为 x 的元素。
（2）若查找到将其与后继元素位置交换。
（3）若找不到将其插入表中并使表中元素仍然递增有序。

void Search_x(SqList A,ElemType x){
    int low=0,high=A.length-1;
    while(low<high){
        mid=(low+high)/2;
        if(a[mid]==x)
            break;
        else if(a[mid]<x)
            low=mid+1;
        else
            high=mid-1;
    }
    if(a[mid]==x&&mid!=A.length){
        int temp=a[mid];
        a[mid]=a[mid+1];
        a[mid+1]=temp;
    }
    if(low>high){
        for(int i=n-1;i>hgh;i--)
            a[i+1]=a[i];
        a[i+1]=x;
    }
}