直接选择排序

直接选择排序是一种很直观的排序方法。其操作是这样：先在未排序的序列中选择最小的元素（或最大的元素），把它与第一个元素交换，放在第一个位置，再在剩余未排序序列中选择第二小的，与第二个元素交换，放在第二个位置，以此类推，直到所有序列排序完毕。

这种排序方法应该是大部分人最直观的一种排序方法，下面就根据一个实际例子来看看其过程。

排序过程

下面以一个未排序的数组[5,1,2,3,4]为例，展示其排序过程：

select_sort

算法效率

时间复杂度: $O({n}^{2})$ ，因为无论数组是哪种情况，都需要进行两次for循环，都是确定数组前n-1个最小值，即使数组是本身有序的。

空间复杂度为 $O({1})$ ，因为只使用有限个数的变量。

实现代码

#include <stdio.h> void swap(int *xp, int *yp) 
{ int temp = *xp; *xp = *yp; *yp = temp; 
} void selectionSort(int arr[], int n) 
{ int i, j, min_idx; // One by one move boundary of unsorted subarray for (i = 0; i < n-1; i++) { // Find the minimum element in unsorted array min_idx = i; for (j = i+1; j < n; j++) if (arr[j] < arr[min_idx]) min_idx = j; // Swap the found minimum element with the first element swap(&arr[min_idx], &arr[i]); } 
} /* Function to print an array */
void printArray(int arr[], int size) 
{ int i; for (i=0; i < size; i++) printf("%d ", arr[i]); printf("\n"); 
} // Driver program to test above functions 
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; 
}