Selection Sort

Posted on In

选择排序是交换排序的一种。它的思想是每一轮选出最小者交换到左侧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <stdio.h>
#include <cstdio>
#include "dbg.h"
using namespace std;

void selectSort(int R[], int len);


int main(int argc, char *argv[])
{
    int R[] = {1, 3, 2, 18, 3, 28, 23, 38, 7, 8};
    cout << "Before sorting: " << endl;
    dbg(R);
    int len = sizeof(R) / sizeof(R[0]);
    cout << "After sorting : " << endl;
    selectSort(R, len);
    dbg(R);
    return 0;
}

void selectSort(int R[], int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        int minIndex = i;
        // 1. 找到元素i右侧最小值
        for (int j = i + 1; j < n; j++)
        {
            minIndex = R[j] < R[minIndex] ? j : minIndex;
            //if (R[j] < R[minIndex])
            //    minIndex = j;
        }
        // 2. 交换
        int temp = R[i];
        R[i] = R[minIndex];
        R[minIndex] = temp;
    }
}

运行结果:
selectSort

时间复杂度: O(n^2)

  1. 每次寻找最小值再交换到左侧是O(n)
  2. 循环n-1轮是O(n)

空间复杂度: O(1)

注意：选择排序并不稳定，当序列中含有多个值相同的元素时，会使这些值相对次序发生变化。