排序算法 - 选择排序(Selection Sort)

by LauCyun Jul 26,2014 22:22:12 3,913 views

核心:不断地选择剩余元素中的最小者。如图2所示。

  • 找到数组中最小元素并将其和数组第一个元素交换位置。
  • 在剩下的元素中找到最小元素并将其与数组第二个元素交换,直至整个数组排序。

性质:

  • 比较次数=\((n-1)+(n-2)+(n-3)+...+1=\frac{n(n-1)}{2}<O(n^2)\)
  • 交换次数介于0与\(n-1\)之间
  • 运行时间与输入无关
  • 数据移动最少

图1 Selection Sort

1 算法实现

c++

#include<iostream>

using namespace std;
const int N = 10;
using ElemType = int;

void SelectSort(ElemType *array);

void Show(ElemType *array);

void SelectSort(ElemType *array) {
    for (int i = 0; i < N - 1; i++) {
        int index = i;
        for (int j = i + 1; j < N; j++) {
            if (array[j] < array[index]) {
                index = j;
            }
        }
        if (i != index) {
            ElemType temp = array[i];
            array[i] = array[index];
            array[index] = temp;
        }
        cout << "i = " << i << " => ";
        Show(array);
    }
}

void Show(ElemType *array) {
    for (int i = 0; i < N; i++) {
        printf("%-4d", array[i]);
    }
    printf("\n");
}

int main() {
    ElemType array[N] = {8, 5, 2, 6, 9, 3, 1, 4, 0, 7};
    Show(array);
    SelectSort(array);
    Show(array);
    return 0;
}

python

#!/usr/bin/env python
# -*- coding: utf-8 -*-

def selectionSort(alist):
    list_len = alist.__len__()
    for i in range(0, list_len):
        print(alist)
        min_index = i
        for j in range(i + 1, list_len):
            if alist[j] < alist[min_index]:
                min_index = j
        alist[min_index], alist[i] = alist[i], alist[min_index]
    return alist


unsorted_list = [8, 5, 2, 6, 9, 3, 1, 4, 0, 7]
print(selectionSort(unsorted_list))

 

2 算法过程演示

如果显示效果不佳,请戳 这里

 

3 复杂度分析

最好情况、最坏情况和平均情况均为 \(O(n^2)\),使用了 temp 作为临时交换变量,空间复杂度为\(O(1)\)

原地操作几乎是选择排序的唯一优点,当空间复杂度要求较高时,可以考虑选择排序;实际适用的场合非常罕见。

 

4 参考文档

(全文完)

Tags