直接插入排序/二分插入排序/希尔排序

2020-12-13 16:27

阅读：550

标签：直接 shellSort 数组 class 插入排序 swap nbsp || public

---恢复内容开始---

插入排序是在源数据已经有序的情况下进行排序。时间复杂度O(N^2)，稳定的

直接插入排序

代码如下

public static int[] insertSort(int [] a){
if(a==null||a.length==0){
return a;}
for(int i=1;i){

for(int j=i-1;j>=0&&a[j]>a[j+1];j--)
  swap(a,j,j+1);//满足前一个大于后一个才进行交换
}
return a;

}

二分插入前提也是原数组是有序的

public static int[] subInser(int a[]) {
        for (int i = 1; i ) {
            int temp = a[i];
            int low = 0, high = i - 1;
            int mid = -1;
            while (low  high) {
                mid = low + (high - low) / 2;
                if (a[mid] > temp) {
                    high = mid - 1;
                } else { // 元素相同时，也插入在后面的位置                
                    low = mid + 1;
                }
            }
            for (int j = i - 1; j >= low; j--) {
                a[j + 1] = a[j];
            }
            a[low] = temp;
        }
        return a;
    }

希尔排序

不再是固定的二分，分段数d在不断的缩小，直到为1

 1  public static int[] shellsort(int [] a){
 2         int d=a.length/2;
 3         int tmp;
 4         while(d>0){
 5             for(int i=d;i){
 6                 tmp=a[i];
 7                 int j=i;
 8                 while(j>d&&tmpd]){
 9                     a[j]=a[j-d];
10                     j-=d;
11                 }
12                 a[j]=tmp;
13             }
14             d=d/2;
15         }
16      return  a;
17     }

直接插入排序/二分插入排序/希尔排序

标签：直接 shellSort 数组 class 插入排序 swap nbsp || public

原文地址：https://www.cnblogs.com/bowenqianngzhibushiwo/p/11619895.html

上一篇：P1908 逆序对-（树状数组）

下一篇：Windows下OpenCV的环境配置

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：直接插入排序/二分插入排序/希尔排序
文章链接：http://soscw.com/essay/36164.html

亲，登录后才可以留言！

直接插入排序/二分插入排序/希尔排序

评论

热门文章

推荐文章

最新文章

置顶文章