疯狂java


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

Java提高八大排序方法之一


 

   

  这篇文章讲八种排序方法中的直接插入排序和希尔排序,这两种排序都属于插入排序的范畴。

  直接插入排序:

  原理:将数组分为无序区和有序区两个区,然后不断将无序区的第一个元素按大小顺序插入到有序区中去,最终将所有无序区元素都移动到有序区完成排序。

  要点:设立哨兵,作为临时存储和判断数组边界之用。

  实现:

  public static void InsertSort(int L[]) {

  int i, j;// 分别为有序区和无序区指针

  for (i = 0; i < L.length - 1; i++) {// 逐步扩大有序区

  j = i + 1;

  if (L[j] < L[i]) {

  int temp = L[j];// 存储待排序元素

  while (i >= 0 && temp < L[i]) {// 查找在有序区中的插入位置,同时移动元素

  L[i + 1] = L[i];// 移动

  i--;// 查找

  }

  L[++i] = temp;// 将元素插入

  }

  i = j - 1;// 还原有序区指针

  }

  }

  希尔排序:

  原理:又称增量缩小排序。先将序列按增量划分为元素个数相同的若干组,使用直接插入排序法进行排序,然后不断缩小增量直至为1,最后使用直接插入排序完成排序。

  要点:增量的选择以及排序最终以1为增量进行排序结束。

  实现:

  public static void ShellSort(int L[]) {

  int d = L.length;

  while (d >= 1) {// 直到增量缩小为1

  Shell(L, d);

  d = d / 2;// 缩小增量

  }

  }

  public static void Shell(int L[], int d) {

  int i, j;

  System.out.println(d);

  for (i = d; i < L.length; i++) {

  if (L[i] < L[i - d]) {

  int temp = L[i];

  j = i - d;

  while (j >= 0 && L[j] > temp) {

  L[j + d] = L[j];// 移动

  j = j - d;// 查找

  }

  L[j + d] = temp;

  }

  }

  }

  这两种方法都属于插入排序的范畴,不是太难理解,看代码就可以知道了。