1.前言

排序算法的实用意义还是很高的，可应用在商业处理，语音识别，天体物理学等领域。本文对简单排序（选择排序，插入排序，希尔排序）的几个模型做一些总结。

2.排序成本模型

• 分析排序过程，主要是对比较和元素交换使用的次数进行分析，可以使用比较和交换的次数作为成本；
• 当然不使用交换元素的算法可以通过统计访问次数来规定算法成本。

3.Comparable接口

遵循Java的规范，可以使用Comparable接口强行对实现它的类的每个实例进行自然排序。当然使用其他语言可以不需要遵循这个规范使用Comparable可以很好的执行less()对元素进行比较和exch()完成元素的交换。
方法：int compareTo（Object o）
利用当前对象和传入的目标对象进行比较，

1. 若是当前对象比目标对象大，则返回1，那么当前对象会排在目标对象的后面；
2. 若是当前对象比目标对象小，则返回-1，那么当前对象会排在目标对象的后面若是两个对象相等，则返回0

Comparable接口强行对实现它的类的每个实例进行自然排序，该接口的唯一方法compareTo方法被称为自然比较方法；强烈建议自然排序和equals一致（就是两个对象调用compareTo方法和调用equals方法返回的布尔值应该一样）。
在这里对一些调用做一些说明算法说明:

//交换元素
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. 在剩下的元素中找到最小（最大）的元素将其与第二个元素交换位置，
   .........
   重复以上步骤，直到将整个数组排序完成。

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);
                 }
             }
         }
     }

成本分析:

• 对于长度为N的数组选择排序一般要进行$N^{{2}/2$次比较（从$0$到$N-1$要比较$(N-1)+(N-2)+...+2+1$~$N}{2}/2$次）
• 交换次数会造成$N$次。

选择排序特点总结

1.运行时间与输入无关
内循环循环结束之后都不会对下一组循环造成影响，也就是为了找到当前最小元素而扫描一遍数组并不能为下一遍扫描提供什么信息。
这样对一个有序数组和元素全部相等的数组和一个元素进行排序所用时间相同。
2. 数据移动是最少的
交换数据的次数与数组大小是线性关系。（其他大部分算法都是线性对数或者平方级别）

4.2 插入排序

4.2.1 插入排序算法描述

插入排序的执行过程如下：
每一步将一个待排序的数据插入到前面已经排好序的有序序列中，直到插完所有元素为止。执行示例如下：

 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);
             }
         }
     }
 }

在这里对插入排序的运行规模做一个总结：
具有N个元素的随机排列（元素不重复），平均情况下需要$N^{{2}/4$次比较，$N}{2}/4$次交换。
（最坏情况下有$N^{{2}/2$次比较，$N}{2}/2$次交换，最好情况下需要$N-1$次比较与$0$次交换）。
这里注意一点插入排序会受输入的数组影响。
例如：如果输入的数组是有序的，这时候插入一个元素能够很容易找到需要插入的位置，这时运行时间是线性的（对于选择排序是平方级别的）

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;
        }
    }
}

算法分析（3）-简单排序总结（选择，插入，希尔含图解）

原文：https://www.cnblogs.com/suanfawu/p/14442232.html