java插入排序及循环不变式

旧城等待， 2022-05-15 01:18 133阅读 0赞

**循环不变式**的三个性质：  
初始化：循环的第一次迭代之前，它为真。  
保持：如果循环的某次迭代之前它为真，那么下次迭代之前它仍为真。  
终止：在循环终止时，不变式为我们提供一个有用的性质，该性质有助于证明算法是正确的。  
**插入排序**主要思想：序列中第一个数默认为是排序好的，从第二个数开始，依次插入前面排序好的部分形成新的排序好的子序列，最终完成排序。  
**注**：if语句只执行一次，while语句为循环语句，直到条件不满足才跳出循环，因此比较部分用while而不能用if。

import java.util.*;
    public class InsertSort{
        public static void main(String[] args){
            int a[] = {
       5,2,4,6,1,3};
            insertsort(a);
        }
        public static void insertsort(int a[]){
            int tmp = 0;
            //第一个数字是排序好的
            for(int i = 1; i < a.length; i++){
                tmp = a[i];  //待插入的当前值缓存
                int j = i - 1;
                //tmp依次跟前面排序好的j个数比较，1到a.length-1次
                while(j >= 0 && a[j] > tmp){
                    // 比tmp大的依次右移
                    a[j+1] = a[j];  
                    j = j - 1;
                }
                //当tmp不比a[j]小时插入j+1位置
                a[j+1] = tmp;
                System.out.println("第 " + i + " 次排序后序列 = " + Arrays.toString(a));
            }
        }
    }

输出：

第 1 次排序后序列 = [2, 5, 4, 6, 1, 3]
    第 2 次排序后序列 = [2, 4, 5, 6, 1, 3]
    第 3 次排序后序列 = [2, 4, 5, 6, 1, 3]
    第 4 次排序后序列 = [1, 2, 4, 5, 6, 3]
    第 5 次排序后序列 = [1, 2, 3, 4, 5, 6]

降序：

public static void insertdownsort(int a[]){
            int tmp = 0;
            //第一个数字是排序好的
            for(int i = 1; i < a.length; i++){
                tmp = a[i];  //待插入的当前值缓存
                int j = i - 1;
                //tmp依次跟前面排序好的j个数比较
                while(j >= 0 && a[j] < tmp){
                    // 比tmp小的依次右移
                    a[j+1] = a[j];  
                    j = j - 1;
                }
                //当tmp不比a[j]大时插入j+1位置
                a[j+1] = tmp;
                System.out.println("第 " + i + " 次排序后序列 = " + Arrays.toString(a));
            }
        }

输出：

第 1 次排序后序列 = [5, 2, 4, 6, 1, 3]
    第 2 次排序后序列 = [5, 4, 2, 6, 1, 3]
    第 3 次排序后序列 = [6, 5, 4, 2, 1, 3]
    第 4 次排序后序列 = [6, 5, 4, 2, 1, 3]
    第 5 次排序后序列 = [6, 5, 4, 3, 2, 1]