算法分析（3）-简单排序总结（选择，插入，希尔含图解）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法分析（3）-简单排序总结（选择，插入，希尔含图解），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含7790字，纯文字阅读大概需要12分钟。
内容图文
@[TOC]( )
# 1.前言
排序算法的实用意义还是很高的，可应用在商业处理，语音识别，天体物理学等领域。本文对简单排序（选择排序，插入排序，希尔排序）的几个模型做一些总结。
# 2.排序成本模型
- 分析排序过程，主要是对比较和元素交换使用的次数进行分析，可以使用比较和交换的次数作为成本；
- 当然不使用交换元素的算法可以通过统计访问次数来规定算法成本。
# 3.Comparable接口
遵循Java的规范，可以使用Comparable接口强行对实现它的类的每个实例进行自然排序。当然使用其他语言可以不需要遵循这个规范使用Comparable可以很好的执行less()对元素进行比较和exch()完成元素的交换。
方法：int compareTo（Object o）
利用当前对象和传入的目标对象进行比较，
1. 若是当前对象比目标对象大，则返回1，那么当前对象会排在目标对象的后面；
2. 若是当前对象比目标对象小，则返回-1，那么当前对象会排在目标对象的后面若是两个对象相等，则返回0
Comparable接口强行对实现它的类的每个实例进行自然排序，该接口的唯一方法compareTo方法被称为自然比较方法；强烈建议自然排序和equals一致（就是两个对象调用compareTo方法和调用equals方法返回的布尔值应该一样）。
<font color=red>**在这里对一些调用做一些说明算法说明:**</font>
```java
//交换元素
private static void exch(Comparable[] a,int i,int j)
{
Comparable t=a[i];a[i]=a[j];a[j]=t;
}
//比较
private static boolean less(Comparable[] v,Comparable[] w)
{
return v.compareTo(w)<0;
}
```
# 4排序算法
## 4.1 选择排序
选择排序是最简单的一类排序（简言之就是从数组中选择最小或者最大的元素进行排序）：
1. 首先找到数据中最小（最大）的元素；
2. 将元素与数组第一个元素交换位置；
3. 在剩下的元素中找到最小（最大）的元素将其与第二个元素交换位置，
.........
重复以上步骤，直到将整个数组排序完成。
```java
public class Selection
{ //将a[]按升序排列
public static void sort(Comparable[] a)
{
int N=a.length;
//内循环进行比较以及交换
for(int i=0;i<N;i++)
{
int min=i;
for(int j=i+1;j<N;j++)
{
if(less(a[j]),a[min])
min=j;
exch(a,i,min);
}
}
}
}
```
<font color=redblue>成本分析:</font>
- 对于长度为N的数组选择排序一般要进行$N^{2}/2$次比较（从$0$到$N-1$要比较$(N-1)+(N-2)+...+2+1$~$N^{2}/2$次）
- 交换次数会造成$N$次。
<font color=red>**选择排序特点总结**</font>
<font color=yellowr>
1.运行时间与输入无关
内循环循环结束之后都不会对下一组循环造成影响，也就是为了找到当前最小元素而扫描一遍数组并不能为下一遍扫描提供什么信息。
这样对一个有序数组和元素全部相等的数组和一个元素进行排序所用时间相同。
2. 数据移动是最少的
交换数据的次数与数组大小是线性关系。（其他大部分算法都是线性对数或者平方级别）
</font>
## 4.2 插入排序
### 4.2.1 插入排序算法描述
插入排序的执行过程如下：
每一步将一个待排序的数据插入到前面已经排好序的有序序列中，直到插完所有元素为止。执行示例如下：
```java
public class Insertion
{
public static void sort(Comparable[] a)
{
//将a[]按升序排列
int N=a.length;
for (int i=1;i<N;i++)
{//执行插入过程判断条件满足两个要求：
// 1.遍历完当前元素左侧所有元素
//2.前一个元素大于当前元素（类似冒泡后续会展开）
for(int j=i;j>0&&less(a[j],a[j-1]);j--)
{
exch(a,j,j-1);
}
}
}
}
```
<font color=yellowr>在这里对插入排序的运行规模做一个总结：
具有N个元素的随机排列（元素不重复），平均情况下需要$N^{2}/4$次比较，$N^{2}/4$次交换。
（最坏情况下有$N^{2}/2$次比较，$N^{2}/2$次交换，最好情况下需要$N-1$次比较与$0$次交换）。</font>
<font color=red>这里注意一点插入排序会受输入的数组影响。
例如：如果输入的数组是有序的，这时候插入一个元素能够很容易找到需要插入的位置，这时运行时间是线性的（对于选择排序是平方级别的）
<font color=greenyellow>与选择排序相比：</font>
- 与选择排序相同的是当前元素左边所有元素都是有序的，但是元素插入的最终位置并不确定，为了给更小的元素腾出空间，会对元素进行移动，当需要进行排序的元素到达最右端后，数组排序就完成了。
- 与选择排序不相同之处是：插入排序的运行时间会受输入元素的初始顺序影响。对于一个规模较大且已经部分有序的元素序列处理效果会好许多。
### <font color=red>4.2.2 插入排序总结(不理解部分有序的读者看这里)</font>
- 插入排序对部分有序的数组十分高效，这里的部分有序可以理解为数组中已有元素的相对位置不需要再进行 排序。
例如：
4 2 1 5 8 9
这一串数字中“2”在“5”“8”“9”之前，这样能够保证2589这一串数字是正序的，我们实际上要“拨乱反正”的有序数是“421”这串数组
- 这里扩展部分有序的理解与定义，如果数组中倒置（数组中两个顺序颠倒的元素，可以参考线代的反序数理解）的数量小于数组大小的某个倍数就可称其为部分有序。其实很简单
例如：123645
其中其中倒置的有“64”，“65”两组，明显小于6（1倍），可以称其为部分有序
<font color=red>可以归纳一下常见的部分有序数组：</font>
1. 数组中每个元素距离它应该存在的位置并不远（如21354）
2. 一个有序的大数组接一个小数组（如：abcdefghiwvu）
3. 数组中只有几个元素位置不正确（这个很简单啦）
这里给出一个有关倒置的推论(读者理解交换即可)
<font color=bkue>插入排序需要的交换操作和数组中倒置的数量相同，需要比较的次数大于等于倒置的数量。小于等于数组的数量加上倒置的数量减一</font>
<font color=blackw>其实不难理解,<font color=red>交换的目的就是消除倒置(敲重点啦！！)</font>每个元素回到应有的顺序就消除一个倒置，倒置数量为0时也就相当于排序完成。
但是1~N-1每个i元素都可能有多一次比较因为当前元素还没有到达对应的位置（左端）。</font>
## 4.3希尔排序
希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序其实也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破$N^{2}$的第一批算法之一。
希尔排序的思想其实是一种<font color=red>分组插入的方法</font>
希尔排序的目标是<font color=redb>使数组中间任意间隔h的元素有序。</font>其中每隔h的元素组成h有序数组。<font color=redb>一个h有序数组就是由h个有序子数列组成的数组</font>
<font color=green>例如：</font>
*一个长度为16的数组，h=4时如下图：*
上图中每隔4个元素分组，每个分组由4个元素构成，一个4-有序数组
*一个长度为16的数组，h=5时如下图：*
上图中每隔5个元素分组，一个5-有序数组
### 4.3.1 希尔排序图解与代码
为了方便读者理解，以下给出希尔排序的图解，如下（可以单击放大查看）：
代码如下，
```java
public class Shell
{
public static void sort(Comparable[] a)
{
int N=a.length;
int h=N/2;
while(h>=1)
{
//获取h的长度，首先从N/2开始
for (int i=h;i<N;i++)
{
//对各个分组进行插入排序
for(int j=i;j>=0&&less(a[j],a[j-h]);j-=h)
{
exch(a,j,j-h);//用法见本章接口说明
}
}
h=h/2;
}
}
}
```
### 4.3.2 分析
希尔排序的复杂度和递增序列是相关的，算法的性能不仅仅取决于h，还取决于h之间的数学性质，比如分组为（4，2，1）或者分组为（9，3，1）。所以很难去描述其对乱序的数组性能特征的排序方法。<font color=red>针对不同的递增序列序列会有不同的时间复杂度。</font>
- {1,2,4,8,...}这种序列并不是很好的递增序列，使用这个增量序列的时间复杂度（最坏情形）是$N^{2}$
- Hibbard提出了另一个递增序列{1,3,7，...,$2^{k}-1$}，这种序列的时间复杂度(最坏情形)为$N^{3/2}$
- Sedgewick提出了几种递增序列，其最坏情形运行时间为$N^{1.3}$,其中最好的一个序列是{1,5,19,41,109,...}
<font color=blue>希尔排序对中等大小的数组还是具有很好的性能的，代码量小，并且不需要额外空间。对于不要求极端的运行环境情况下是一个不错的选择。</font>
内容总结
以上是互联网集市为您收集整理的算法分析（3）-简单排序总结（选择，插入，希尔含图解）全部内容，希望文章能够帮你解决算法分析（3）-简单排序总结（选择，插入，希尔含图解）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。