首页 » 开发 » 排序算法

排序算法

排序算法的稳定性。两个键值相同的元素R1和R2,在排序前R1在前R2在后,若排序后R1仍在R2前,则称算法是稳定的,否则是不稳定的。换一个描述则是:键值相同的元素排序前后相对位置保持不变:

排序前: (4,5) (9,1) (4,3) (2,7)
稳定排序: (2,7) (4,5) (4,3) (9,1)
不稳定排序:(2,7) (4,3) (4,5) (9,1)

常见排序算法的基本面分析

排序算法最好平均最坏空间复杂度稳定性
冒泡排序O(n)O(n2)O(1)稳定
直接插入排序O(n)O(n2)O(1)稳定
直接选择排序O(n2)O(1)不稳定
快排O(n log n)O(n2)O(log n)不稳定
堆排序O(n log n)O(1)不稳定
归并排序O(n log n)O(n)稳定

编程珠玑2/e 14.4节指出:虽然堆排序保证了最坏情况下的O(n log n)性能,但对常见输入数据,最快的堆排序通常也比简单快排程序慢。大多数程序语言标准库中的默认排序方法也是快排。

堆排序

堆主要用来实现排序和优先队列。

  1. 堆排序的时间复杂度为Ο(n log n),且只需少量额外空间
  2. 优先级队列。通过插入新元素和提取最大/最小元素这两种操作来维护元素集合,每个操作的时间复杂度均为Ο(log n)

下面以最大堆为例描述算法,最小堆原理相似不再赘述。最大堆接近一棵完全二叉树,且它有几个性质:

  1. 最大元素位于根节点。
  2. 任何节点的值都大于或等于其子节点的值(不限制左右子节点的相对顺序)。
  3. 接近一棵完全二叉树,最多在两层上具有叶节点,其中最底层的叶节点靠左分布。树中不存在空闲位置,如果有n个节点,则任一节点到根节点的距离都不超过(log n)。

C++实现

获取i节点的父节点、左右子节点:

int parent(int i)   { return (int)floor((i-1)/2); }
int left(int i)     { return (2*i + 1); }
int right(int i)    { return (2*i + 2); }

维持一个子树的最大堆属性,子树的根为i:

void max_heapify(int* arr, int len, int i)
{
    int lf = left(i);
    int rt = right(i);
    int largest = i;

    if(lf < len and arr[lf] > arr[i]) {
        largest = lf;
    } 
    if(rt < len and arr[rt] > arr[largest]) {
        largest = rt;
    }

    if(i != largest) {
        std::swap(arr[i], arr[largest]);
        max_heapify(arr, len, largest);
    }
}

构建最大堆:

void build_max_heap(int* arr, int len)
{
    int i = (int)floor((len-1)/2);
    for(; i > -1; --i) {
        max_heapify(arr, len, i);
    }
}

堆排序:

void heap_sort(int* arr, int len)
{
    build_max_heap(arr, len); 

    for(int i = len - 1; i > 0; --i) {
        std::swap(arr[0], arr[i]);  // move max value to tail
        --len;
        max_heapify(arr, len, 0);   // keep max heap
    }
}

快排

快排的思路是在数组中选定一个数x,在一轮排序后,使数组左侧的数都小于x,且数组右侧的数都大于x。此时,递归扫描数组左侧和右侧。

void qsort1(int* arr, int bg, int ed)
{
    if(bg >= ed) return ;

    int m = bg;
    for(int i = bg + 1; i < ed; ++i) {
        if(arr[i] < arr[bg]) {
            std::swap(arr[++m], arr[i]);
        }
    }

    std::swap(arr[bg], arr[m]);

    qsort1(arr, bg, m);
    qsort1(arr, m+1, ed);
}

冒泡排序

冒泡排序的思路:每次比较相邻的两个元素,若a[i] > a[i+1]则交换两个元素,一轮排序后,最大元素出现在数组末端。重复这个过程,n个元素的数组遍历n-1次后整个数组成为有序数组:

void bubblesort(int* arr, int bg, int ed)
{
    int counter = ed - bg - 1;
    while(counter--) {
        for(int j = bg; j < ed - 1; ++j) {
            if(arr[j] > arr[j+1]) {
                std::swap(arr[j], arr[j+1]);
            }
        }
        --ed;
    }
}

为了提高排序效率,可以做一个简单优化:若一轮遍历中没有元素交互,则可认为整个数组已有序,此时可中断排序:

void bubblesort(int* arr, int bg, int ed)
{
    int counter = ed - bg - 1;
    bool done = false;
    while(counter-- and !done) {
        done = true;
        for(int j = bg; j < ed - 1; ++j) {
            if(arr[j] > arr[j+1]) {
                done = false;
                std::swap(arr[j], arr[j+1]);
            }
        }
        --ed;
    }
}

直接插入排序

直接插入排序的思路:维持一个已序的数组,每次往数组里添加一个元素,并保证加入新元素后数组依然保持有序。用直接排序算法排序a[n]:a[1]是已序(只有1个元素),将a[2]加入,使a[1..2]已序;将a[3]加入,使a[1..3]已序,以此类推。

打扑克牌时抓牌放在手中就是一个典型的插入排序。当摸起第1张手牌时数组已序(只有1个元素),之后每摸一张牌,我们都保障它插入到正确的位置,以使整个手牌已序。

void insertsort(int* arr, int bg, int ed)
{
    int tmp, j;
    for(int i = bg + 1; i < ed; ++i) {
        tmp = arr[i];
        for(j = i - 1; j > -1 and arr[j] > tmp; --j) {
            arr[j+1] = arr[j];
        }
        arr[j+1] = tmp;
    }
}

分享

0