插入排序

假设数列第一个元素为已排序数列，剩余数列为未排序将待排序元素挨个插入到已排序数列中每次插入都必须保证数列是有序的，即通过比较和移动有序数列中的元素，将元素插入到合适的位置
思路：如同玩扑克牌一样，每次摸牌都将它与手中的牌比较，始终将牌放在比它大的牌前面，比它小的牌后面。这样当牌全部摸到手上后，就是一个有序的序列。从后往前找合适的位置。

public class MainActivity extends AppCompatActivity {
    int[] arr = new int[]{9, 5, 4, 8, 7, 3, 1};
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_main);
        int[] insert = insert(arr);
        System.out.println(Arrays.toString(insert));

    }

    public int[] insert(int[] array) {
        for (int i = 1; i < array.length; i++) {
            if (array[i] < array[i - 1]) {//如果第i个数大于前一个数就不用判断了,因为前面都是有序数列,大于前一个数肯定比前面所有数都大,否则的话把这个数拿出来也就是赋值给temp,然后依次与前面的数比较,如果比前一个数小就让前一个数往后挪一位直到找到比temp小的位置放进去
                int temp = array[i];
                int f = i;
                for (; f >= 1 && array[f - 1] > temp; f--) {
                    array[f] = array[f-1];

                }
            array[f] = temp;
            }
        }
        return array;
    }
}