选择排序法c语言代码

选择排序是一种简单直观的排序算法。它的原理是每次从待排序的元素中选出最小（或最大）的一个元素，将其放在已排序序列的末尾，直到全部元素排序完成。

以下是选择排序的C语言代码实现：

void Swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void SelectSort(int* arr, int size) {
    int i = 0;
    for (i = 0; i < size-1; i++) {
        int min = i;
        int j = 0;
        for (j = i+1; j < size; j++) {
            if (arr[j] < arr[min]) {
                min = j;
            }
        }
        Swap(&arr[i], &arr[min]);
    }
}

以上代码中，`Swap`函数用于交换两个数据，`SelectSort`函数用于实现选择排序。代码中通过两层循环，每次找出未排序部分的最小值，然后将其与未排序部分的首位元素交换位置。

选择排序的优化主要包括减少交换次数和减少比较次数。以下是一个优化后的选择排序代码实现：

void Swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void SelectSort(int* arr, int size) {
    int begin = 0;
    int end = size - 1;
    while (begin < end) {
        int max = begin;
        int min = begin;
        int i = 0;
        for (i = begin+1; i <= end; i++) {
            if (arr[i] < arr[min]) {
                min = i;
            }
            if (arr[i] > arr[max]) {
                max = i;
            }
        }
        Swap(&arr[begin], &arr[min]);
        if (begin == max) {
            max = min;
        }
        Swap(&arr[end], &arr[max]);
        begin++;
        end--;
    }
}

这个优化的代码通过在每次循环中同时找出最小值和最大值，减少了比较次数和交换次数。

选择排序的时间复杂度是O(n^2)，空间复杂度是O(1)。