插入排序Java实现

/**
 * 将元素分为两组，一组有序，一组无序，依次遍历无序数组中的每一个元素插入到有序数组中的合适位置
 * 至于怎么插入，可以从紧挨着当前无序数组中元素的有序数组元素开始，若遇到比当前元素还小的元素，则交换位置
 * 直到遇到比自己元素大的元素，才能确定最终位置。
 */
public class InsertionSort {
    public static void insertionSort(Comparable[] arr){
        for(int i = 1;i<= arr.length-1;i++){    //从下标为1的元素开始，插入到左边有序数组的合适位置，
                                                // 初始左边有序数组只有arr[0]一个元素
            int index = i;                      // 将当前要插入有序数组的元素的索引进行存储，因为是依次进行比较,
                                                // 会发生元素交换，所以应该声明一个变量用来存储现在插入元素的实时位置
            for(int j = i;j>=1;j--){            // 每次插入一个新的元素，最多比较i次，刚好和外层循环产生联系。
                if(arr[index].compareTo(arr[index-1])<0){   //判断当前元素是否比前一个元素小，如果小的话，则交换两个元素的位置
                    swap(arr,index,index-1);
                }else{
                    break;                      //若当前元素大于等于前一个元素，则没有继续进行循环的必要了，跳出循环即可。
                }
                index--;                        //实时更新待插入元素索引的位置
            }
        }
    }

    //用于交换数组指定位置的两个元素
    private static void swap(Comparable[] arr, int j, int i) {
        Comparable temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}