java中简单选择排序和直接插入排序,实例展示

BSO 2020-09-15 14:06:09 java常见问答 6054

java作为一门功能强大内容丰富的编程语言,它的使用也是十分广泛的,涉及到了我们工作与生活的方方面面。今天就为大家介绍一下java中简单选择排序和直接插入排序的实例展示,一起来看看吧。

一、首先是简单选择排序:

简单选择排序的基本原理是:

1.对于给定的一组记录,经过第一轮比较后得到最小的记录;

2.然后将该记录与第一个记录的位置进行交换;

3.接着对不包括第一个记录以外的其他记录进行第二轮比较,得到最小的记录并与第二个记录进行位置交换;

4.重复该过程,直到进行比较的记录只有一个时为止。

实现过程为:

1.将整个记录序列划分为有序区和无序区,初始时,有序区为空,无序区含有待排序的所有记录。

2.在无序区中选取关键码最小的记录,将它与无序区中的第一个记录交换,使得有序区扩展了一个记录,同时无序区减少了一个记录。

3.不断重复第二步,直到无序区只剩下一个记录为止。此时所有的记录已经按关键码从小到大的顺序排列。具体代码如下所示:

/**
 * $Id: TestDemo.java,v 1.0 2020/8/23 20:47 *** Exp $
 * <p>
 * Copyright 2016 Asiainfo Technologies(China),Inc. All rights reserved.
 */
package com.asiainfo.emos.sec.api.impl;
/**
 * @author ***
 * @version $Id: TestDemo.java,v 1.1 2020/8/23 20:47 *** Exp $
 * Created on 2020/8/23 20:47
 */
public class TestDemo
{
    static void selectSort(int arr[])
    {
        int i;
        int j;
        //用temp记录在一趟比较过程最小记录
        int temp = 0;
        //用flag记录在一趟比较过程最小的记录位置
        int flag = 0;
        /**
         * 个人理解:大的循环首先要遍历每个参数,内循环假设首个最小值与每个值进行对比,利用中间参数temp接收最小值
         * 将假定首位的值放入真正最小值的位置相当于替换它,将真正最小值temp放入首位,
         *
         *
         */
        for (i = 0; i < arr.length - 1; i++)
        {
            //每轮开始temp设定为当前无序区的最小记录。
            temp = arr[i];
            //每轮开始时将(flag=i)设定为当前无序区的第一个位置
            flag = i;
            // 用temp与无序区中的其他记录进行比较
            for (j = i + 1; j < arr.length; j++)
            {
                if (arr[j] < temp)
                {
                    temp = arr[j];
                    flag = j;
                }
            }
            //一趟比较结束后,flag中保留的就是本趟排序的关键码最小的记录位置,temp中保留的就是本趟排序的关键码最小的记录。
            if (flag != i)
            {
                // 将每轮开始时假定的无序区的最小值arr[i](即本轮无序区的首元素),放到真正最小值的位置;然后将真正的最小值temp,放在本轮无序区的首位
                //将首位的值放到被排序出来刚被排序出来的位置
                arr[flag] = arr[i];
                arr[i] = temp;
            }
        }
    }
    public static void main(String[] args)
    {
        int arr[] = {
            2
            , 5
            , 8
            , 1
            , 3
            , 6
            , 9
            , 0
            , 4
            , 7
        };
        selectSort(arr);
        for (int i = 0; i < arr.length; i++)
            System.out.println(arr[i]);
    }
}

简单选择排序

二、直接插入排序(Insertion Sort)

它的基本思想是,每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子序列中的适当位置,直到全部记录插入完成为止。具体代码如下所示:

static void Insertsort1(int a[])
{
    int i, j, k;
    for (i = 1; i < a.length; i++)
    {
        //为a[i]在前面的a[0...i-1]有序区间中找一个合适的位置
        for (j = i - 1; j >= 0; j--)
            if (a[j] < a[i])
                break;
        //如找到了一个合适的位置
        if (j != i - 1)
        {
            //将比a[i]大的数据向后移
            int temp = a[i];
            for (k = i - 1; k > j; k--)
                a[k + 1] = a[k];
            //将a[i]放到正确位置上
            a[k + 1] = temp;
        }
    }
}

以上就是有关java中简单选择排序和直接插入排序的实例展示。如果你对java知识感兴趣,想要了解更多java基础java经典例子,敬请关注奇Q工具网。

推荐阅读:

java排序方法对比,其他排序展示

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

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