【数据结构】——排序算法——1.1、直接插入排序

前端之家收集整理的这篇文章主要介绍了【数据结构】——排序算法——1.1、直接插入排序前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

插入算法很多,无论是在内功修炼,各种笔试面试都是相当有用的。接下来,将陆续将各种排序算法进行练习:@H_403_2@


@H_403_2@

主要分为以下几个部分(其他后面学习补充):@H_403_2@

@H_403_2@一、插入类排序:1、直接插入排序(折半插入排序)2、希尔shell排序3、二叉树排序;@H_403_2@

@H_403_2@二、交换类排序:1、冒泡排序 2、快速排序;@H_403_2@

@H_403_2@三、选择类排序:1、简单选择; 2、堆排序;@H_403_2@

四、归并排序

五、分配排序(箱排序、基数排序)@H_403_2@


@H_403_2@

所需辅助空间最多:@H_403_2@归并排序@H_403_2@

所需辅助空间最少:堆排序@H_403_2@

平均速度最快:快速排序@H_403_2@

不稳定:快速排序,希尔排序,堆排序
@H_403_2@

本人多使用Java——开始吧!@H_403_2@

首先推荐1、维基百科《排序算法》词条,图文并茂,很形象!2、学习博文《维基百科上的算法和数据结构链接很强大》,资料很多,保存学习!@H_403_2@


@H_403_2@
【数据结构】——排序算法——1.1、直接插入排序@H_403_2@

一、先上维基的图:@H_403_2@

@H_301_82@@H_403_2@

@H_301_82@图一、插入排序例子@H_403_2@

分类@H_403_2@ 排序算法
数据结构@H_403_2@ 数组
最差时间复杂度@H_403_2@ @H_403_2@
最优时间复杂度@H_403_2@ @H_403_2@
平均时间复杂度@H_403_2@ @H_403_2@
最差空间复杂度@H_403_2@ 总共,需要辅助空间
@H_403_2@

@H_403_2@
二、描述@H_403_2@
@H_403_2@很简单,类似打扑克牌时按从小到大排。每次派牌的人发一张,就拿上来整理一下。拿起新派的牌,第一件事,便是看牌的大小,然后从手里整理好的牌按从大到小(或者从小到大)的方向查询。当找到一个位置同时满足一边大于等于新牌、而另外一边小于等于新牌,那就将新牌插入这个位置。重复,最后牌就排好序了!@H_403_2@

@H_403_2@
三、Java程序@H_403_2@

@H_403_2@
@H_403_2@
public class Insertion {  
    public static void insertionSort(Comparable []data) {  
        for(int index = 1; index < data.length; index++) {  
            Comparable key = data[index];  
            int position = index;  
            //shift larger values to the right  
            while (position > 0 && data[position - 1].compareTo(key) > 0) {  
                data[position] = data[position - 1];  
                position--;  
            }  
            data[position] = key;  
        }     
    }  
    public static void main(String []args) {  
        Comparable []c = {4,9,23,1,45,27,5,2};  
        insertionSort(c);  
        for(int i = 0; i < c.length; i++)  
            System.out.println("插入排序:" + c[i]);  
    }  
}


@H_403_2@折半排序在直接插入排序的基础上做了少许改良,就是查找插入位置时不再是按照顺序逐个去查找,而是用折半式的方法不断缩小插入位置的范围。Java程序如下:@H_403_2@

@H_403_2@
@H_403_2@
public class BinaryInsertion {  
  
    public int[] binSort(int r[],int n) {  
          
        for(int i=1;i<n;i++)  
        {  
            int temp=r[i];  
            int low=0;  
            int high=i-1;  
              
            while(low<=high)  
            {  
                int mid=(low+high)/2;               //折半  
                if(temp<r[mid])high=mid-1;         //插入点在低半区  
                else low=mid+1;                      //插入点在高半区  
            }  
              
            System.out.println("low:"+low+" high:"+high);  
              
            for(int j=i-1;j>=high+1;j--)  
            {  
                r[j+1]=r[j];  
            }  
              
            r[high+1]=temp;  
        }  
          
        return r;  
    }  
  
    public static void main(String[] args) {  
        int[] test = { 844,52,13,8,55,97,33,777,87,6,1 };  
  
        test = new BinaryInsertion().binSort(test,test.length);  
  
        for (int i : test) {  
            System.out.print(i+" ");  
        }  
    }  
}  

猜你在找的数据结构相关文章