直接插入排序(java与js版)

短命女 2022-09-22 13:57 26阅读 0赞

插入排序简单来说，就是重新去遍历一组数据，然后在遍历的时候，拿正在遍历的数据和已经遍历过的数据去对比，最后按照某种特定的顺序去排序；

举个简单的例子，大家都玩过斗地主吧，我们把桌子上的牌看成是一个杂乱无序的数组；在我们斗地主的时候，我们会拿刚起的牌和手中的牌进行比较，然后把它插入到指定的位置。这就是我们的插入排序；

![Center][]

输入：n个数的一个序列<a₁,a₂,...,an>。

输出:输出的结果要满足排序后的结果;

public static void main(String[] args) {
    		int[] a = { 90, 34, 5, 7, 71, 2};
    		insertSort1(a, a.length);
    	}
    
    	public static void insertSort1(int a[], int num) {
    		for (int i = 1; i < num; i++) {
    			int temp=a[i];  //复制为哨兵进行对比
    			int j=i-1;
    			while(j>=0&&temp<a[j]){
    				a[j+1]=a[j]; //如果要对比的数大于当前数则后移一位
    				j--;  
    			}
    			a[j+1]=temp; 
    			print(a);
    		}
    	}
    	public static void print(int a[]){
    		for (int i = 0; i < a.length; i++) {
    			if(i%6==0){
    				System.out.println();
    			}
    			System.out.print(a[i]+"  ");
    		}
    	}

再来个JS版本的

下面再贴上一副自己画的图， 可能不是很正确，但是帮助了自己的理解

![Center 1][]

算法适用于少量数据的排序， [时间复杂度][Link 1]为O(n^2)。是稳定的排序方法。插入算法把要排序的 [数组][Link 2]分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。

插入排序的基本思想是：每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。

直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的纪录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的纪录插入完为止，得到一个新的有序序列

例如，已知待排序的一组数据是：90, 34, 5, 7, 71, 2

这里我们把90作为一个哨兵，然后插入34的时候，到while循环里面去找到34的插入位置；再进行插入。假设在排序过程中前三个已按关键码值递增的次序重新排序，构成一个有序序列:

5,34,90

将待排序的第四个记录7插入上述序列中。首先找到7的插入位置。我们可以将7放入到数组的第一个单元r\[0\]中。然后从90右起对比查找，7小于90,将90右移，这时再讲7与r\[0\]进行对比，7>=r\[0\]，它插入的位置就是r\[1\].

直接插入排序的算法思路：

（1） 设置监视哨r\[0\]，将待插入纪录的值赋值给r\[0\]；

（2） 设置开始查找的位置j；

（3） 在数组中进行搜索，搜索中将第j个纪录后移，直至r\[0\].key≥r\[j\].key为止；

（4） 将r\[0\]插入r\[j+1\]的位置上。

[Center]: /images/20220721/c69655f10d2847f296077395d77f23c2.png
[Center 1]: /images/20220721/0cd2434d22bc44ae9a4af0d0ab405983.png
[Link 1]: http://baike.baidu.com/view/104946.htm
[Link 2]: http://baike.baidu.com/view/209670.htm