常用的排序算法之选择排序（Selection Sort）-阿南达文事网

常用的排序算法之选择排序（Selection Sort）

选择排序（Selection Sort）

原理

选择排序（Selection Sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。这种排序方法是不稳定的排序方法。选择排序的起源并不明确，但它是计算机科学中最早提出的排序算法之一。

定义

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

扩展应用

选择排序的思想可以扩展到选择K个最小（或最大）的元素，或者选择第K小的元素等问题上。此外，选择排序的思想也可以用于一些更复杂的算法中，如堆排序和快速选择算法。

优缺点

优点：

实现简单直观，易于理解。
在数据规模较小的情况下，效率可以接受。

缺点：

时间复杂度较高，为O(n^2)，在大数据集上性能不佳。
是不稳定的排序算法，即相等的元素在排序后可能会改变其原有的顺序。

使用场景

选择排序通常用于数据量较小且对时间效率要求不高的场景，或者作为教学示例来帮助学生理解排序算法的基本概念。由于它的不稳定性，对于需要保持元素原始顺序的排序任务可能不适用。

使用数据一步步举例

假设有一个数组[64, 25, 12, 22, 11]，我们使用选择排序来对其进行升序排序：

第一轮选择：
- 找到最小元素11，与第一个元素64交换位置。
- 数组变为[11, 25, 12, 22, 64]
第二轮选择：
- 在剩余元素[25, 12, 22, 64]中找到最小元素12，与第二个元素25交换位置。
- 数组变为[11, 12, 25, 22, 64]
第三轮选择：
- 在剩余元素[25, 22, 64]中找到最小元素22，与第三个元素25交换位置。
- 数组变为[11, 12, 22, 25, 64]
第四轮选择：
- 最后一个元素64已经是剩余元素中的最大值，无需交换。
- 数组保持为[11, 12, 22, 25, 64]

Java示例代码

代码语言：javascript代码运行次数：0运行复制

public class SelectionSort {  
    public static void main(String[] args) {  
        int[] array = {64, 25, 12, 22, 11};  
        selectionSort(array);  
        System.out.println(Arrays.toString(array));  
    }  
  
    public static void selectionSort(int[] array) {  
        int n = array.length;  
        for (int i = 0; i < n - 1; i++) {  
            int minIndex = i;  
            for (int j = i + 1; j < n; j++) {  
                if (array[j] < array[minIndex]) {  
                    minIndex = j;  
                }  
            }  
            // 交换找到的最小元素到当前位置  
            if (minIndex != i) {  
                int temp = array[minIndex];  
                array[minIndex] = array[i];  
                array[i] = temp;  
            }  
        }  
    }  
}

运行上述代码，将输出排序后的数组[11, 12, 22, 25, 64]。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。原始发表：2024-05-27，如有侵权请联系 cloudcommunity@tencent 删除排序排序算法数组selectionsort

常用的排序算法之选择排序（Selection Sort）