排序算法:选择排序

icy2003 程序 2020-05-08 18:22:40 112 0条

选择排序(Selection Sort)是一种简单直观的排序算法。它的工作原理如下,首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕

640 (1).gif

算法评价

  • 平均时间复杂度:O(n^2)
  • 最好情况:O(n^2)
  • 最坏情况:O(n^2)
  • 空间复杂度:O(1)
  • 稳定性:不稳定

算法思想

  1. 在未排序序列中找到最小(大)元素,存放到排序序列的起始位置。
  2. 从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。
  3. 以此类推,直到所有元素均排序完毕。

实例分析

以数组 arr = [8, 5, 2, 6, 9, 3, 1, 4, 0, 7] 为例,先直观看一下每一步的变化,后面再介绍细节

第一次从数组 [8, 5, 2, 6, 9, 3, 1, 4, 0, 7] 中找到最小的数 0,放到数组的最前面(与第一个元素进行交换):

                               min
                                ↓
8   5   2   6   9   3   1   4   0   7
↑                               ↑
└───────────────────────────────┘

交换后:

0   5   2   6   9   3   1   4   8   7

在剩余的序列中 [5, 2, 6, 9, 3, 1, 4, 8, 7] 中找到最小的数 1,与该序列的第一个个元素进行位置交换:

                       min
                        ↓
0   5   2   6   9   3   1   4   8   7
    ↑                   ↑
    └───────────────────┘

交换后:

0   1   2   6   9   3   5   4   8   7

在剩余的序列中 [2, 6, 9, 3, 5, 4, 8, 7] 中找到最小的数 2,与该序列的第一个个元素进行位置交换(实际上不需要交换):

       min
        ↓
0   1   2   6   9   3   5   4   8   7
        ↑

重复上述过程,直到最后一个元素就完成了排序。

                   min
                    ↓
0   1   2   6   9   3   5   4   8   7
            ↑       ↑
            └───────┘

                           min
                            ↓
0   1   2   3   9   6   5   4   8   7
                ↑           ↑
                └───────────┘

                       min
                        ↓
0   1   2   3   4   6   5   9   8   7
                    ↑   ↑
                    └───┘

                       min
                        ↓
0   1   2   3   4   5   6   9   8   7
                        ↑   

                                   min
                                    ↓
0   1   2   3   4   5   6   9   8   7
                            ↑       ↑
                            └───────┘  

                               min
                                ↓
0   1   2   3   4   5   6   7   8   9
                                ↑      

                                   min
                                    ↓
0   1   2   3   4   5   6   7   8   9
                                    ↑

Selection-Sort-Animation.gif

代码示例

Javascript

function selectionSort(array) {
    var length = array.length,
        i,
        j,
        minIndex,
        minValue,
        temp;
    for (i = 0; i < length - 1; i++) {
        minIndex = i;
        minValue = array[minIndex];
        for (j = i + 1; j < length; j++) {
            if (array[j] < minValue) {
                minIndex = j;
                minValue = array[minIndex];
            }
        }

        // 交换位置
        temp = array[i];
        array[i] = minValue;
        array[minIndex] = temp;
    }
    return array
}
标签: 算法

非特殊说明,本博所有文章均为博主原创。