数据结构与算法之选择排序

一、C语言之数据结构与算法之选择排序源码实现及详解

选择排序是一种简单直观的排序算法，其思想为每次找出未排序部分中最小（或最大）的元素，将其与未排序部分的第一个元素进行交换，直到所有元素排序完成。选择排序的时间复杂度为 O(n^2)，空间复杂度为 O(1)，比较次数和交换次数均为 n(n-1)/2。

以下是选择排序的 C 语言实现及详解：

void selection_sort(int arr[], int len) {
    int i, j, min_index;
    for (i = 0; i < len - 1; i++) {  // i 表示未排序部分的起始下标
        min_index = i;
        for (j = i + 1; j < len; j++) {  // j 表示未排序部分的当前下标
            if (arr[j] < arr[min_index]) {
                min_index = j;  // 找到未排序部分中的最小元素下标
            }
        }
        if (min_index != i) {  // 如果最小元素不是未排序部分的第一个元素，则交换它们
            int temp = arr[i];
            arr[i] = arr[min_index];
            arr[min_index] = temp;
        }
    }
}

选择排序的核心代码是两层循环，第一层循环表示当前未排序部分的起始下标，第二层循环则表示未排序部分的当前下标。在第二层循环中，通过比较找到未排序部分中的最小元素下标，如果最小元素不是未排序部分的第一个元素，则将它与第一个元素交换。

以下是选择排序的简单测试代码：

#include <stdio.h>

void selection_sort(int arr[], int len);

int main() {
    int arr[] = {5, 7, 1, 3, 8, 4, 2, 9, 6};
    int len = sizeof(arr) / sizeof(int);
    int i;

    printf("Before sorting:");
    for (i = 0; i < len; i++) {
        printf(" %d", arr[i]);
    }

    selection_sort(arr, len);

    printf("\nAfter sorting:");
    for (i = 0; i < len; i++) {
        printf(" %d", arr[i]);
    }

    return 0;
}

输出结果为：

Before sorting: 5 7 1 3 8 4 2 9 6
After sorting: 1 2 3 4 5 6 7 8 9

可以看到，选择排序确实将数组按从小到大的顺序进行了排序。

二、C++语言之数据结构与算法之选择排序源码实现及详解

选择排序（Selection Sort）是一种简单直观的排序算法，它的基本思想是：首先在未排序的数列中找到最小元素，然后将其存放到数列的起始位置；接着，再从剩余的未排序元素中继续寻找最小元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

选择排序的时间复杂度为O(n^2)，和冒泡排序一样效率较低，但是由于其简单直观，代码实现也较为简单，因此在某些场景下还是有用武之地的。

下面是C++语言实现选择排序的代码及详解注释：

#include <iostream>
using namespace std;

