c语言怎么实现选择排序算法代码示例

前言

选择排序是一种简单的排序算法，只需要极少的额外内存空间，可以实现稳定的原地排序，其时间复杂度为O(n^2)，并不适用于大规模数据的排序。

算法思路

选择排序的基本思路是，从未排序的元素中选出最小的元素，将其放到已排序序列的末尾，然后再从未排序元素中继续选出最小元素，放到已排序序列的末尾。直到所有元素均已排序完毕。

代码示例

下面是使用C语言实现选择排序算法的示例代码：

#include 

void selection_sort(int arr[], int len) {
    int i, j, min_idx;
    for (i=0; i < len-1; i++) {
        min_idx=i;
        for (j=i+1; j < len; j++) {
            if (arr[j] < arr[min_idx])
                min_idx=j;
        }
        // Swap the found minimum element with the first element
        int temp=arr[min_idx];
        arr[min_idx]=arr[i];
        arr[i]=temp;
    }
}

int main() {
    int arr[]={64, 25, 12, 22, 11};
    int len=sizeof(arr)/sizeof(arr[0]);
    selection_sort(arr, len);
    printf("Sorted array: \n");
    for (int i=0; i < len; i++)
        printf("%d ", arr[i]);
    return 0;
}

代码解释

首先，在主函数中定义了一个无序数组arr，调用selection_sort函数进行排序，最后输出排完序后的数组。

selection_sort函数的实现中，外层循环控制排序的轮数，循环次数为len-1，因为排序完成n-1轮后，数组已经有序了，无需再进行排序。内层循环找到未排序元素中的最小元素，并将其与已排序序列的末尾元素进行交换。

因为该算法是原地排序，没有使用额外的内存空间，所以是一种空间复杂度为O(1)的算法。而其时间复杂度为O(n^2)。

总结

选择排序是一种简单、稳定的原地排序算法，但其时间复杂度为O(n^2)，并不适用于大规模数据的排序。其基本思路是从未排序元素中选出最小元素，放到已排序序列的末尾，重复以上步骤直到所有元素均已排序。通过上述代码示例和解释，相信大家可以更好地了解和掌握选择排序算法。