排序算法理论与插入排序

排序算法

排序算法的评价指标

稳定性

alt

排序前后相同元素的相对位置没有发生改变，称为稳定。反之称为不稳定

稳定的排序算法不一定比不稳定的好，要看实际需求

排序算法分类

alt

内部排序关注如何使算法的时间、空间复杂度更低。外部排序关注如何使磁盘的读写次数更少。

总结

alt

学习网站：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

插入排序

算法思想：将一个待排序的记录按其关键字的大小插入到前面已排序的子序列中，直到全部的记录插入完毕。

第一步默认从下标为1的元素开始，将下标为1的元素与左边元素对比。

alt

第二步如果比左边元素大就插入到他的前面。为了保障稳定性，遇到元素相等不右移。

alt

算法实现

alt

外层循环遍历每个元素（从下标为1开始）内层循环用于对比当前元素与左边元素的的大小。只有当前元素比左边元素更大，才插入到元素前面。插入元素就是将插入位置右边的所有元素右移

package wangdao.TreeNode;
import java.util.Arrays;

/**
 * @author 韩明保
 * @version 1.0
 * @description: TODO
 * @date 2022/5/11 23:06
 */
public class InsertSort {

    public static void main(String[] args) {
        int[] nums={49,38,35,32,65,55,43,87,90};
        insertSort(nums,nums.length);
        System.out.println(Arrays.toString(nums));
    }
    public static   void insertSort(int[] nums,int n){
        int i,j,temp; //temp用于保存要插入的元素
        for( i=1;i<n;i++){//从第二个元素开始对比（下标为1）
            if (nums[i]<nums[i-1]){ //当前插入元素比左边元素小（寻找插入位置进行插入）
                temp=nums[i];
                for (j=i-1;j>=0&&nums[j]>temp;j--){ //插入元素左边的所有元素与 待插入的元素进行对比。找到插入位置。
                    nums[j+1]=nums[j]; //插入元素就是将位置空出来（元素右移）
                }
                nums[j+1]=temp;//在空位置插入元素
            }
        }
    }
}