美文网首页程序员
直接插入排序(JAVA)

直接插入排序(JAVA)

作者: 林天涯 | 来源:发表于2018-01-01 09:13 被阅读0次

    前言


      本文集将用java语言实现包括插入排序(直接插入、折半插入、希尔排序),交换排序(快速排序和冒泡排序),选择排序,堆排序,归并排序以及基数排序在内的所有内排序算法。虽然都很简单且实际开发几乎已运用不到(Arrays.Sort和Collection.Sort可直接调用),但是这些属于一个程序员的基本功,熟稔掌握是必须的。

    算法


      直接插入排序的思想就是当发现序列不是有序的情况下时,将待排序元素插入到前面已经有序的序列中。所以怎么插是核心问题,其实归根结底还是找到待排序元素的插入位置。由于是从小到大排序,可由待排序元素的前一个位置开始从后向前比较,若发现比较元素大于待排序元素,则将比较元素向后移位以腾出位置。最终将元素赋值给排序结束腾出的位置。
      边比较边移位是其特点,所以有待优化的地方。后续的折半插入和希尔排序都是对直接插入排序的一种优化。时间复杂度为o(n*n)。

    例子


    以序列 4 3 1 2 5为例


    示例

    Codes


    package com.fairy.InnerSort;
    
    import java.util.Scanner;
    
    /**
     * 直接插入排序
     * @author Fairy2016
     *
     */
    public class DirectInsertSort {
        
        public static void sort(int a[], int n) {
            int i,j;
            for(i = 2; i <= n; i++) {
                if(a[i-1] > a[i]) {
                    a[0] = a[i];//a[0]作为探针,既存储待排序元素又作循环停止标志,省却if判断
                    for(j = i-1; a[j] > a[0]; j--) {
                        a[j+1] = a[j];//遇到比a[i]大的向后移位,腾出位置
                    }
                    a[j+1] = a[0];//将待排序元素赋值到最终位置
                }
            }
        }
        
        public static void Print(int a[], int n) {
            for(int i = 1; i <= n; i++) {
                System.out.print(a[i]+" ");
            }
        }
    
        public static void main(String args[]) {
            int n;
            int a[];
            Scanner scanner = new Scanner(System.in);
            while(scanner.hasNext()) {
                n = scanner.nextInt();
                if(n > 0) {
                    a = new int[n+1];
                    for(int i=1; i <= n; i++) {
                        a[i] = scanner.nextInt();
                    }
                    sort(a, n);
                    Print(a, n);
                }
            }
        }
    }
    
    

    相关文章

      网友评论

        本文标题:直接插入排序(JAVA)

        本文链接:https://www.haomeiwen.com/subject/sywzgxtx.html