插入排序
算法思想:
通俗的说,我们玩扑克牌的时候要把扑克排序,也就是说面前放10张扑克牌(10张已经排好序)我们要把把新的一张插入其中,然后插入到相应的位置。
在计算机中实现的时候,我们要做的是在我们插入元素之前,我们必须把其余元素都向右移动一位。
官方解释:
插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序。
时间复杂度为O(n^2)。
实现思路:
(1)用一个临时变量存放待排序的数字;
(2)从数组前依次遍历找第一个比待排序数字大的数字的位置;
(3)将从待排序的数字位置开始,到找的要插入的数字的位置之间的数字向后挪一位,最后将待排序数字插入到找到的位置;
实现动图:
实现的方法:
代码实现:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | import java.util.Scanner; public class Insertion { private static void exch(Comparable a[],int i,int j) {//交换元素位置 Comparable t = a[i]; a[i] = a[j]; a[j] = t; } private static boolean less(Comparable v,Comparable w) {//对元素进行比较 return v.compareTo(w) < 0; } public static void sort(Comparable a[]) { int N = a.length;//将a数组升序 for(int i = 1;i < N;i++) {//将a[i]插入到a[i-1]、a[i-2]、a[i-3]...之中 for(int j = i;j > 0 && less(a[j],a[j-1]);j--) { exch(a, j, j-1); } } } public static void main(String[] args) { // TODO 自动生成的方法存根 System.out.println("请输入想要排序的数组:"); String Arrays[] = new String[5]; for(int i = 0;i < 5;i++) { Scanner S = new Scanner(System.in); Arrays[i] = S.next(); } System.out.println("排序后结果为:"); sort(Arrays); for(int i = 0;i < 5;i++) { System.out.print("\t"+Arrays[i]); } } } |
打算明天主写less 和exch功能实现。