【数据结构】冒泡排序、快速排序

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

1. 冒泡排序

1. 冒泡排序的定义

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

如果从后往前两两比较：

第1趟排序使关键字最小的一个元素“冒”到最前面。

第2趟结束后，最小的两个元素会“冒”到最前边。

...

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

2. 算法实现

// 交换
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-1;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(flag==false){
            return;  // 本趟遍历后没有发生交换，说明表已经有序
        }
    }
}

说明：i所指位置之前的元素都已“有序”。只有A[j-1]>A[j]时才交换，因此算法是稳定的。

3. 算法性能分析

空间复杂度：O(1)。

最好时间复杂度（有序）：O(n)。

最坏时间复杂度（逆序）：O(n^2)。

平均时间复杂度：O(n^2)。

4. 是否适用于链表

适用：可从前往后“冒泡”，每一趟将更大的元素“冒”到链尾。

2. 快速排序

1. 算法思想

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

如此，49将序列分为左右两部分，而49的最终位置已经确定。然后左右重复执行上述过程，即可完成排序。

2. 算法实现

// 用第一个元素将待排序序列划分为左右两个部分
int Partition(int A[],int low,int high){
    int pivot=A[low];  // 第一个元素作为枢轴
    while(low<high){  // 用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);  // 划分右子表
    }
}

3. 算法效率分析

稳定性：不稳定。

3. 小结

快速排序算法是所有内部排序算法中平均性能最优的排序算法。