选择排序

shawsun 2020-04-17

简述

选择排序的基本思想是:每一趟从待排序列中选取关键字最小的元素,作为有序序列的一个新的元素,直到待排序列只剩下一个元素,则完成排序。主要算法有简单选择排序和堆排序。

简单选择排序

算法思想

假设序列为L[1...n],第i趟排序从L[i...n]中选择最小的元素与L(i)交换,因此每一趟可以确定一个元素的最终位置,这样经过n-1趟排序可以使得整个序列有序。

算法性能分析

  • 空间效率:使用常数个辅助单元,故空间复杂度为\(O(1)\)
  • 时间效率:元素移动操作不会超过\(3(n-1)\)次,最好的情况是0次;而元素比较操作则固定有\(\sum_{i=1}^{n-1}i\)次,所以时间复杂度为\(O(n^2)\)
  • 稳定性:是不稳定的。

C++实现

#include <iostream>
using namespace std;

void selectSort(int a[], int n) {
    for (int i = 0; i < n; ++i) {
        int minIndex = i;
        for (int j = i + 1; j < n; ++j) // 找到最小元素的下标
            if (a[j] < a[minIndex])
                minIndex = j;
        if(minIndex != i)
            swap(a[i], a[minIndex]);    // 放置最小元素
    }
}

int main() {
    const int SIZE = 10;
    int a[SIZE] = { 0 };
    for (int i = 0; i < SIZE; ++i) {
        a[i] = rand() % 10;
        cout << a[i] << " ";
    }
    cout << "\n\n";

    selectSort(a, SIZE);

    for (auto elem : a)
        cout << elem << " ";

    return 0;
}

堆排序

算法思想

堆排序是一种树形选择排序方法,特点是:排序过程中,将序列看成是一棵完全二叉树的顺序存储结构,利用完全二叉树中双亲结点和孩子结点之间的内在关系,每次选择其中的最大(或最小)元素构成有序序列。

在堆排序的过程中,最主要的工作就是调整堆。我们从最后一个结点所在的子树开始筛选(对于大根堆,若根结点关键字小于左右子女中关键字的较大者,则交换),使该子树成为堆。之后向前依次对各结点为根的子树进行筛选,看该结点的值是否大于其左右子节点的值,若不是,则将左右结点中的较大者与之交换,交换后可能会破坏下一级的堆,于是需要继续采用上述方法构造下一级的堆,直到该结点没有子结点为止。重复这个过程,直至达到堆的根结点。

我们首先将调整一棵子树的算法总结出来,用a[0],a[1],...,a[n-1]表示一个堆,故结点a[i]的左孩子结点是a[2i+1],右孩子结点是a[2i+2]。而使用任意左右孩子结点的下标j同样可以获得其父结点,父结点的下标为(j-1)/2。因而我们可以得到以下的算法描述:

  1. 暂存需要调整的结点的值t;
  2. 判断是否当前需要调整的结点是否还有孩子结点,有则3,没有则5;
  3. 找出左右孩子中较大的结点;
  4. 如果该较大的结点大于t,则将该孩子结点上移,继续循环,进入2;否则退出循环,进入5;
  5. 当前位置即为合适位置,插入t。

有了调整一棵子树的算法,接下来的堆排序就比较简单了,主要有以下步骤:

  1. 将序列从最后一个结点的根结点开始逐个往上调整成堆;
  2. 取堆中的首元素(即为最大值或最小值)与堆中最后的元素进行交换,例如a[0]与a[n-1];
  3. 把交换后的序列重新调整成堆,例如a[0],...,a[n-2]。

这里需要注意的是,由于只交换了一个元素,整个堆是整体符合要求的,因此只需要对交换后的首元素进行堆调整就可以了。

算法性能分析

  • 空间效率:使用常数个辅助单元,空间复杂度为\(O(1)\)
  • 时间效率:建堆的时间为\(O(n)\),之后有n-1次调整的操作,每次调整的时间复杂度为\(O(h)\),故在最好、最坏和平均的情况下,堆排序的时间复杂度为\(O(nlog_2n)\)
  • 稳定性:调整过程中,有可能把后面的相同关键字元素移动到前面,因此是不稳定的。

C++实现

#include <iostream>
using namespace std;

// 调整以结点i为根结点的堆
void shiftDown(int a[], int i, int n) {
    int t = a[i], j;
    while ((j = 2 * i + 1) < n) {           // 如果有子结点
        if (j + 1 < n && a[j] < a[j + 1])   // 取子结点中较大的结点
            ++j;
        if (t < a[j]) {             // 较大的子结点上移
            a[(j - 1) / 2] = a[j];
            i = j;
        }
        else
            break;
    }
    a[(j - 1) / 2] = t;         // 插入需要调整的结点
}

void heapSort(int a[], int n) {
    for (int i = (n - 2) / 2; i >= 0; --i)  // 调整成堆
        shiftDown(a, i, n);
    for (int i = n - 1; i > 0; --i) {       // 每次选取堆的根结点
        swap(a[0], a[i]);
        shiftDown(a, 0, i);                 // 调整堆
    }
}

int main() {
    const int SIZE = 10;
    int a[SIZE] = { 0 };
    for (int i = 0; i < SIZE; ++i) {
        a[i] = rand() % 10;
        cout << a[i] << " ";
    }
    cout << "\n\n";

    heapSort(a, SIZE);

    for (auto elem : a)
        cout << elem << " ";


    return 0;
}

相关推荐