首页 计算机科学 数据结构

排序：就是重新排列列表中的元素，使表中元素满足按关键字有序的过程

排序算法的评价指标：

算法的稳定性。若待排序的表中有两个元素 Ri 和 Rj，其对应的关键字相同 keyi=keyj，且在排序前 Ri 在 Rj 前面，若使用某一排序算法后，Ri 仍在 Rj 前面，则称这个排序算法是稳定的，否则称排序算法是不稳定的

稳定的：关键字相同的元素在排序前后相对位置不变

排序算法：

  • 内部排序：数据都在内存 (关注如何使算法时、空间复杂度更低)
  • 外部排序：数据太多，无法全部放入内存 (还要关注如何使读 / 写磁盘次数更少)

# 插入排序

算法思想：每次将一个待排序的记录按其关键字大小插入到前面已排好的子序列中，直到全部记录插入完成

算法实现：

//直接插入排序
void InsertSort(int A[],int n){
    int i,j,temp;
    for(i=1;i<n;i++){               //将各元素插入已排好序的序列中
        if(A[i]<A[i-1]){             //若A[i]关键字小于前驱
            temp=A[i];                 //用temp暂存A[i]
            for(int j=i-1;j>=0 && A[j]>temp;--j)   //检查所有前面已排好序的元素
                A[j+1]=A[j];       //所有大于temp的元素都向后挪位
            A[j+1]=temp;           //复制到插入位置
        }
    }
}
//带哨兵的算法实现
void InsertSort(int A[],int n){
    int i,j;
    for(i=2;i<n;i++){               //将各元素插入已排好序的序列中
        if(A[i]<A[i-1]){             //若A[i]关键字小于前驱
            A[0]=A[i];                 //用temp暂存A[i]
            for(int j=i-1;A[j]>temp;--j)   //检查所有前面已排好序的元素
                A[j+1]=A[j];       //所有大于temp的元素都向后挪位
            A[j+1]=A[0];           //复制到插入位置
        }
    }
}
//带哨兵的优点：不用每轮都判断j>=0

空间复杂度：O (1)，时间复杂度O(n2)O(n^2)，最好时间复杂度 O (n)，最坏时间复杂度O(n2)O(n^2)

算法稳定性：稳定

优化：折半插入排序

思路：先用折半查找找到应该插入的位置，再移动元素

当 low>high 时折半查找停止，应将 [low,i-1] 内的元素全部右移，并将 A [0] 复制到 low 所指位置

当 A [mid]==A [0] 时，为了保证算法的稳定性，应继续在 mid 所指位置右边寻找插入位置

//折半插入排序
void InsertSort(int A[],int n){
    int i,j,low,high,mid;
    for(i=2;i<n;i++){               //将各元素插入已排好序的序列中
        A[0]=A[i];
        low=1,high=i-1;
        while(low<=high){
            mid=(low+high)/2;
            if(A[mid]>A[0])
                high=mid-1;
            else
                low=mid+1;
        }
        for(j=i-1;j>=high+1;--j)
            A[j+1]=A[j];
        A[high+1]=A[0];
    }
}

# 希尔排序

希尔排序：

  • 先追求表中元素部分有序，再逐渐逼近全局有序

  • 先将待排序表分割成若干形如 L [i,i+d,i+2d,...,i+kd] 的特殊子表，对各个分别进行直接插入排序。缩小增量 d，重复上述过程，直到 d=1 为止

  • 每次让增量 d 缩小一半

算法实现：

void ShellSort(int A[],int n){
    int d.i,j;
    for(d=n/2;d>=1;d=d/2){
        for(i=d+1;i<=n;++i)
            if(A[i]<A[i-d]){
                A[0]=A[i];
                for(j=i-d;j>0 && A[0]<A[j];j-=d)
                    A[j+d]=A[j];
                A[j+d]=A[0];
            }
    }
}

空间复杂度：O (1)

时间复杂度：和增量序列 d1,d2,...,dn 的选择有关，目前无法用数学手段证明确切的时间复杂度，最坏时间复杂度为O(n2)O(n^2)，当 n 在某个范围内时，可达O(n1.3)O(n^{1.3})

稳定性：不稳定

适用性：仅适用于顺序表，不适用于链表

交换排序

分为冒泡排序和快速排序

基于 "交换" 的排序：根据序列中两个元素关键字的比较结果对换这两个记录在序列中的位置

# 冒泡排序

从后往前 (或从前往后) 两两比较相邻元素的值，若为逆序 (即 A [i-1]>A [i])，则交换它们，直到序列比较完。称这样过程为 "一趟" 冒泡排序

若某一趟排序没有发生交换，说明此时已经整体有序。

算法实现：

//交换，每次交换需要移动元素3次
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 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)
            return;
    }
}

空间复杂度：O (1)

时间复杂度：O(n2)O(n^2)

最好时间复杂度：O (n)

最坏时间复杂度：O(n2)O(n^2)

稳定性：稳定

适用性：顺序表、链表都可以

# 快速排序

算法思想：在待排序表 L [1,...,n] 中任取一个元素 pivot 作为枢轴 (或基准，通常取首元素)，通过一趟排序将待排序表划分为独立的两部分 L [1,...,k-1] 和 L [k+1,...,n]，使得 L [1,...,k-1] 的所有元素小于 pivot，L [k+1,..,n] 的所有元素大于等于 pivot，则 pivot 放在了其最终位置 L (k) 上，这个过程称为一次 "划分"。然后分别递归地对两个子表重复上述过程，直至每部分内只有一个元素或空为止，即所有元素放在了其最终位置上。

//用第一个元素将待排序序列划分成左右两个部分
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);
    }
}

空间复杂度：O (递归层数)

最好时间复杂度 = O (nlogn)

最坏时间复杂度 = O (n2n^2)

最好空间复杂度 = O (log2n)

最坏空间复杂度 = O (n)

若每一次选中的 "枢轴" 将待排序序列划分为均匀的两个部分，则递归深度最小，算法效率最高

快速排序算法优化思路：尽量选择可以把数据中分的枢轴元素

  • 选头、中、尾三个元素，取中间值作为枢轴元素
  • 随机选一个元素作为枢轴元素

稳定性：不稳定