黑马程序员技术交流社区

标题: 关于排序问题 [打印本页]
作者: 刘建龙    时间: 2012-7-25 09:43
标题: 关于排序问题
听毕老师的视频的时候，发现除了，选择排序，冒泡排序，还有一个插入排序。小弟在这里请教插入排序的代码，以及原理。请知道的同学，讲解一下
作者: 吴立杰    时间: 2012-7-25 09:56
插入排序的原理是：每次比较时记录元素角标的位置，从而减少了每次交换位置的次数，提供了效率，代码如下：
  1. class Demo
  2. {
  3.         public static void main(String[] args)
  4.         {
  5.                 int[] arr ={1,5,2,32,11,323,4,8,6};
  6.                 sort(arr);
  7.                 print(arr);
  8.         }

  10.         public static void sort(int[] arr)
  11.         {
  12.                 for (int i = 1;i<arr.length ;i++ )
  13.                 {
  14.                         int temp = arr[i];
  15.                         int j = i-1;
  16.                         while (temp<arr[j])
  17.                         {
  18.                                 arr[j+1]=arr[j];
  19.                                 j--;
  20.                                 if (j==-1)
  21.                                 {
  22.                                         break;
  23.                                 }
  24.                                 arr[j+1]=temp;
  25.                         }
  26.                 }
  27.         }

  29.         public static void print(int[] arr)
  30.         {
  31.                 for (int x =0;x<arr.length ;x++ )
  32.                 {
  33.                         System.out.println(arr[x]);
  34.                 }
  35.         }
  36. }
复制代码
作者: 肖琦    时间: 2012-7-25 09:58


  1. public static void insertSort(int[] arr){
  2.       for(int i = 1;i <arr.length; i++){
  3.                     int j = -1;
  4.          //找到arr[i]应该摆放的位置，此处可以利用查找算法进行优化
  5.          while(j <= i && arr[i] > arr[++j]);
  6.          if(j < i){
  7.                             //将j之后的数据移动一位，然后把arr[i]移动到j处
  8.                             int temp = arr[i];
  9.                             for(int k = i-1;k >= j;k--){
  10.                arr[k+1] = arr[k];
  11.              }
  12.              arr[j] = temp;
  13.                      }
  14.      }
  15. }
复制代码
简单说就是数组在循环过程中下一个和上一个比较，把小的放到上一个里，大的放到下一个里，然后接着循环，这样就实现了从小到大，希望我说的够详细


作者: 乐峰    时间: 2012-7-25 09:59
插入排序的原理：检查数组列表中的每个元素，并将其放入已排序元素中的适当位置，当最后一个元素放入合适位置时，该数组排序完毕.
public static void main(String[] args){
         int i,j;
    System.out.print("请输入数组中元素的个数：");
    Scanner input=new Scanner(System.in);
    int m=input.nextInt();
    int []a;
    a=new int[m];
    for(i=0;i<m;i++){
         System.out.print("第"+(i+1)+"元素：");
       a[i]=input.nextInt();
    }
    System.out.print("输出排序前的数组中的元素：");
     for(i=0;i<m;i++){
        System.out.print(a[i]+" ");
     }
     System.out.println();
    for(i=1;i<m;i++){
       int k=a[i];
       for(j=i-1;j>=0&&k<a[j];j--){
        a[j+1]=a[j];  
       }
       a[j+1]=k;
    }
    System.out.print("输出排序后的数组中的元素：");
    for(i=0;i<m;i++){
       System.out.print(a[i]+" ");
    }
   
     }
     
作者: 李菁    时间: 2012-7-25 10:18
        public static void main(String[] args) {
                int[] arr = {5,46,26,67,2,35};
                Sort(arr);
                for(int i = 0;i<arr.length;i++){  //显示排序后的数组       
                System.out.println(arr);
                }


        }
        public static void Sort(int[] arr){  //传入要排序的数组       
        for (int i = 1; i < arr.length; i++)   
        {   
            int temp = arr;   //循环把数组第二个值放到temp里
            int j = i;   
            while ((j > 0) && (arr[j - 1] > temp))  //temp值小于数组中的第一个值              {   
                arr[j] = arr[j - 1];//把数组中第一个值赋给第二个值   
                j--;   
            }   
            arr[j] = temp;   
        }   
}
至于插入排序原理可以举个例子：
摸牌时，左手是空的，每次摸一张牌，将它插入到左手的正确位置。
为了找到这张牌的正确位置，用它与手中已有的牌依次进行比较，要使手中的牌始终是排序好的。
作者: 张莹莹    时间: 2012-7-25 10:32
1.思路原理及代码见InsetSort.png

InsetSort.png (33.68 KB, 下载次数: 47)

插入排序

插入排序




欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2