c语言排序算法之六(选择排序)

前言

以下内容是被验证可以有效理解选择排序，代码也较容易理解。如果你发现还有很多需要增加的，欢迎留言。

为什么要单独写排序算法这一系列，看过一些贴子普遍篇幅较长。看完还依旧云里雾里，难以直观理解原理及整个过程。代码永远是基于理解的基础上才能实现。

执行过程能动画展示需方便清晰，同时需具备单步调试，方便没理解的可以回看。

语言比较推荐c语言，高级语言库函数较多，人都有惰性思维，将自己置身于环境中训练也是至关重要。

问题与思考:学了这么多排序算法，有什么区别呢？文末QA缓解帮助大家理解。

实现原理

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

选择排序的过程可以概括为：

1. 从数组的第一个元素开始，遍历整个数组，寻找最小（或最大）的元素。
2. 将找到的最小（或最大）元素与数组的第一个元素互换位置。
3. 重新开始遍历，这次从第二个元素开始，重复上述步骤。
4. 继续这个过程，直到整个数组都排好序，即所有的元素都已按照升序（或降序）排列。

选择排序的时间复杂度是O(n^2)，其中n是数组的元素个数。这种排序算法适用于较小的数据集，但在大规模数据集的排序中，效率较低。优点是排序过程中需要的额外空间较少，空间复杂度为O(1)。然而，选择排序不是稳定性排序算法，相同的元素在排序前的相对前后位置和排序完成后的，相对前后位置可能不一致。

动画展示过程(Selection Sort)

Comparison Sorting Visualization

具体代码实现

#include <stdio.h>
 
void selectionSort(int arr[], int n) {
    int i, j, min_idx;
    for (i = 0; i < n - 1; i++) {
        // 找到未排序部分的最小值
        min_idx = i;
        for (j = i + 1; j < n; j++)
            if (arr[j] < arr[min_idx])
                min_idx = j;
        
        // 交换最小值到正确的位置
        int temp = arr[i];
        arr[i] = arr[min_idx];
        arr[min_idx] = temp;
    }
}
 
void printArray(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
 
int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    selectionSort(arr, n);
    printf("Sorted array: \n");
    printArray(arr, n);
    return 0;
}

Q1:选择排序和冒泡排序时间复杂度一样，那么实际性能一样吗？

A1:不一样，选择排序实际性能好。由于冒泡排序过程中大量的交换元素。

Q2:选择排序为什么是不稳定的？

A1:举例:2(0),2(1),3(2),4(3),1(4)排序后是1(4),2(1),2(0),3(2),4(3),可以看到相同的2下标位置前后顺序颠倒。

Q3:排序算法的稳定性意义？

A3:如果原本的初始顺序存在意义，那么我们需要在二次排序的基础上保持原有排序的意义，才需要使用到稳定性的算法，例如要排序的内容是一组原本按照价格高低排序的对象，如今需要按照销量高低排序，使用稳定性算法，可以使得想同销量的对象依旧保持着价格高低的排序展现，只有销量不同的才会重新排序。