平武建站

深入浅析java中的排序方法

这篇文章给大家介绍深入浅析java中的排序方法，内容非常详细，感兴趣的小伙伴们可以参考借鉴，希望对大家能有所帮助。

专注于为中小企业提供成都网站设计、成都网站建设服务,电脑端+手机端+微信端的三站合一,更高效的管理,为中小企业龙沙免费做网站提供优质的服务。我们立足成都，凝聚了一批互联网行业人才，有力地推动了上千家企业的稳健成长，帮助中小企业通过网站建设实现规模扩充和转变。

排序

1、概念：

有n个记录的序列{R1,R2,.......,Rn}（此处注意：1,2,n 是下表序列，以下是相同的作用），其相应关键字的序列是{K1,K2,.........,Kn}。通过排序，要求找出当前下标序列1,2,......,n的一种排列p1,p2,........pn，使得相应关键字满足如下的非递减（非递增）关系，即：Kp1<=Kp2<=Kpn，这样就得到一个按关键字有序的记录序列：{Rp1,Rp2,.......,Rpn}。

2、分类

根据排序时数据所占用存储器的不同，可将排序分为两类。

内部排序：整个排序过程完全在内存中进行，如下：

插入类排序（直接插入排序、折半插入排序、希尔排序）；

交换类排序（冒泡排序、快速排序）；

选择类排序（简单选择排序、树型选择排序、堆排序）；

归并排序；

分配类排序（多关键字排序、链式基数排序、基数排序的顺序表实现））；

外部排序：由于待排序记录数据量太大，内存无法容纳全部数据，排序需要借助外部存储设备才能完成（磁盘排序，磁带排序）。

3、稳定性

假设在待排序的序列中存在多个具有相同关键字的记录。设Ki=Kj(1<=i<=n,1<=j<=n,i != j)，若在排序前的序列中Ri领先与Rj(即i<=j)，经过排序后得到的序列中Ri仍然领先与Rj，则称所用的排序方法是稳定的；反之，当相同关键字的领先关系在排序过程中发生变化，则所用的排序方法是不稳定的。

插入排序：

思想：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。

直接插入排序：

算法思想：假设待排序的记录存放在数组R[1..n]中。初始时，R[1]自成1个有序区，无序区为R[2..n]。从i=2起直至i=n为止，依次将R[i]插入当前的有序区R[1..i-1]中，生成含n个记录的有序区。

用java实现的代码如下：

package exp_sort;
public class DirectInsertSort {
  public static void DircstSort(int array[]) {
    int j;
    // 循环从第二个数开始，第一个数用做存放待插入的记录
    for (int i = 1; i < array.length; i++) {
      int temp = array[i];
      // 寻找插入位置
      for (j = i; j > 0 && temp < array[j - 1]; j--) {
        array[j] = array[j - 1];
      }
      // 将待插入记录插入到已经排序的序列中
      array[j] = temp;
    }
    for (int i = 0; i < array.length; i++) {
      System.out.print(array[i] + " ");
    }
    System.out.println("\n");
  }
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int array[] = { 38, 62, 35, 77, 55, 14, 35, 98 };
    DircstSort(array);
  }
}

算法分析：最好的情况是待排序记录本身已经按照关键字有序排列，最坏的情况是待排序记录是按照关键字逆序排列的；时间复杂度是O(N^2)，空间复杂度是O(1)；该算法是稳定的排序算法：比较适用于待排序记录数目较少且基本有序的情况。

折半插入排序：

算法思想：对于有序表进行折半查找，其性能优于顺序查找。

算法实现代码如下：

package exp_sort;
public class BinaryInsertSort {
  public static void sort(int array[]) {
    int temp, low, mid, high;
    for (int i = 1; i < array.length; i++) {
      temp = array[i];
      low = 0;
      high = i -1;
      //确定插入位置
      while (low <= high) {
        mid = (low + high) / 2;
        if (temp < array[mid]) {
          high = mid - 1;
        } else {
          low = mid + 1;
        }
      }
      //记录依次向后移动
      for (int j = i; j >= low + 1; j--) {
        array[j] = array[j-1];
      }
      //插入记录
      array[low] = temp;
    }
    for (int i = 0; i < array.length; i++) {
      System.out.print(array[i] + " ");
    }
    System.out.println("\n");
  }
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int array[] = {38, 62, 35, 77, 55, 14, 35, 98};
    sort(array);
  }
}

算法分析：是一种稳定的排序算法，比直接插入算法明显减少了关键字之间比较的次数，因此速度比直接插入排序算法快，但记录移动的次数没有变，所以折半插入排序算法的时间复杂度仍然为O(n^2)，与直接插入排序算法相同。

关于深入浅析java中的排序方法就分享到这里了，希望以上内容可以对大家有一定的帮助，可以学到更多知识。如果觉得文章不错，可以把它分享出去让更多的人看到。


网站名称：深入浅析java中的排序方法
分享URL：http://pwwzsj.com/article/pjcgee.html

其他资讯