选择排序

## 选择排序
![](/media/202205/20210509190545640_1653632376.gif)

**基本思想：**
- 即每次从待排序列中选出一个最小值，然后放在序列的起始位置，直到全部待排数据排完即可

**算法描述：**
n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果：
1. 初始状态：无序区为R[1…n]，有序区为空
2. 第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1…i-1]和R(i…n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1…i]和R[i+1…n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区
3. n-1趟结束，数组有序化了

[wokwi_选择排序](https://wokwi.com/projects/332791245340410451)|[wokwi_选择排序](https://wokwi.com/projects/334327008171393618)
### 选择排序(一次一个数)
```c
// 选择排序(一次一个数),SelectSort(数组名,数组长度,[排序方向,默认小到大])
// 即每次从待排序列中选出一个最小值,然后放在序列的起始位置,直到全部待排数据排完即可
void SelectSort(int array[], int size,boolean forward = true){
	// i代表参与该趟选择排序的第一个元素的下标
	for (int i = 0; i < size; i++){
		// 当前选择的元素
		int start = i;
		// 记录最小元素的下标
		int min = start;
		while (start < size){
			// 根据传入的第三个参数,来确定是正向排序(小到大)还是逆向排序(大到小)
			if (forward == true){
				// 判断当前元素和选择的元素那个是最小值,保留最小元素
				if (array[start] < array[min]){
					// 最小值的下标更新
					min = start;
				}
			}else{
				if (array[start] > array[min]){
				// 因为要逆向排序,实际这里是找出最大值了
				min = start;
			}
		}
		// 当前选择元素下标增加(往后比较)
		start++;
		}
		// 比较完成后,把当前排序第一个元素与刚筛选出来的最小元素交换位置
		int tmp = array[i];
		array[i] = array[min];
		array[min] = tmp;
	}
}
```

### 选择排序(一次两个数)
```c
// 选择排序(一次两个数),TwoSelectSort(数组名,数组长度,[排序方向,默认小到大])
// 一趟选出两个值，一个最大值一个最小值，然后将其放在序列开头和末尾，这样可以使选择排序的效率快一倍
void TwoSelectSort(int array[], int size,boolean forward = true){
	// 记录参与该趟选择排序的第一个元素的下标
	int left = 0;
	// 记录参与该趟选择排序的最后一个元素的下标
	int right = size - 1;
	// 从两边往内，直到两个下标都指向中间
	while (left < right){
		int minIndex = left;//记录最小元素的下标
		int maxIndex = left;//记录最大元素的下标
		// 找出最大值及最小值的下标
		for (int i = left; i <= right; i++){
			// 根据传入的第三个参数,来确定是正向排序(小到大)还是逆向排序(大到小)
			if (forward == true){
				// 判断当前元素是否大于或小于当前记录的最大最小元素
				if (array[i] < array[minIndex]) minIndex = i;
				if (array[i] > array[maxIndex]) maxIndex = i;
			}else{
				if (array[i] > array[minIndex]) minIndex = i;
				if (array[i] < array[maxIndex]) maxIndex = i;
			}
		}
		// 将最大值和最小值放在序列开头和末尾
		// 比较完成后,把当前左侧元素与刚筛选出来的最小元素交换位置
		int mintmp = array[left];
		array[left] = array[minIndex];
		array[minIndex] = mintmp;
		if (left == maxIndex){
		// 防止最大值位于序列开头，被最小值交换
			maxIndex = minIndex;
		}
		// 比较完成后,把当前右侧元素与刚筛选出来的最大元素交换位置
		int maxtmp = array[right];
		array[right] = array[maxIndex];
		array[maxIndex] = maxtmp;
		// 下标移动，开始新的比较
		left++;
		right--;
	}
}
```