欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

java直接插入排序示例

程序员文章站 2024-03-31 13:42:40
影响排序效率的一般从3个方面比较:数据比较的次数,数据移动的次数,内存空间占用的大小。我们就冒泡排序、选择排序、插入排序、快速排序做一个总的比较。一般情况下不会使用冒泡排序...

影响排序效率的一般从3个方面比较:数据比较的次数,数据移动的次数,内存空间占用的大小。
我们就冒泡排序、选择排序、插入排序、快速排序做一个总的比较。一般情况下不会使用冒泡排序算法,因为它的比较次数和移动次数在几种排序算法中都是最多的,它的唯一好处是算法简单,易于理解,所以在数据量很小的时候它会有些应用价值。选择排序在比较次数上和冒泡排序一样,都是n的平方,但它把交换的次数降低到了最低,所以在数据量很小且交换数据相对于比较数据更加耗时的情况下,可以应用选择排序。
在大多数情况下,当数据量比较小或基本上有序时,插入排序算法是最好的选择。对于更大的数据量排序来说,快速排序通常是最好的方法。
上述排序算法在内存空间上占用很少,仅需要一个额外的变量来暂时存储交换时的数据项。所以在内存空间占用的大小上没有可比性。

插入排序的比较次数仍然是n的平方,但在一般情况下,它要比冒泡排序快一倍,比选择排序还要快一点。它常常被用在复杂排序算法的最后阶段,比如快速排序。

算法:经过i-1遍处理后,l[1..i-1]己排好序。第i遍处理仅将l[i]插入l[1..i-1]的适当位置,
使得l[1..i]又是排好序的序列。要达到这个目的,我们可以用顺序比较的方法。
首先比较l[i]和l[i-1],如果l[i-1]<=l[i],则l[1..i]已排好序,第i遍处理就结束了;
否则交换l[i]与l[i-1]的位置,继续比较l[i-1]和l[i-2],直到找到某一个位置j(1≤j≤i-1),
使得l[j] ≤l[j+1]时为止
优点:移动元素次数少,只需要一个辅助空间
时间复杂度n*n
当待排序记录的数量n很小时,这是一种很好的排序方法。但是n很大时,则不适

例如:int[] values = { 5, 2, 4, 1, 3 };

排序过程:
第1次:2,5,4,1,3
第2次:2,4,5,1,3
第3次:1,2,4,5,3
第4次:1,2,3,4,5


java代码:

复制代码 代码如下:

public class insertsort {
   public static void main(string[] args) {
       int[] values = { 5, 2, 4, 1, 3 };
       sort(values);
       for (int i = 0; i < values.length; ++i) {
           system.out.println(values[i]);
       }
   }
   public static void sort(int[] values) {
       int temp;
       int j = 0;
       for (int i = 1; i < values.length; i++) {
           if(values[i]<values[i-1])//此处的判断很重要,这里体现了插入排序比冒泡排序和选择排序快的原因。
           {
               temp = values[i];
               //数据往后移动
               for (j=i-1; j>=0 && temp<values[j]; j--)
               {
                   values[j+1] =values[j];
               }
               //将数据插入到j+1位置
               values[j+1] =temp;
               system.out.print("第" + (i + 1) + "次:");
               for (int k = 0; k < values.length; k++) {
                   system.out.print(values[k]+",");
               }
               system.out.println("");
           }
       }
   }
}

第二个示例

复制代码 代码如下:

package cn.cqu.coce.xutao;

public class zhijiecharu {

 public static void main(string args[]){

 int a[]={1,2,34,67,8,9,6,7,56,34,232,99};
 int i,j,k;
 for(i=0;i<a.length;i++)
  system.out.print(a[i]+"\t");
 system.out.println();
 for(i=1;i<a.length;i++){

  for(j=i-1;j>=0;j--)
   if(a[i]>a[j])
    break;

  if(j!=i-1){
   int temp;
   temp=a[i];
   for(k=i-1;k>j;k--)
    a[k+1]=a[k];
   a[k+1]=temp;  
  }  
 }
 for(i=0;i<a.length;i++)
  system.out.print(a[i]+"\t");
 system.out.println();
  }
}



java直接插入排序示例