疯狂java


您现在的位置: 疯狂软件 >> 新闻资讯 >> 正文

Java算法之插入排序


 

   

  1.直接插入排序

  感觉自己写的排序怪怪的,算了,以后再好好学习吧,现在就这样了,继续努力

  2.希尔排序

  采取了两个处理方式,还是感觉怪怪的,先记下来,明天继续看。。。。。

  /*插入排序

  1.直接插入排序方法 时间复杂度 :O(n^2) 稳定的排序(相等的数字不会交换位置)

  一直n歌数据,从第一个数据开始,将后面的每一个数据,插入到前面已经排好顺序的数据中的合适的位置。

  例如:12 43 23 15 25

  12 43 23 15 25 43>12不做处理

  12 43 23 15 25 23插入到12与43之间, 那么,23<43则23和43,交换位置

  23>12?则不再继续循环,12 23 43,不再变化

  12 23 43 15 25 15插入到12与23之间,那么,15<43?,则15和43 互换<12 23 15 43>

  15<23则15与23互换<12 15 23 43>,15>12?位置不变

  12 15 23 43 25 25插入到23与43之间,25<43?互换位置<12 15 23 25 43>,25>23?不变化

  2.希尔排序(最小增量排序) 时间复杂度在O(n)--O(n^2)之间

  将数组分成若干个小模块然后,对每一个小模块进行插入排序,在一次进行分块,直到每个块中有一个数字为

  1).最外层分组,用d进行分组

  2).对每个一组进行插入排序

  1).最外层分组,用d进行分组

  2).当i=0的时候对第一组进行排序,第一组排序之后前d个数字已经是有序的

  3).第二组要在第一组的基础上进行排序,第一组的数字是有序的,

  因此,第i+d个数字,插入到arr[i]--arr[i+d-1]个数字中,直接从最后一个开始换位置

  例如:8 54 98 100 19 120

  d=3 arr[d]

  (8 54 98 100) 19 120

  8 (19 54 98 100) 120

  8 19 (54 98 100 120)

  ----------------------------------------

  d=1 (8) 19 54 98 100 120

  8 19 54 98 100 120

  8 19 54 98 100 120

  8 19 54 98 100 120

  8 19 54 98 100 120

  */

  public class SortAgrimatic {

  //插入排序方法???--->感觉怪怪的

  public static int[] insertSort(int[] arr)

  {

  int temp;//定义临时变量

  for(int i=1;i

  {

  /*arr[i]的位置会变化,使用变量j来记录,

  遇到小的就换位置,遇到大的数字,就不变化*/

  for(int j = i-1;j>=0;j--)

  {

  if(arr[j+1]

  {

  temp = arr[j+1];

  arr[j+1] = arr[j];

  arr[j] = temp;

  }

  else

  break;//结束内循环

  }

  }

  print(arr);

  return arr;

  }

  //希尔排序方法???--->感觉更怪

  public static int[] shellSort(int[] arr)

  {

  int d = (int) Math.ceil(arr.length/2);

  int temp;

  System.out.println(d);

  while(d>0)

  {

  if(d%2==0)

  d=d+1;

  for(int i=0;i+d

  {

  for(int j=i;j

  {

  for(int k=j+1;k>i;k--)

  {

  if(arr[k]

  {

  temp = arr[k];

  arr[k] = arr[k-1];

  arr[k-1] = temp;

  }

  else

  break;

  }

  }

  }

  d = d/2;

  }

  return arr;

  }

  /*希尔排序2,为什么不这么实现呢?第一次小组排序之后就是有序的,之后可以直接从最后开始插入了? */

  public static int[] hillSort(int[] arr)

  {

  int d = (int) Math.ceil(arr.length/2);

  int temp;

  //1.最外层分组,用d进行分组

  while(d>0)

  {

  if(d%2==0)

  d=d+1;

  //2.当i=0的时候对第一组进行排序,第一组排序之后前d个数字已经是有序的

  int i = 0 ;

  for(int j=i;j

  {

  for(int k=j+1;k>0;k--)

  {

  if(arr[k]

  {

  temp = arr[k];

  arr[k] = arr[k-1];

  arr[k-1] = temp;

  }

  else

  break;

  }

  }

  i=1;//进入第二组

  System.out.print(d+"--");

  print(arr);

  /*3.第二组要在第一组的基础上进行排序,第一组的数字是有序的,

  * 因此,第i+d个数字,插入到arr[i]--arr[i+d-1]个数字中,直接从最后一个开始换位置

  * */

  while(i+d

  {

  for(int j=i+d;j>i;j--)

  {

  if(arr[j]

  {

  temp = arr[j-1];

  arr[j-1] = arr[j];

  arr[j] = temp;

  }

  else

  break;

  }

  i++;

  print(arr);

  }

  System.out.println("----------------------------------------");

  d = d/2;

  }

  return arr;

  }

  //输出函数,输出数组

  public static void print(int[] arr)

  {

  for(int i=0;i

  {

  System.out.print(arr[i]+" ");

  }

  System.out.println("");

  }

  public static void main(String[] args) {

  int[] arr = new int[]{57,68,59,52,72,28,96,33,24,19};

  System.out.print("排序前::");

  print(arr);

  // arr = insertSort(arr);

  arr = shellSort(arr);

  // arr = hillSort(arr);

  System.out.print("排序后::");

  print(arr);

  }

  }