java中选择排序与归并排序的内容,详细解析

BSO 2020-09-09 08:53:43 java常见问答 6983

上次我们已经为大家介绍过java中插入、分治和快速排序的内容,今天再来为大家介绍一下java中选择排序与归并排序的具体内容,并且通过实际的代码为大家解析。

首先我们需要了解的是,选择排序也是一种简单直观的排序算法,实现原理比较直观易懂。

1.在未排序数列中找到最小元素;2.然后将其与数列的首部元素进行交换;3.在剩余未排序元素中继续找出最小元素;4.将其与已排序数列的末尾位置元素交换;5.以此类推,直至所有元素圴排序完毕,图片如下所示:

选择排序

代码如下所示:

public static void sort(int[] arr)
{
    for (int i = 0; i < arr.length - 1; i++)
    {
        int min = i; // 遍历的区间最小的值
        for (int j = i + 1; j < arr.length; j++)
        {
            if (arr[j] < arr[min])
            {
                // 找到当前遍历区间最小的值的索引
                min = j;
            }
        }
        if (min != i)
        {
            // 发生了调换
            int temp = arr[min];
            arr[min] = arr[i];
            arr[i] = temp;
        }
    }
}

接下来我们看一下归并排序。

归并排序,简而言之就是把一串数,从中平等分为两份,再把两份再细分,直到不能细分为止,其实就是分而治之的分的步骤。再从最小的单元,两两合并,合并的规则是将它们按从小到大的顺序放到一个临时数组中,再把这个临时数组替换原数组对应的位置,这就是治。具体图解如下所示:

归并排序

归并排序

归并排序

代码展示如下所示:

public static void mergeSort(int[] a, int s, int e)
{
    int m = (s + e) / 2;
    if (s < e)
    {
        mergeSort(a, s, m);
        mergeSort(a, m + 1, e);
        //归并
        merge(a, s, m, e);
    }
}
private static void merge(int[] a, int s, int m, int e)
{
    //初始化一个从起始s到终止e的一个数组
    int[] temp = new int[(e - s) + 1];
    //左起始指针
    int l = s;
    //右起始指针
    int r = m + 1;
    int i = 0;
    //将s-e这段数据在逻辑上一分为二,l-m为一个左边的数组,r-e为一个右边的数组,两边都是有序的
    //从两边的第一个指针开始遍历,将其中小的那个值放在temp数组中
    while (l <= m && r <= e)
    {
        if (a[l] < a[r])
        {
            temp[i++] = a[l++];
        }
        else
        {
            temp[i++] = a[r++];
        }
    }
    //将两个数组剩余的数放到temp中
    while (l <= m)
    {
        temp[i++] = a[l++];
    }
    while (r <= e)
    {
        temp[i++] = a[r++];
    }
    //将temp数组覆盖原数组
    for (int n = 0; n < temp.length; n++)
    {
        a[s + n] = temp[n];
    }
}

以上就是有关在java中选择排序与归并排序的具体内容,并且通过实际的代码为大家展示。如果你对java知识感兴趣,想要了解更多java基础,敬请关注奇Q工具网。

推荐阅读:

java中对象排序的概念是什么?实例代码展示

java集合排序该如何实现?

java中冒泡排序低级版与高级版对比,实例展示