查找与排序

2019-08-31

查找算法

顺序查找

顺序查找又称线性查找。它的过程为：从查找表的最后一个元素开始逐个与给定关键字比较，若某个记录的关键字和给定值比较相等，则查找成功，否则，若直至第一个记录，其关键字和给定值比较都不等，则表明表中没有所查记录查找不成功，它的缺点是效率低下。

二分查找

简介
基本思想是将n个元素分成大致相等的两部分，取a[n/2]与x做比较，如果x=a[n/2],则找到x，算法中止；如果x < a[n/2]，则只要在数组a的左半部分继续搜索x，如果x > a[n/2]，则只要在数组a的右半部搜索x。
二分查找的时间复杂度为O(logn)

实现

int BinSearch(int low,int high,int target)
{
    while(low<=high){
        int mid=(low+high)/2;
        if(target==arr[mid])return mid;
        else if(arr[mid]>target){
            high=mid-1;
        }
        else low=mid+1;
    }
    return -1;
}

排序算法

冒泡排序

简介
基本思想是：设排序序列的记录个数为n，进行n-1次遍历，每次遍历从开始位置依次往后比较前后相邻元素，这样较大的元素往后移，n-1次遍历结束后，序列有序。

实现

//冒泡排序：从小到大
void BubbleSort(int arr[],int len)
{
    int flag=true;
    for(int i=0;i<len-1;i++){//len-1次冒泡
        if(!flag)break;
        flag=false;
        for(int j=0;j<len-i-1;j++){//去除最后一个已到位的
            if(arr[j]>arr[j+1]){
                swap(arr[j+1],arr[j]);
                flag=true;
            }
        }
    }
        return;
}

分析
最佳情况下冒泡排序只需一次遍历就能确定数组已经排好序，不需要进行下一次遍历，所以最佳情况下，时间复杂度为**O(n)。
最坏情况下冒泡排序需要n-1次遍历，第一次遍历需要比较n-1次，第二次遍历需要n-2次，…，最后一次需要比较1次，最差情况下时间复杂度为O(n^2)**。
简单选择排序
简介
设排序序列的记录个数为n，进行n-1次选择，每次在n-i+1(i = 1,2,…,n-1)个记录中选择关键字最小的记录作为有效序列中的第i个记录。

实现

//选择排序，从小到大
void SelectSort(int arr[],int len)
{
    for(int i=0;i<len-1;i++){
        int mini=i;
        for(int j=i+1;j<len;j++){
            if(arr[mini]>arr[j]){
                mini=j;
            }
        }
        swap(arr[i],arr[mini]);
    }
}

分析
进行比较操作的时间复杂度为 O(n^2) ，进行移动操作的时间复杂度为 O(n) 。总的时间复杂度为O(n^2)
直接插入排序
简介
思想：是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。

实现

//直接插入排序，从小到大
void DInsertSort(int arr[],int len)
{
    int now=0;
    for(int i=1;i<len;i++){
        now=arr[i];
        int j=i-1;
        for(;j>=0;j--){
            if(arr[j]<now){
                break;
            }
            arr[j+1]=arr[j];
        }
        arr[j+1]=now;
    }
}

分析
最好情况下，当待排序序列中记录已经有序时，则需要n-1次比较，不需要移动，时间复杂度为O(n) 。最差情况下，当待排序序列中所有记录正好逆序时，则比较次数和移动次数都达到最大值，时间复杂度为O(n^2) 。平均情况下，时间复杂度为**O(n^2)**。
归并排序
简介
归并排序是分治法的一个典型应用，它的主要思想是：将待排序序列分为两部分，对每部分递归地应用归并排序，在两部分都排好序后进行合并。

实现

//归并排序：从小到大
//#define Max 1000
int Merge(int A[],int p,int q,int r)
{
    int n1=q-p+1;
    int n2=r-q;
    int i=0,j=0;
    //用2个数组分别存放目标A[]数组
    //p~q与q+1~r的数
    int L[n1+1],R[n1+1];
    for(i=0;i<n1;i++){
        L[i]=A[p+i];
    }
    L[i]=Max;
    for(j=0;j<n2;j++){
        R[j]=A[q+j+1];
    }
    R[j]=Max;
    i=0;j=0;
    //合并L[]与R[]数组
    for(int k=p;k<=r;k++){
        if(L[i]<=R[j]){
            A[k]=L[i];
            i++;
        }
        else{
            A[k]=R[j];
            j++;
        }
    }
    return 1;
}

