当前位置：首页 > article >正文

【最基础最直观的排序 —— 选择排序算法】

article 2024/9/27 6:04:48

最基础最直观的排序 —— 选择排序算法

选择排序算法是一种简单直观的排序算法。其基本思想是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（或最大）元素，放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。
在这里插入图片描述

以下是用 Java 实现的选择排序代码示例：

public class SelectionSort {
    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;
                }
            }
            // 交换最小元素和当前位置的元素
            int temp = array[minIndex];
            array[minIndex] = array[i];
            array[i] = temp;
        }
    }
    public static void main(String[] args) {
        int[] array = {64, 34, 25, 12, 22, 11, 90};
        selectionSort(array);
        System.out.println("排序后的数组：");
        for (int i : array) {
            System.out.print(i + " ");
        }
    }
}

在 Python 中的实现如下：

def selection_sort(alist):
    for i in range(len(alist)-1):
        max_index=i
        for j in range(i+1,len(alist)):
            if alist[j]>alist[max_index]:
                max_index=j
        alist[max_index],alist[i]=alist[i],alist[max_index]
    return alist

if __name__ == '__main__':
    alist=(449,333,441,555,666,777,888,999,332,222,111)
    print("the init of list is:",alist)
    print("the sorted of list is:",selection_sort(alist))

选择排序算法通过两个嵌套的循环来实现。外层循环控制已排序部分的增长，内层循环用于找到未排序部分的最小（或最大）元素的索引。找到最小（或最大）元素后，将其与未排序部分的第一个元素进行交换，从而逐步将整个序列排序完成。

选择排序算法的时间复杂度为 O(n²)，其中 n 是待排序元素的数量。这是因为无论原始数据的排列情况如何，算法都需要进行相同数量的比较和交换操作。空间复杂度为 O(1)，因为它只需要有限的额外空间来存储临时变量，而不依赖于输入数据的大小。

选择排序算法虽然简单易懂，但在处理大规模数据时效率较低。在实际应用中，可以根据具体情况选择更高效的排序算法，如快速排序、归并排序等。

选择排序算法思想是什么

选择排序是一种简单直观的排序算法。其基本思想是将待排序的数据分为已排序和未排序两部分。首先在未排序的数列中查找到最小（或最大）元素，然后将其存放到数列的起始位置，此时已排序部分就有了一个元素。接着，再从剩余未排序的元素中继续寻找最小（或最大）的元素，放到已排序序列的末尾。如此重复这个过程，直到所有元素都被排序完毕。

例如，对于数组{20,40,30,10,60,50}，第一趟会找到最小元素10，将其与数组第一个元素20交换，得到{10,40,30,20,60,50}。第二趟从剩余未排序元素{40,30,20,60,50}中找到最小元素20，与第二个元素40交换，变为{10,20,30,40,60,50}。后面继续这个过程，直到整个数组有序。

选择排序的优点是实现简单，不占用额外的内存空间。缺点是时间复杂度较高，为O(n²)，不太适合处理大规模数据。

选择排序算法的 Java 实现代码

以下是选择排序算法的 Java 实现代码：

public class SelectionSort {
    public static void main(String[] args) {
        int[] arr = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
        arr = selectionSort(arr);
        for (int a : arr) {
            System.out.print(a + ",");
        }
    }

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

在这个实现中，外层循环控制当前待排序的位置，内层循环用来找到未排序部分的最小元素的下标。然后将当前待排序位置的元素与最小元素进行交换。通过持续地重复这个过程，直到所有元素都被排序。

选择排序算法的 Python 实现代码

选择排序算法的 Python 实现如下：

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_index = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr

nums = 
print("待排序的数列：", nums)
sorted_nums = selection_sort(nums)
print("排序后的结果为：", sorted_nums)

这段代码首先定义了一个函数selection_sort，函数接收一个待排序的列表作为参数。在函数内部，通过两个嵌套的循环实现选择排序。外层循环遍历列表的每个位置，内层循环在未排序部分找到最小元素的下标。最后，将当前位置的元素与最小元素进行交换，直到整个列表有序。

选择排序算法时间复杂度是多少

选择排序算法的时间复杂度为 O(n²)。其中 n 是待排序数据的数量。

选择排序的工作方式是每一次从待排序的数据中选择最小（或者最大）的一个元素，放到序列的起始位置，直到全部待排序的元素排完。在每一趟排序中，都需要遍历未排序部分的所有元素来找到最小（或最大）元素，对于一个长度为 n 的数组，第一趟需要比较 n - 1 次，第二趟需要比较 n - 2 次，以此类推。总的比较次数为 (n - 1) + (n - 2) +… + 1，根据等差数列求和公式可得总比较次数为 n(n - 1)/2，近似为 n²/2。当 n 趋向于无穷大时，时间复杂度的量级为 n²，记作 O(n²)。

虽然选择排序的时间复杂度比较高，但是由于其实现简单，所以在数据规模较小时，选择排序仍然是一种较为常用的排序算法。