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

选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上,则它不会被移动。选择排序每次交换一对元素,它们当中至少有一个将被移到其最终位置上,因此对 n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中,选择排序属于非常好的一种。

算法

首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置。

再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。

重复第二步,直到所有元素均排序完毕。

代码示例

java

public static void selectionSort(int[] arr){
    for (int i = 0; i < arr.length - 1; i++) {
        int  min = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[min] > arr[j]) {
                min = j;
            }
        }
        if (min != i) {
            int tmp = arr[min];
            arr[min] = arr[i];
            arr[i] = tmp;
        }
    }
}

python

def selectionSort(arr):
    for i in range(len(arr) - 1):
        # 记录最小数的索引
        minIndex = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[minIndex]:
                minIndex = j
        # i 不是最小数时,将 i 和最小数进行交换
        if i != minIndex:
            arr[i], arr[minIndex] = arr[minIndex], arr[i]
    return arr

【腾讯云】境外1核2G服务器低至2折,半价续费券限量免费领取!
https://cloud.tencent.com/act/cps/redirect?redirect=1068&cps_key=e4b50f6c64a4480367f8a8d16fd07c5a&from=console

标签: 算法, 选择排序, Selection sort

添加新评论