排序算法

排序问题整理

• 排序的时候能用快速排序尽量用快排

• 整理排序算法的复杂度以及优缺点

1.快速排序（交换排序）

• 需要一个递归栈来保存信息
• 最好情况$O(nlog_2{n})$；平均情况$O(nlog_2{n})$；最坏情况$O(n^{2})$
• 空间复杂度：$O(log_2{n})$
• 是否稳定：否（快的排序都不稳定）
• 每排一次，枢轴被放入最终位置

int Partition(int A[],int low,int high){     //一趟划分
    int pivot = A[low];                      //将当前表中第一个元素设为枢轴，对表进行划分
    int t = low;
    while(low<high){
        low++;
        while(A[low]<=pivot){                //从前往后找到一个比枢轴大的数
            low++;
        }
        while(A[high]>pivot){                //从后往前找到一个比枢轴小的数
            high--;
        }
        if(low<high){
            int w = A[low];                  //用临时变量w储存值，交换两个数
        	A[low] = A[high];                //用临时变量w储存值，交换两个数
        	A[high] = w;                     //用临时变量w储存值，交换两个数
        }
    }
    A[t] = A[high];                          //找到枢轴的正确位置，交换这两个元素
    A[high] = pivot;
    return high;                             //返回枢轴正确的位置
}
void QuickSort(int &A[],int low,int high){   //开始快排
    if(low<high){
        int mid = Partition(A,low,high);
        QuickSort(A,low,mid-1);              //枢轴左半边继续快排
        QuickSort(A,mid+1,high);
    }
}

2.冒泡排序（交换排序）

• 注意返回值类型以及函数以及flag的使用

• 从后往前比较两两相邻元素的值，若为逆序，则交换他们，直到序列比较完成。这成为第一趟冒泡。
• 结果是将最小的元素交换到待排序列的第一个位置
• 下一趟冒泡时，前一趟确定的最小元素不再参与比较，这样最多$n-1$趟冒泡就能排好序
• 最好情况：$O({n})$；平均情况：$O(n^{2})$；最坏情况：$O(n^{2})$
• 是否稳定：是

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;                    //没有发生交换，这说明有序
        }
    }
}
//网上找的swap函数，仅供参考
void swap(int *a,int *b)
{
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

3.直接插入排序

• 从前往后依次插入到前面的序列
• 最好情况是表中元素已经有序，此时每插入一个元素，都只需比较一次而不用移动元素
• 最好情况：$O({n})$；平均情况：$O(n^{2})$；最坏情况：$O(n^{2})$
• 是否稳定：是

void InserSort(int A[],int n){
    int i,j;
    for(i=2;i<n;i++){                  //依次将A[2]~A[n]插入到前面已排序序列
        if(A[i]<A[i-1]){               //若A[i]关键词小于其前驱，将A[i]插入有序表
            A[0] = A[i];//复制为哨兵，A[0]不存放元素
            for(j=i-1;A[0]<A[j];j--){//从后往前查找待插入位置
                A[j+1] = A[j];//向后挪位
            }
            A[j+1] = A[0];//复制到插入位置
        }
    }
}

4.折半插入排序

• 只适用于顺序表
• 最好情况：$O({n})$；平均情况：$O(n^{2})$；最坏情况：$O(n^{2})$
• 是否稳定：是

void InsertSort(int A[],int n){
    int i,j,low,high,mid;
    for(i=2;i<=n;i++){           //依次将A[2]~A[n]插入到前面的已排序序列
        A[0] = A[i];             //将A[i]暂存到A[0]
        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];        //插入操作
    }
}

5.希尔排序

• 只适用于顺序表
• 是否稳定：否

void ShellSort(int A[],int n){
    int i,j,dk;
    for(dk=n/2;dk>=1;dk=dk/2){       //步长变化 
        for(i=dk+1;i<=n;++i){
            if(A[i]<A[i-dk]){        //需将A[i]插入有序增量字表
                A[0] = A[i];         //暂存A[0]
                for(j=i-dk;j>0 && A[0]<A[j];j=j-dk){
                    A[j+dk] = A[j];  //记录后移，查找插入位置
                }
                A[j+dk] = A[0];      //插入
            }//if
        }
    }
}

6.堆排序

• 每排列一次，都有一个正确结点
• 最好情况$O(nlog_2{n})$；平均情况$O(nlog_2{n})$；最坏情况$O(nlog_2{n})$
• 是否稳定：否

void BuildMaxHeap(int A[],int len){
    for(int i=len/2;i>0;i--){//反复调整堆
        HeadAdjust(A,i,len);
    }
}
void HeadAdjust(int A[],int k,int len){
    A[0] = A[k];//
    for(int i=2*k;i<=len;i*=2){
        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趟的交换和建堆
        int temp = A[i];//堆顶和堆底元素交换
        A[1] = A[i];
        A[i] = temp;
        HeadAdjust(A,1,i-1);//继续调整剩余元素
    }
}