void selectionSort(int arr[], int n) { // 定义选择排序函数
    for (int i = 0; i < n - 1; i++) { // 外层循环，从i=0开始，到n-2结束
        int minIndex = i; // 设定最小值下标为i
        for (int j = i + 1; j < n; j++) { // 内层循环，从j=i+1开始，到n-1结束
            if (arr[j] < arr[minIndex]) { // 若arr[j]比arr[minIndex]小
                minIndex = j; // 更新最小值下标
            }
        }
        // 交换arr[i]和arr[minIndex]的值
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

int main() {
    int arr[] = {2, 5, 1, 8, 3}; // 定义待排序数组
    int n = sizeof(arr) / sizeof(arr[0]); // 求数组长度
    cout << "Original array:";
    for (int i = 0; i < n; i++) {
        cout << " " << arr[i]; // 输出原始数组
    }
    cout << endl;
    selectionSort(arr, n); // 调用选择排序函数
    cout << "Sorted array:";
    for (int i = 0; i < n; i++) {
        cout << " " << arr[i]; // 输出排序后的数组
    }
    cout << endl;
    return 0;
}

该程序运行结果如下：

Original array: 2 5 1 8 3
Sorted array: 1 2 3 5 8

选择排序的原理比较简单，就是不断寻找未排序部分的最小值，并将其放到已排序部分的末尾。具体实现中，需要使用两层循环：外层循环控制已排序部分的范围，内层循环则用于在未排序部分中寻找最小值。每次找到最小值后，都将其与未排序部分的第一个数交换位置。

从代码实现中可以看出，选择排序需要进行n-1次循环，最好情况下时间复杂度为O(n^{2)，最坏情况下的时间复杂度也是O(n}2)，因此它并不是一种高效的排序算法。在实际应用中，选择排序的主要作用是用来教学，以便让学习者深刻理解排序算法的原理和过程。选择排序（Selection Sort）是一种简单直观的排序算法，它的基本思想是：首先在未排序的数列中找到最小元素，然后将其存放到数列的起始位置；接着，再从剩余的未排序元素中继续寻找最小元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

选择排序的时间复杂度为O(n^2)，和冒泡排序一样效率较低，但是由于其简单直观，代码实现也较为简单，因此在某些场景下还是有用武之地的。

下面是C++语言实现选择排序的代码及详解注释：

#include <iostream>
using namespace std;

void selectionSort(int arr[], int n) { // 定义选择排序函数
    for (int i = 0; i < n - 1; i++) { // 外层循环，从i=0开始，到n-2结束
        int minIndex = i; // 设定最小值下标为i
        for (int j = i + 1; j < n; j++) { // 内层循环，从j=i+1开始，到n-1结束
            if (arr[j] < arr[minIndex]) { // 若arr[j]比arr[minIndex]小
                minIndex = j; // 更新最小值下标
            }
        }
        // 交换arr[i]和arr[minIndex]的值
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

int main() {
    int arr[] = {2, 5, 1, 8, 3}; // 定义待排序数组
    int n = sizeof(arr) / sizeof(arr[0]); // 求数组长度
    cout << "Original array:";
    for (int i = 0; i < n; i++) {
        cout << " " << arr[i]; // 输出原始数组
    }
    cout << endl;
    selectionSort(arr, n); // 调用选择排序函数
    cout << "Sorted array:";
    for (int i = 0; i < n; i++) {
        cout << " " << arr[i]; // 输出排序后的数组
    }
    cout << endl;
    return 0;
}

该程序运行结果如下：

Original array: 2 5 1 8 3
Sorted array: 1 2 3 5 8

选择排序的原理比较简单，就是不断寻找未排序部分的最小值，并将其放到已排序部分的末尾。具体实现中，需要使用两层循环：外层循环控制已排序部分的范围，内层循环则用于在未排序部分中寻找最小值。每次找到最小值后，都将其与未排序部分的第一个数交换位置。

从代码实现中可以看出，选择排序需要进行n-1次循环，最好情况下时间复杂度为O(n^{2)，最坏情况下的时间复杂度也是O(n}2)，因此它并不是一种高效的排序算法。在实际应用中，选择排序的主要作用是用来教学，以便让学习者深刻理解排序算法的原理和过程。

三、java语言之数据结构与算法之选择排序源码实现及详解

选择排序(Selection Sort)是一种简单直观的排序算法，其基本思想是每一趟从待排序的数据元素中选出最小(或最大)的一个元素，存放到序列的起始位置，直到全部待排序的数据元素排完。

下面是Java语言实现选择排序的源代码：

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

选择排序的核心是双重循环。外层循环控制每一轮比较的起点，内层循环则从待排序元素中选择最小(或最大)的元素，并将其与起点元素交换位置。这样，每一轮选择排序就确定了一个元素的最终位置，经过n-1轮的排序之后，就可以将整个序列排好序。时间复杂度为O(n²)。

选择排序的优点是简单易懂，实现容易；缺点是排序过程中无法保证相同元素的相对位置不变。选择排序(Selection Sort)是一种简单直观的排序算法，其基本思想是每一趟从待排序的数据元素中选出最小(或最大)的一个元素，存放到序列的起始位置，直到全部待排序的数据元素排完。

下面是Java语言实现选择排序的源代码：

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

选择排序的核心是双重循环。外层循环控制每一轮比较的起点，内层循环则从待排序元素中选择最小(或最大)的元素，并将其与起点元素交换位置。这样，每一轮选择排序就确定了一个元素的最终位置，经过n-1轮的排序之后，就可以将整个序列排好序。时间复杂度为O(n²)。

选择排序的优点是简单易懂，实现容易；缺点是排序过程中无法保证相同元素的相对位置不变。