int MergeSort(int A[],int p,int r)
{
    int q=0;
    if(p<r){
        q=(p+r)/2;
        MergeSort(A,p,q);
        MergeSort(A,q+1,r);
        Merge(A,p,q,r);
    }
    return 1;
}
//MergeSort(array,0,len-1);

分析
时间复杂度为O(nlogn)
快速排序
简介
主要思想是：在待排序的序列中选择一个称为主元的元素，将数组分为两部分，使得第一部分中的所有元素都小于或等于主元，而第二部分中的所有元素都大于主元，然后对两部分递归地应用快速排序算法。

实现

//快速排序：从小到大
//实现对子数组A[p,r]的原址重拍
int PARTITION(int A[],int p,int r)
{
    int x=A[r];
    //i作为比x小的位置标记
    int i=p-1;
    int j;
    for(j=p;j<r;j++)
    {
        if(A[j]<=x){
        //使i+1到j之前严格大于A[r]
            i=i+1;
            swap(&A[i],&A[j]);
        }
    }
    i=i+1;
    swap(&A[i],&A[r]);
    return i;
}

void QUICKSORT(int A[],int p,int r)
{
    if(p<r){
        int x=PARTITION(A,p,r);
        QUICKSORT(A,p,x-1);
        QUICKSORT(A,x+1,r);
    }
}
//QUICKSORT(array,0,len-1);

分析
最差情况下算法需要(n-1)+(n-2)+…+1= O(n^2) 时间;
最佳情况下，每次主元将数组划分为规模大致相等的两部分，时间复杂度为**O(nlogn)**。
堆排序
简介
堆性质(小根堆)：(1) ki <= k(2i）且 ki <= k(2i+1) (1 ≤ i≤ n/2），即完全二叉树中所有的非终端节点的值均不大于（或不小于）其左右孩子节点的值。
主要思想是：给定一个待排序序列，首先经过一次调整，将序列构建成一个大根堆，此时第一个元素是最大的元素，将其和序列的最后一个元素交换，然后对前n-1个元素调整为大根堆，再将其第一个元素和末尾元素交换，这样最后即可得到有序序列。

实现

//堆排序：小到大
void MAX_HEAPIF(int A[],int i)
{
    int x=2*(i+1);
    int l=x-1;
    int r=x;
    int largest=i;
    if(l<Heap_Size&&A[i]<A[l]){
        largest=l;
    }
    if(r<Heap_Size&&A[largest]<A[r]){
        largest=r;
    }
    if(largest!=i){//根节点比他的孩子结点小，需要交换
        int f=A[i];
        A[i]=A[largest];
        A[largest]=f;

    //为保持以孩子结点为根节点的堆为最大堆
    MAX_HEAPIF(A,largest);
    }
}

//将最原始的数组变为最大堆
//需要从最底下的非叶子结点往上建
void BUILD_MAX_HEAP(int A[],int n)
{
    int node=n/2;
    for(int i=node-1;i>=0;i--){
        MAX_HEAPIF(A,i);
    }
}

//堆排序算法
void HEAP_SORT(int A[],int n)
{
    BUILD_MAX_HEAP(A,n);
    //建一个最大堆之后，每次将根节点与Heap_size最后一个结点置换，再继续建最大堆
    //直到Heap_size为1
    while(Heap_Size>1){
        int f=A[Heap_Size-1];
        A[Heap_Size-1]=A[0];
        A[0]=f;

        Heap_Size--;

        MAX_HEAPIF(A,0);
    }
}
//Heap_Size=len;
//HEAP_SORT(array,len);

分析
由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。堆排序时间复杂度也为**O(nlogn)**，空间复杂度为O(1)。它是不稳定的排序方法。与快排和归并排序相比，堆排序在最差情况下的时间复杂度优于快排，空间效率高于归并排序。
二叉树的性质

 常见数据结构与算法整理

桶排序

非比较排序；[0,MAX]格子的桶；

基数排序

桶排序的延伸，预处理成数位相同，从个位开始到最高位，依次桶排序

查找算法

顺序查找

二分查找

排序算法

冒泡排序

简单选择排序

直接插入排序

归并排序

快速排序

堆排序

桶排序

基数排序