vlambda博客
学习文章列表

    最近重温了数据结构和算法（主要参考：《王道数据结构》），以下是排序算法的笔记。

    排序算法可分为以下几类：

    交换排序算法：冒泡排序、快速排序；

    选择排序算法：简单选择排序、堆排序；

    插入排序算法：直接插入排序、希尔排序；

    归并排序算法。

    主要做了以上7种排序算法的笔记，字数可能较多，所以分为几篇。

    此为第一篇，交换排序算法：冒泡排序、快速排序。

简介

所谓交换指根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置。

基于交换的排序算法主要介绍冒泡排序和快速排序。

一.冒泡排序

冒泡排序（从小到大）基本思想是：从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即A[i-1]>A[i]），则交换它们，直到序列比较完。

第一趟冒泡，结果是将最小的元素交换到待排序列第一个位置（或将最大的元素交换到待排序列的最后一个位置）。关键字最小的元素如气泡般逐渐往上“漂浮”直至“水面”（或关键字最大的元素如石头般下沉至水底）。下一趟冒泡时，前一趟确定的最小元素不再参与比较，每趟冒泡的结果是把序列中的最小元素（或最大元素）放到了序列的最终位置……这样最多做 n-1趟冒泡就能把所有元素排好序 。

    图8.3所示为冒泡排序的过程，第一趟冒泡时：27 < 49 不交换；13 < 27 不交换；76 > 13 交换；97 > 13 交换；65 > 13 交换；38 > 13 交换；49 > 13 交换。

    通过第一趟冒泡后，最小元素己交换到第一个位 ，也是它的最终位置。第二趟冒泡时对剩余子序列采用同样方法进行排序，以此类推，到第六趟结束后没有发生交换 ，说明表已有序，冒泡排序结束。

1.例程

/********************************* 冒泡排序（交换排序） *********************************/#include <stdio.h>#include <stdlib.h>#include <string.h>
void BubbleSort(int *data, int length){    int i, j, temp;    for(i = 0; i < length-1; i++)            //外循环：进行n-1次循环        for(j = length-1; j > i; j--)        //内循环：从最后一个序号到i序号，进行两两比较            if(data[j] < data[j-1])          //若后面比前面小的，则交换            {                temp = data[j];                data[j] = data[j-1];                data[j-1] = temp;            }}
int main() {    int i = 0;    int data[] = {23, 64, 24, 12, 9, 16, 53, 57};    int temp[] = {0}; int length = sizeof(data) / sizeof(int);
 BubbleSort(data, length);
 for (i = 0;i < length;i ++) {        printf("%4d", data[i]);    }}

2.性能分析

2.1空间复杂度：执行这个算法所需要的内存空间

在进行交换时，使用的辅助单元temp所占用的内存空间。

最优的空间复杂度就是开始元素顺序已经排好了，则空间复杂度为：0；最差的空间复杂度就是开始元素逆序排序了，则空间复杂度为：O(n)；

平均的空间复杂度为：O(1)；

2.2时间复杂度：执行算法所需要的计算工作量

每次比较后都必须移动元素3次来交换元素位置，因此

最优的情况是已经排序好了，那么就不用交换元素了，则时间复杂度为：O( n^2 )；

最差的情况是元素是逆序的，那么每一次排序都要交换两个元素，则时间复杂度为：O( n^2 )；

平均的时间复杂度为：O( n^2 )；

2.3稳定性：若在一个待排序的序列中，存在2个相等的数，在排序后这2个数的相对位置保持不变，那么该排序算法是稳定的；否则是不稳定的

由于 i>j且A[i]= [j]时，不会发生交换，因此冒泡排序是种稳定排序方法。

二.快速排序

快速排序的基本思想是基于分治法（分--将问题分解为规模更小的子问题；治--将这些规模更小的子问题逐个击破；合--将已解决的子问题合并，最终得出“母”问题的解；）的：在待排序表 L[1.....n］中任取一个元素pivot 作为枢轴（或基准，通常取首元素），通过一趟排序将待排序表划分为独立的两部分 L[1...k-1 ］和L[k+1...n]。使得 L[1...k ］中的所有元素小于 pivot, L [k+ 1...n］中的所有元素大于等于 pivot ，则 pivot 放在了其最终位置L(k)上。这个过程称为一趟快速排序（或一次划分）。然后分别递归对两表重复上述过程，直至每部分内只有一个元素或空为止，即所有元素放在了其最终位置上。

一趟快速排序的过程是一个交替搜索和交换的过程，下面通过实例来介绍，附设两个指针 i和j，初值分别为low和high，取第一个元素 49 为枢轴赋值到变量pivot。

1.例程

/********************************* 快速排序（交换排序） *********************************/#include <stdio.h>#include <stdlib.h>#include <string.h>
void sort(int *data, int left, int right) {
    if (left >= right) return ;
    int i = left;    int j = right;    int key = data[left];                       //pivot哨兵
    while (i < j) {        while (i < j && key <= data[j]) {       //right向左移，直到找到小于或等于key的值            j --;        }        data[i] = data[j];      //将right找到的小于key的值交换到left（第一次存放的是哨兵的位置）
        while (i < j && key >= data[i]) {       //left向右移，直到找到大于或等于key的值            i ++;        }        data[j] = data[i];                      //将left找到的大于key的值交换到right     }
    data[i] = key;                              //当i=j时，将哨兵的值存放到该位置
    sort(data, left, i - 1);                    //再对left和right两部分进行递归快排    sort(data, i + 1, right);}
int quick_sort(int *data, int length) {    sort(data, 0, length-1);}
int main() {    int i = 0;    int data[] = {23, 64, 24, 12, 9, 16, 53, 57};    int temp[] = {0}; int length = sizeof(data) / sizeof(int);
 quick_sort(data, length);
 for (i = 0;i < length;i ++) {        printf("%4d", data[i]);    }    printf("\n");}

2.性能分析

2.1空间复杂度

快速排序是递归的，需要借助一个递归工作栈来保存每层递归调用的必要信息，其容量应与递归调用的最大深度一致。

最好情况下为：O(log₂ n)；

最坏情况下，要进行n-1次递归调用，所以复杂度为：O(n)；

平均的空间复杂度为O(log₂n)；

2.2时间复杂度

快速排序的运行时间与划分是否对称有关（同时快速排序算法的性能也主要取决于划分操作的好坏）。

    快速排序的最坏情况发生在两个区域，分别包含 n-1 元素和0元素时，这种最大程度的不对称性若发生在每层递归上，即对应于初始排序表基本有序或基本逆序时，得到最坏情况下的时间复杂度为：O(n²)；

    在最理想的状态下，尽可能做到最平衡的划分，得到的两个子问题的大小都不可能大于 n/2 ，在这 种情况下，快速排序的运行速度将大大提升，此时，最优的时间复杂度为O(nlog₂n)；

好在快速排序平均情况下的运行时间与其最佳情况下的运行时间很接近，而不是接近其最坏情况下的运行时间。快速排序是所有内部排序算法中平均性能最优的排序算法。

2.3稳定性

在划分算法中若右端区间有两个关键字相同 ，且均小于基准值的记录，则在交换到左端区间后，它们的相对位置会发生变化。例如，表L={3, 2, 2}，经过一趟排序后L={2, 2, 3}，最终排序序列也是L={2, 2, 3}，显然，2与2的相对次序发生了变化。

因此快速排序是一种不稳定的排序方法。

下一篇，第二篇，选择排序算法：简单选择排序、堆排序。

参考：

《王道数据结构》