[数据结构与算法]保姆级教学：手把手教你写经典选择排序算法及其优化

此文章针对于小白中的小白，对于选择排序毫无思路，不知道怎么下手的。下面，我尽量展示我是怎么一步一步在大佬的指导下，写出排序算法的。秉持三个原则：

1. 由简单到复杂
   ① 验证一步走一步 ②多打印中间结果
2. 先局部后整体
3. 先粗糙后精细
   ①变量更名 ②语句合并 ③边界处理

经典选择排序算法

面对选择排序，不知道怎么下手，一筹莫展。定义一个数组，把他打印出来，总会吧。

int arr[] = { 6,2,3,7,1,4,5,8,0 };//定义无序数组
int length = sizeof(arr) / sizeof(arr[0]);//数组长度
//打印出来
for (auto i : arr)
		cout << i << " ";

原则1：先简单后复杂，然后运行看打印结果是不是对。
接下来，选择排序不就是，假定第一个元素是最小的，然后将后面未排序的数组一个一个与之比较，最终找出真正最小的元素嘛。
定义个标记点，要记录下最小位置

int minPos = 0;

然后就是将后面未排序的数组一个一个与之比较，for循环，很简单了吧

for (int j = 1; j < length; j++) {
			if (arr[j] < arr[minPos])
				minPos = j;
		}
		//打印出来，看看找出的最小的元素位置是否正确
		cout<<minPos<<endl;

找到最小元素位置了，就交换嘛，三步走，定义temp

int temp = arr[0];
arr[0] = arr[minPos];
arr[minPos] = temp;

以上，第一个元素的排序就完成了，也就是第一次遍历的过程。剩下的步骤，就是重复上述过程。

for(int i=0;i<length;i++){
//直接把上面的内容复制下来
int minPos = 0;

for (int j = 1; j < length; j++) {
			if (arr[j] < arr[minPos])
				minPos = j;
		}
		
int temp = arr[0];
arr[0] = arr[minPos];
arr[minPos] = temp;
}

做一点修改，上面只是针对第一个元素的嘛，把他改为针对整个数组。
首先

int minPos=i;//标记点minPos是不断变化的嘛，随着i,也就是第一个元素

其次，j的值也要随着移动嘛，每次都是移动“第一个元素”的下一个，也就是i+1

for (int j = i+1; j < length; j++) {
			if (arr[j] < arr[minPos])
				minPos = j;
		}

最后，交换。也就是把原来的arr[0]改为arr[i]。很简单吧

int temp = arr[i];
arr[i] = arr[minPos];
arr[minPos] = temp;

好了，现在就是一个完整的排序算法。

int main(){
int arr[] = { 5,3,6,8,1,7,9,4,2 };//先建立个无序数组
int length = sizeof(arr) / sizeof(arr[0]);

	for (int i = 0; i < length-1; i++) { //优化，不需要最后一次比较，-1
		int minp = i;//假设最小值的位置
		
		for (int j = i+1; j < length; j++) {
			/*if (arr[j] < arr[minp])
				minp = j;*/
			//合并语句 2变1.
			minp = arr[j] < arr[minp] ? j : minp;
		}
		//cout << minp << endl;
        //交换
		int temp = arr[i];
		arr[i] = arr[minp];
		arr[minp] = temp;
		}

排序算法优化

思路：查找最小值的同时，找到一个最大值，将最小值放到前面，最大值放到最后，这样可以减少循环次数，减少一半，但是时间复杂度还是O(n*2)。
先上代码，看增加改动了哪些

int main(){
int arr[] = { 6,2,3,7,1,4,5,8,0 };
int length = sizeof(arr) / sizeof(arr[0]);
	
	for (int i = 0; i < (length/2); i++) {
		int minPos = i;
		int maxPos = i;
		for (int j = i+1; j < length-i; j++) {
			if (arr[j] < arr[minPos])
				minPos = j;
			if (arr[j] > arr[maxPos])
				maxPos = j;
		}
		//cout << minPos << endl;
		//cout << maxPos << endl;
		//交换最小元素位置
		int temp = arr[i];
		arr[i] = arr[minPos];
		arr[minPos] = temp;

		if (i != maxPos) {
			int te = arr[maxPos];
			arr[maxPos] = arr[length - i - 1];
			arr[length - i - 1] = te;
		}
		else {
			int temp = arr[length - i - 1];
			arr[length - i - 1] = arr[minPos];
			arr[minPos] = temp;
		}
	}
	for (auto i : arr)
		cout << i << " ";
		}

第一个变化，只是在找最小元素位置时，顺便找到最大元素。没什么好讲的哈。

if (arr[j] > arr[maxPos])
		maxPos = j;

第二个变化，就是增加，交换最大值与最后元素的位置。注意两种情况：

1. 只需交换一次。当maxPos在“第一个元素”位置，minPos在“最后一个”元素位置，只需交换一次。不然，就又颠倒回去了嘛。
2. 不交换。当maxPos在“最后一个元素”位置，minPos在“第一个”元素位置，当然无需交换。

·针对第一种情况，当i与minPos元素交换后，现在i=maxPos，所以也就是minPos位置是最大元素，执行第二个交换，相当于自己与自己交换了。
·针对第二种情况，maxPos也相当于自己与自己交换了。
总之，当i不等于maxPos时，和待排序数组的末尾元素交换。
当i等于maxPos时，minPos元素和待排序数组的末尾元素交换。

if (i != maxPos) {
			int te = arr[maxPos];
			arr[maxPos] = arr[length - i - 1];
			arr[length - i - 1] = te;
		}
		else {
			int temp = arr[length - i - 1];
			arr[length - i - 1] = arr[minPos];
			arr[minPos] = temp;
		}

End.