c语言如何实现选择排序算法「代码示例」

选择排序算法简介

选择排序算法是一种简单但是低效的排序算法，虽然它在速度上不如一些高级排序算法，但是它的思路清晰简单，容易理解，因此它是初学者学习排序算法的入门算法。选择排序算法的思路是，先在待排序序列中找到最小的元素，然后将其放到序列的起始位置，接着从剩余的元素中再找到最小的元素，将其放到已排序序列的末尾，直到所有的元素都被排序。

选择排序算法的步骤

选择排序算法的实现思路和它的算法步骤很相似，下面我们来看一下选择排序算法的步骤：

1. 在未排序序列中找到最小的元素，存放到排序序列的起始位置

首先，我们需要遍历待排序的序列，找到其中的最小元素，然后将它与序列的第一个元素进行交换。下面是这一步骤的代码实现：

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; 
  
        swap(&arr[min_idx], &arr[i]); 
    } 
} 

在上面的代码中，我们遍历了待排序的序列，使用了一个变量 min_idx 来记录当前序列中最小元素的下标，每当我们找到一个更小的元素时，就将 min_idx 更新为该元素的下标。遍历完成后，我们就可以将找到的最小元素和序列的第一个元素进行交换，完成第一步的操作。

2. 在剩余未排序序列中找到最小元素，放到已排序序列的末尾

第一步完成后，我们就可以开始第二步操作。此时，已经把最小的元素放到了序列的第一个位置，并且序列的剩余部分是未排序的。因此，我们只需要在剩余的序列中继续寻找最小的元素，然后把它放到已排序序列的末尾即可。下面是第二步的具体代码实现：

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; 
    swap(&arr[min_idx], &arr[i]); 
} 

在上面的代码中，我们的循环次数是 n - 1，因为在已经排序好的序列中越来越多的元素后面的序列元素个数也在逐渐减小，因此我们可以在循环中使用类似于冒泡排序算法的方式，不断把找到的最小元素和已排序序列的后面进行交换。这样，在最后一次循环结束后，整个序列就被排序完成了。

选择排序算法的优缺点分析

虽然选择排序算法非常容易理解和实现，但是它的时间复杂度和空间复杂度都比较低效：

时间复杂度：

选择排序算法的时间复杂度为 O(n^2)，这是因为选择排序算法的每一次遍历都需要在序列中找到最小的元素，这一步操作的时间复杂度为 O(n)，因此排序算法的时间复杂度为 O(n^2)。

空间复杂度：

选择排序算法的空间复杂度为 O(1)，这是因为只需要一个临时变量来记录最小元素的下标，因此它的空间复杂度非常低。

因此，尽管选择排序算法是一个容易理解的排序算法，但它的效率并不高。当需要对大规模的数据进行排序时，选择排序算法很可能会占用较多的计算资源，因此，在实际应用中，选择排序算法很少被使用。

选择排序算法的代码示例

下面是选择排序算法的完整代码示例：

#include  
  
void swap(int *xp, int *yp) 
{ 
    int temp = *xp; 
    *xp = *yp; 
    *yp = temp; 
} 
  
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; 
  
        swap(&arr[min_idx], &arr[i]); 
    } 
} 
  
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; 
}