排序算法总结(一)---- 直接插入排序，希尔排序（java实现）

不念不忘少年蓝@ 2022-07-03 12:29 151阅读 0赞

### 一、概述 ###

排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。

![SouthEast][]

###  二、**稳定性，时间复杂度和空间复杂度总结** ###

![SouthEast 1][]

**选择排序算法准则：**

**1、**当n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序序。

快速排序：是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；  
       堆排序 ： 如果内存空间允许且要求稳定性的，

归并排序：它有一定数量的数据移动，所以我们可能过与插入排序组合，先获得一定长度的序列，然后再合并，在效率上将有所提高。

**2、**当n较大，内存空间允许，且要求稳定性，优先归并排序

**3、**当n较小，可采用直接插入或直接选择排序。

直接插入排序：当元素分布有序，直接插入排序将大大减少比较次数和移动记录的次数。

直接选择排序 ：元素分布有序，如果不要求稳定性，选择直接选择排序

**4、**一般不使用或不直接使用传统的冒泡排序。

**5、**基数排序  
它是一种稳定的排序算法，但有一定的局限性：  
　　1、关键字可分解。  
　　2、记录的关键字位数较少，如果密集更好  
　　3、如果是数字时，最好是无符号的，否则将增加相应的映射复杂度，可先将其正负分开排序。

**稳定性：**

排序算法的稳定性:若待排序的序列中，存在多个具有相同关键字的记录，经过排序，这些记录的相对次序保持不变，则称该算法是稳定的；若经排序后，记录的相对次序发生了改变，则称该算法是不稳定的。   
      稳定性的好处：排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。基数排序就是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。另外，如果排序算法稳定，可以避免多余的比较；

稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。

不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。

### 三、算法实现 ###

#### 1、**直接插入排序** ####

（1）基本思想：在要排序的一组数中，假设前面(n-1) \[n>=2\] 个数已经是排

好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数

也是排好顺序的。如此反复循环，直到全部排好顺序。

（2）图解

![SouthEast 2][]

（3）用java实现

public void insertSort(){  
      
        int a[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17,18,23,34,15,35,25,53,51};  
        int temp=0;  
      
        for(int i=1;i<a.length;i++){  
      
           int j=i-1;  
           temp=a[i];  
      
           for(;j>=0&&temp<a[j];j--){  
      
           a[j+1]=a[j];                       //将大于temp的值整体后移一个单位  
      
           }  
           a[j+1]=temp;  
      
        }  
      
        for(int i=0;i<a.length;i++)  
      
           System.out.println(a[i]);  
      
    }

#### **2，  希尔排序（最小增量排序）** ####

（1）基本思想：[**算法**][Link 1]先将要排序的一组数按某个增量d（n/2,n为要排序数的个数）分成若干组，每组中记录的下标相差d.对每组中全部元素进行直接插入排序，然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。当增量减到1时，进行直接插入排序后，排序完成。

（2）图解：

![SouthEast 3][]

（3）用java实现

public void shellSort(){  
      
        int a[]={1,54,6,3,78,34,12,45,56,100};  
        double d1=a.length;  
        int temp=0;  
      
        while(true){  
      
           d1= Math.ceil(d1/2);  
      
           int d=(int) d1;  
      
           for(int x=0;x<d;x++){  
      
               for(int i=x+d;i<a.length;i+=d){  
      
                  int j=i-d;  
      
                  temp=a[i];  
      
                  for(;j>=0&&temp<a[j];j-=d){  
      
                  a[j+d]=a[j];  
      
                  }  
      
                  a[j+d]=temp;  
      
               }  
           }  
      
           if(d==1)  
      
               break;  
      
        }  
      
        for(int i=0;i<a.length;i++)  
      
           System.out.println(a[i]);  
      
    }

下一篇：[排序算法总结(二)-------选择，堆，冒泡，快速，归并排序（java实现）][-------_java]

[SouthEast]: /images/20220618/8b4b744f541c4862bc7e7bd5cfdd3b4b.png
[SouthEast 1]: /images/20220618/0acb95a47c204d38a0994ba33c020ca0.png
[SouthEast 2]: /images/20220618/d46a778122894c2d88ebd841e6de3eb5.png
[Link 1]: http://lib.csdn.net/base/datastructure
[SouthEast 3]: /images/20220618/f73486068fbc4487b244d441f57d873e.png
[-------_java]: http://blog.csdn.net/ljheee/article/details/69676924