选择排序(Selection sort)
1. 概要说明
选择排序是直观的排序，通过从待排序的的数组中找出最大或最小的交换到对应位置。
算法描述：
- 在一个长度为 N 的无序数组中，第一次遍历 n-1 个数找到最小的和第一个数交换。
- 第二次从下一个数开始遍历 n-2 个数，找到最小的数和第二个数交换。
- 重复以上操作直到第 n-1 次遍历最小的数和第 n-1 个数交换，排序完成。
There are many different ways to sort the cards. Here’s a simple one, called selection sort:
- Find the smallest card. Swap it with the first card.
- Find the second-smallest card. Swap it with the second card.
- Find the third-smallest card. Swap it with the third card.
- Repeat finding the next-smallest card, and swapping it into the correct position until the array is sorted.
This algorithm is called selection sort because it repeatedly selects the next-smallest element and swaps it into place.
2. 动图演示
3. C++实现选择排序
#include <iostream>
using namespace std;
void selection_sort(int arr[], int len)
{
int i,j;
for (i = 0 ; i < len - 1 ; i++)
{
int min = i;
for (j = i + 1; j < len; j++) //遍历未排序的元素
if (arr[j] < arr[min]) //找到目前最小值
min = j; //记录最小值的位置
//交换
int tmp = arr[i];
arr[i] = arr[min];
arr[min] = tmp;
}
}
int main()
{
int arr[8] = {3, 5, 7, 11, 13, 2, 9, 6};
selection_sort(arr, 8);
for (int i = 0; i < 8; i++)
{
cout << arr[i] << " ";
}
return 0;
}