黑马程序员技术交流社区

标题: Java排序总结（2） [打印本页]

---

作者: 徐梦侠    时间: 2012-10-12 00:05
标题: Java排序总结（2）

（一个帖子限制字数，不能发完，这个接上帖）
4、插入排序：
包括：直接插入排序，二分插入排序（又称折半插入排序），链表插入排序，希尔排序（又称缩小增量排序）。

直接插入排序：无序插有序，将数组中每个数依次插入已经排列好顺序的数组中，需要用到嵌套循环，外层循环标识并决定待比较的数值。内层循环为待比较数值确定其最终位置。直接插入排序是将待比较的数值与它的前一个数值进行比较，所以外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较，直到找到比待比较数值小的并将待比较数值置入其后一位置，结束该次循环。

public static void inSort(int[] arr) {

   int num=arr.length;

   int i,j;

   for(i=0;i<num;i++){

      int temp=arr;

      for(j=i; j>0 && temp<arr[j-1]; j--){

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

       }

       arr[j]=temp;

    }

}

5、希尔排序：
属于插入类排序，是将整个无序列分割成若干小的子序列分别进行插入排序。(下面希尔排序代码还需优化，只能表达思想，还不能正确运行)

public class Test {

   public static int[] a = { 10,32, 1, 9, 5, 7, 12, 0, 4, 3 };

   public static void main(String args[]) {

      int i; // 循环计数变量

      int Index = a.length;// 数据索引变量

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

      for (i = 0; i < Index - 1; i++)

          System.out.printf("%3s ", a);

      System.out.println("");

      ShellSort(Index - 1); // 选择排序

      // 排序后结果

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

      for (i = 0; i < Index - 1; i++)

          System.out.printf("%3s ", a);

      System.out.println("");

   }

   public static void ShellSort(int Index){

      int i, j, k; // 循环计数变量

      int Temp; // 暂存变量

      boolean Change; // 数据是否改变

      int DataLength; // 分割集合的间隔长度

      int Pointer; // 进行处理的位置

      DataLength = (int) Index / 2; // 初始集合间隔长度

      while (DataLength != 0) // 数列仍可进行分割

      {

          // 对各个集合进行处理

         for (j = DataLength; j < Index; j++) {

              Change = false;

              Temp = a[j]; // 暂存Data[j]的值,待交换值时用

              Pointer = j - DataLength; // 计算进行处理的位置

              // 进行集合内数值的比较与交换值

             while (Temp < a[Pointer] && Pointer >= 0 && Pointer <= Index) {

                 a[Pointer + DataLength] = a[Pointer];

                 // 计算下一个欲进行处理的位置

                 Pointer = Pointer - DataLength;

                 Change = true;

                if (Pointer < 0 || Pointer > Index)

                   break;

              }

              // 与最后的数值交换

              a[Pointer + DataLength] = Temp;

            if (Change) {

                  // 打印目前排序结果

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

                for (k = 0; k < Index; k++)

                      System.out.printf("%3s ", a[k]);

                  System.out.println("");

             }

         }

         DataLength = (int)DataLength/2; // 计算下次分割的间隔长度

      }

   }

}

6、Java提供的排序方法
Java的util包中提供了一个数组排序方法，开发时使用该句代码

Arrays.sort(arr);

---

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

黑马程序员IT技术论坛 X3.2