一篇讲透排序算法之插入排序and选择排序

1.插入排序

1.1算法思想

先将数组的第一个元素当作有序，让其后一个元素与其比较，如果比第一个元素小则互换位置，之后再将前两个元素当作有序的，让第三个元素与前两个元素倒着依次进行比较，如果第三个元素比第二个元素小的话，则交换位置，之后再比较第二个元素和第一个元素。

之后我们重复以上操作即可完成插入排序。

为了帮助大家理解，现在我们一步步完成这些操作。

1.2实现逻辑以及具体实现

首先，如果第二个元素小于第一个元素，则交换位置。

	if (a[1] < a[0]){int tmp = a[1];a[1] = a[0];a[0] = tmp;}

之后，我们就可以让第三个元素依次与前两个元素进行比较了。

在这里，我们要记录一下第二个元素的位置，否则我们不知道如何比较。

因此我们在这里定义一个end来记录第二个元素的位置。

int end = 1;
while (end)
{//如果第三个元素和第二个元素发生了交换//则比较第一个元素和新的第二个元素if (a[end + 1] < a[end]){int tmp = a[end + 1];a[end + 1] = a[end];a[end] = tmp;}//由于前end个元素已经有序，所以有一次没有进if就可以跳出循环了else{break;}end--;
}

现在我们就完成了单趟的循环，但我们需要比较多趟，而每趟的比较中不一样的变量就是end，每趟的比较end都会+1，因此我们在外层再写一个循环即可。

	for (int i = 0; i < n-1; i++){int end = i;while (end >= 0){if (tmp < a[end]){int tmp = a[end + 1];a[end + 1] = a[end];end--;}else{break;}}a[end + 1] = tmp;}

到这里我们已经完成了一次插入排序，最后我们只需要将这些内容放在函数定义当中即可彻底完成！

void InsertSort(int* a, int n)
{for (int i = 0; i < n-1; i++){int end = i;while (end >= 0){if (tmp < a[end]){int tmp = a[end + 1];a[end + 1] = a[end];end--;}else{break;}}a[end + 1] = tmp;}
}

2.选择排序

2.1算法思想

先遍历一遍数组，找出最小的元素，然后与第一个元素交换位置。

之后从数组的第二个数开始，再遍历一遍数组，找出此次遍历中最小的数，与第二个数交换位置。

之后重复以上的操作即可完成任务。

使用上述的原理遍历数组，每次遍历都可以选出一个最小的数，放到对应的位置上面去。

2.2实现逻辑以及具体实现

现在我们来逐步实现这个排序算法

首先，我们应遍历数组，找出最小的元素。

int min=a[0];
for (int i = 0; i < n; i++)
{if (a[i] < min){int tmp = min;min = a[i];a[i] = tmp;}
}

我们这样写出现了一个问题，我们交换了min和a[i]的数值，但是a[0]处的数值并没有随着min的改变而改变，对此，我们应该怎么做呢？

这里我们可以将两数交换封装为一个函数，之后我们不再让min记录数值，而是记录下标即可。 

//假设最小的是下标为0处的元素
int min = 0;
for (int i = 0; i < n; i++)
{if (a[i] < a[min]){//交换下标，每次交换后，min中记录的则是较小数的下标//之后进入下一次循环，继续比较min = i;}
}
//比较完毕之后，交换数值即可
swap(&arr[min], &arr[0]);//这个函数自己写，我没贴上来。

现在我们已经找到了最小的数，而且已经将其放到了第一个位置上去。

现在我们只需要在外面再套一层循环，每次不断更新下标，即可完成选择排序。

for (int i = 0; i <n-1; i++)//一共需要比较n-1趟
{//此时i下标元素最小int min = i;for (int j = i+1; j < n; j++)//前i个有序，因此j=i+1,比较n个元素，因此j<n{//假设最小的是下标为j处的元素if (a[j] < a[min]){//交换下标，每次交换后，min中记录的则是较小数的下标//之后进入下一次循环，继续比较min = j;}}//比较完毕之后，交换数值即可swap(&arr[min], &arr[0]);
}

 我们将其封装在函数体内，即可完成一次排序。

void SelectSort(int* arr, int len)
{for (int i = 0; i < len - 1; i++){int min = i;for (int j = i + 1; j < len; j++){if (arr[j] < arr[min]){mini = j;}}swap(&arr[min], &arr[i]);}
}

2.3选择排序的优化

我们的选择排序还可以进行一下优化，我们可以一次循环同时找最小和最大的数据，只需要在每次比较时定义一个min，一个max，即可在一次循环中找到最小和最大的数据。

这里我们还是先完成第一趟排序，代码如下

int max = 0;
int min = 0;
for (int j =1; j < n; j++)//前i个有序，因此j=i+1,比较n个元素，因此j《n
{//假设最小的是下标为j处的元素if (a[j] < a[min]){//交换下标，每次交换后，min中记录的则是较小数的下标min = j;}if (a[j] > a[max]){//交换下标，每次交换后，min中记录的则是较大数的下标max = j;}
}
swap(&arr[min], &arr[0]);
swap(&arr[max], &arr[n-1]);

通过上面这段代码，我相信大家可以了解优化的原理了。

现在我们就可以着手于完成优化后的选择排序了。

由于我们在一个循环体内同时寻找最小值和最大值，并交换位置。

因此我们需要两个变量记录每次循环中最左边的值和最右边的值的下标，我们将其定义为begin和end。

当begin和end相遇时，我们的循环就结束了。这时我们的数组就有序了。

当begin>=end时，她们就有序了。因此我们的循环条件可以写为begin<end。

void SelectSort(int* arr, int len)
{int begin = 0;int end = len - 1;while (begin < end){//假设mini和maxi都是beginint mini = begin;int maxi = begin;for (int i = begin + 1; i <= end; i++){//找大if (arr[mini] > arr[i]){mini = i;}//找小if (arr[maxi] < arr[i]){maxi = i;}}swap(&arr[mini], &arr[begin]);swap(&arr[maxi], &arr[end]);begin++;end--;}}
}

到了这里，我们的选择排序已经基本完成了，

但是请大家思考一个问题： 

如果我们的begin和maxi重合的话，上面这段代码的执行逻辑是什么样的呢？

    如果begin和maxi重合，根据我们的代码逻辑，我们首先会交换mini和begin位置处的值。

此时我们的begin下标处的值已经更新成了mini处的值，而由于我们的maxi和begin是相同的，因此此时我们maxi下标处的值其实是mini处的值。

    文字表述可能比较抽象，我们现在将文字具象化为代码。

		swap(&arr[mini], &arr[begin]);swap(&arr[begin], &arr[end]);

那么应该怎么解决这个问题呢？很简单，因为我们的下标重合了，因此我们在进行完第一个交换之后更新一下maxi的值即可。

void SelectSort(int* arr, int len)
{int begin = 0;int end = len - 1;while (begin < end){//假设mini和maxi都是beginint mini = begin;int maxi = begin;for (int i = begin + 1; i <= end; i++){//找大if (arr[mini] > arr[i]){mini = i;}//找小if (arr[maxi] < arr[i]){maxi = i;}}swap(&arr[mini], &arr[begin]);//begin处的值和mini处的值交换了位置//因此现在mini处保存的值为最大值//我们将maxi更新为mini即可。if (begin == maxi){maxi = mini;}swap(&arr[maxi], &arr[end]);begin++;end--;}}
}