计算机考研之数据结构-排序

数据结构-排序

重要概念

定义

对元素进行重拍使得其关键字满足递增或者递减的过程。

输入：n个记录(R_1,cdots,R_n)，对应关键字为(k_1,cdots,k_n)
输出：一个输入序列的重拍(R_1^{'} ,cdots,R_n^{'})使得(k_1^{'}leqcdotsleq k_n^{'})，比较符号可以改变。

稳定性

对于关键字相同的两个元素，如果排序前后顺序不变即满足稳定性。

内部性与外部性

内部排序：排序过程中所有元素都在内存中。
外部排序：排序过程中元素要在内外存中交换。

说明

以下例子都以顺序表为例。

插入类

插排将序列分为两个部分，有序序列和无序的序列。然后从无序序列中拿出一个元素插入到有序序列中即可。

直接插入排序

void Sort(int A[], int len){
    for(int i=1; i<len; i++){
        if(A[i]<A[i-1]){ //判断是否需要向前插入
            int temp = A[i];
            for(int j=i-1; temp<A[j]; j--) //找到插入位置
                A[j+1]=A[j]; // 为插入的元素挪位置
            A[j+1]=temp;
        }
    }
}

性能分析：
空间：O(1)。
时间：最好O(n)，最坏O(n^{2)，平均O(n}2)。
稳定性：稳定。

折半插入排序

因为插入的序列是有序的，所以可以使用折半查找节约时间。

void sort(int A[], int len){
    for(int i=1; i<len; i++){
        int temp = A[i];
        int low=0;int high=i-1;
        while(low<=high){
            int mid=(low+high)/2;
            if(A[mid]>temp) high=mid-1;
            else low=mid+1;
        }
        for(int j=i-1; j>high; j--) //找到插入位置
            A[j+1]=A[j]; // 为插入的元素挪位置
        A[high]=temp;  
    }
}

性能分析：
空间：O(1)。
时间：平均O(n^2)。
稳定性：稳定。

希尔排序

希尔排序将序列按照一定的长度切分为多个子序列，对子序列进行插入排序，再对整个序列进行插入排序。

void Sort(int A[], int len){
    for(int dk/len; dk>=1;dk=dk/2){
        for(int i=dk+1;i<=n;i++){
            if(A[i]<A[i-dk]){
            }
        }
    }
}

性能分析：
空间：O(1)。
时间：一般约为(n^{1.3)，最坏O(n}2)。
稳定性：不稳定。

交换类

冒泡排序

冒泡的排序关键在于每一轮都会把第i大的那个关键字排到有序的位置上。

void sort(int A[], int len){
    for(int i=0;i<len-1;i++)
        for(int j=0;j<len-1-i;j++)
            if(A[j]>A[j+1]){
                int temp = A[j];
                A[j]=A[j+1];
                A[j+1]=temp;
            }
}

加入flag来优化最好情况：

void sort(int A[], int len){
    for(int i=0;i<len-1;i++){
        int flag = 0;
        for(int j=0;j<len-1-i;j++){
            if(A[j]>A[j+1]){
                int temp = A[j];
                A[j]=A[j+1];
                A[j+1]=temp;
                flag=1;
            }
        }
        if(flag==0)
            return;
    }
}

性能分析：
空间：O(1)。
时间：最坏 O(n^2)，最好 O(n)，平均 O(n^2)。
稳定性：不稳定。

快速排序

int partition(int A[], int lo, int hi){
    int p = A[lo];
    while(lo<hi){
        while(lo<hi && A[hi]>=p) hi--;
        A[lo]=A[hi];
        while(lo<hi && A[lo]<=p) lo++;
        A[hi]=A[lo];
    }
    A[lo]=p;
    return lo;
}

void sort(int A[], int lo, int hi){
    int lo=0; int hi=len-1;
    if(lo<hi){
        int pos=partition(A,lo,hi);
        sort(A,lo,pos-1);
        sort(A,pos+1,hi);
    }
}

性能分析：
空间：即递归栈的深度，最好 O(log(n+1))，最坏 O(n)，平均 O()
时间：最坏 O(n^2)，平均 O(logn)。
稳定性：不稳定。

选择类

选择排序

void sort(int A[], int len){
    for(int i=0;i<len-1;i++){
        int min = i;
        for(int j=i+1;j<n;j++)
            if(A[j]<A[min])
                min = j;
        if(min!=i)
            swap(A[i],A[min]);
    }
}

性能分析：
空间：O(1)
时间：O(n^2)。
稳定性：不稳定。

堆排序

void adjust(int A[], int i, int len){
    int child;
    for(; 2*i+1<len; i=child){
        int child = 2*i+1; //leftchild
        if(child<len-1 && A[child+1]>A[child])
            child++; // rightchild
        if(A[i]<A[child])
            swap(A[i],A[child])
        else
            break;   
    }
}

sort(int A[], int len){
    for(int i=len/2-1; i>=0; i--)
        adjust(A,i,len);
    
    for(int i=length-1;i>0;i--){
        swap(A[0],A[i]);
        adjust(A,0,i);
    }
}

性能分析：
空间：O(1)
时间：O(nlogn)。
稳定性：不稳定。

归并类

归并排序

int *B=(int *)malloc(n)*sizeof(int);

void merge(int A[], int low, int mid, int high){
    for(int k=low;k<=high;k++)
        B[k]=A[k];
    for(int i=low,int j=mid+1,int k=i;i<=mid&&j<=high;k++){
        if(B[i]<=B[j])
            A[k]=B[i++];
        else 
            A[k]=B[j++];
    }
    while(i<=mid) A[k++]=B[i++];
    while(j<=high) A[k++]=B[j++];
}

void sort(int A[], int low, int high){
    if(low<high){
        int mid=(low+high)/2;
        sort(A,low,mid);
        sort(A,mid+1;high);
        merge(A,low,mid,high);
    }
}

性能分析：
空间：O(n)
时间：最坏最好都是O(nlogn)。
稳定性：稳定。

基数类

基数排序

性能分析：
空间：O(r)。
时间：最坏最好都是O(d(n+r))。
稳定性：稳定。