基本的排序算法原理与实现
最后更新于：2022-04-01 21:40:36
### 引言
本节主要介绍基本的排序算法原理与实现 ，即：插入排序，选择排序，冒泡排序.
### 插入排序算法
#### 基本思想
插入排序首先考虑data中的前两个元素，即data[0]和data[1]。如果它们的次序颠倒了，就交换它们。然后，考虑第三个元素data[2],将其插入到合适的位置上。如果data[2]同时小于data[0]和data[1],那么data[0]和data[1]都要移动一个位置；data[0]放在位置1上，data[1]放在位置2上，而将data[2]放在位置0上。如果data[2]小于data[1]，而不于data[0],那么只须把data[1]移动到位置2上，并由data[2]占据它的位置。最后，如果data[2]不小于前两个元素，它将保留在当前的位置。每一个元素data[i]都要插入到合适的位置j上，使0<=j<=i,所有比data[i]大的元素都要移动一个位置。
插入排序算法的要点如下：
~~~
insertionsort(data[],n){
for(i=1; i void insertionsort(T data[], int n)
{
for(int i =1, j; i0&&tmp< data[j-1]; j--)
data[j] = data[j-1];
data[j] =tmp;
}
}
~~~
插入排序的一个优点是只有需要时才对数组排序。如果数组已经排好序了，就不再对数组进行移动；只有变量tmp得到初始化，存储在变量中的值返回值原位置。可以识别出已排序的数组部分，并相应停止，但忽视元素可以已在合适位置上的事实。一个缺点是：如果插入数据项，所有比插入元素大的元素都必须移动。插入操作不是局部的，可能需要移动大量的元素。其中，在博文[【编程珠玑】插入排序](http://blog.csdn.net/songzitea/article/details/8761722)中，介绍了关于插入排序优化代码。
#### 算法分析
为了获取insertionsort()算法执行的移动和比较次数，首先要注意，外层的for语句执行n-1次。但是，比data[i]大的元素移动一个位置的次数并不总是相同的。
**最好的情况是**：数据已排好序。对于每个位置i,只需比较一匀，这样就只需进行n-1次比较(其数量级是o(n))和2(n-1)次移动，所有的移动和比较都是多余的。**最坏的情况是：**数据按相反顺序排序。在这种情况下，对于外层for的每次迭代i,都比较i次，即所有迭代的比较总数是
内层for中的赋值次数可以用相同的公式计算。把tmp在外层for中加载和卸载的次数加起来，得到总的移动次数：
前面我们只考虑了极端情况。如果数据是随机排序的，结果如何呢？假设数据项占用数组单元的概率相等，在外层for的迭代i中，data[i]与其它元素的平均比较次数计算如下：
为了求得所有比较次数的平均值，对于所有的迭代i来说，都必须从1开始一直累加到n-1为止。结果是
它的时间复杂度是O(n^2),大约是最坏情况下的比较次数的1/2。按照相同的方式，可以确定在外层for的迭代i中，data[i]需要移动0,1,..i-1次：即
次，加上一定分会发生的两次移动。因此，在外层for中所有迭代中，平均移动次数为
其中时间复杂度为O(n^2)。
综上所述，对于随机顺序的数组来说，移动和比较的次数是与最好情况接近，还是与最坏情况接近？遗憾的是，它接近于后者，即：当数组的元素加倍时，平均需要付出4倍的努力来排序。
#### 测试输出结果
### 选择排序算法
#### 基本思想
选择排序先找到时位置不合适的元素，再把它放在其最终的合适位置上，它试图仅在本地交换数组元素。基本思想是：先找出数组中的最小元素，将其与第一个位置上的元素进行交换。然后在剩余元素data[1],...,data[i-1]中找到最小元素，把它放到第二个位置上。这种选择和定位的方法是：在每次迭代中，找出元素data[i],....data[n-1]中的最小元素，然后将其与data[i]交换位置，直到所有的元素都放到了合适位置为止。
如下的伪代码反映出选择排序算法的简单性：
~~~
selectionsort(data[] ,n)
for i =0 到n-2
找出元素data[i]....data[n-1]中的最小元素；
将其与data[i]交换；
~~~
很明显，n-2是最后一个i值，因为寻如果除最后一个元素之外的所有元素都放在合适的位置上，那么第n个元素就是一定是最大的。下面提选择排序的C++代码：
~~~
template void selectionsort (genType data[], int n)
{
int j,least;
for(int i =0; ii;--j)
如果两者逆序，交换位置j和j-1的元素
~~~
下面是冒泡排序的实现：
~~~
template void bubblesort( genType data[], int n)
{
for( int i =0; ii;--j){
if(data[j]
';