前言
旨在
在对dx和dy这类无穷小量的研究中，《微积分的历程》中指出
牛顿是这种动态方法的倡导者。
诚然，学习微积分的过程充满了形同“割之弥细，所失弥少”的思考。不仅如此，牛顿的弦截法和牛顿二项展开式充满了递归思想，而这种过程用动态形式展现最好不过。如果非要说我们有什么理念的话，那么我们一切旨在用简单和谐的动态过程描述算法。我先承诺会对弦截法和牛顿二项展开式进行描述。最后，用Python和C++实现。(如果Python有时间的话)。
选择排序(Selection Sort)
选择排序有着和冒泡排序一样简单的思路。
即每次遍历标记最小的数，然后与最前面的数交换。
只要进行n-1次遍历就可以完成排序。
注意，我们一般，选择排序每次挑出最小的数放在最前面，冒泡排序每次把最大的数放在最后面。两者也可以互换，只要你条理清晰即可。
选择排序与冒泡排序的区别
这里多扯两句。因为笔者曾把选择排序错写成冒泡排序。选择排序每次遍历完，只找到最小数的位置，然后交换。因为每次遍历仅交换一次，选择排序的交换次数仅为n-1，比冒泡排序少得多。(注意区分交换次数和比较次数)。因为交换次数少，所以选择排序要比冒泡排序快，但也引发了选择排序的不稳定问题。
简言之，冒泡排序与选择排序最大的区别在于寻找最小(最大)元素的方式不同。
选择排序的不稳定问题
这里直接举百度百科的例子
选择排序是不稳定的排序方法（比如序列[5， 5， 3]第一次就将第一个[5]与[3]交换，导致第一个5挪动到第二个5后面）。
因此要对此进行优化(笔者在一道题目里遇见的，才意识到问题，也算是见识浅薄了)，然而优化以后，效率也有损耗。我们时常用到快速排序，更快，然而也是不稳定的，在下一个博客，我们将会谈到。
选择排序的时间复杂度
选择排序的比较次数也是n(n-1)/2次。因此它的复杂度也是Ο(N²)。
选择排序的一个例子
我们依然输入一个数组，数组里有五个数[48 38 15 27 4]，我们对这五个数进行从小到大的排序。
一些说明
黄色表示每次循环最小的数将要交换的位置，一次是从1到5；
绿色显示遍历的情况；
temp指针(实际操作中我们也可以用一个数p来标记下标值)指向当前(即遍历过程)最小的元素位置，当遍历到末尾最后一个元素的时候temp所指即为最小数，temp指针随之变为黄色；
红色表示已经交换并且排好序的元素。
具体过程
第一次遍历
选择排序-step1.PNG
第二次遍历
选择排序-step2.PNG
第三次遍历
选择排序-step3.PNG
第四次遍历
选择排序-step4.PNG
等价的
等价.PNG
时间复杂度
选择排序的动态演示
这是一个选择排序的动态演示。
选择排序.gif
C++代码实现
//选择排序原理：每趟把最小的数放在第一位。（按从小到大顺序）
//注意为啥不把最大的数放在最后一位呢（也可以）
#include <iostream>
using namespace std;
int main()
{
int array[5];
for(int i = 0; i < 5; i++)
{
cin>> array[i];
}
for(int i = 0; i < 4; i++)
{
int p = i;
for(int j = i+1; j < 5; j++)//注意比较次数。
{
if(array[p] > array[j])
{
p = j;
}
}
if(p != i)
{
int exchange = array[p];
array[p] = array[i];
array[i] = exchange;
}
}
for(int i = 0; i < 5; i ++)
{
cout<< array[i]<<' ';
}
return 0;
}
写在后面
关于选择排序
快速排序见。
参考文献
wikipedia
《微积分的历程》
使用工具
visualgo(参考http://visualgo.net)
GifCam
网友评论