排序算法理论与插入排序

排序算法

排序算法的评价指标

稳定性

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

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

排序算法分类

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

总结

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

插入排序

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

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

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

算法实现

外层循环遍历每个元素（从下标为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;//在空位置插入元素
            }
        }
    }
}

算法实现（哨兵）

复杂度分析

最好情况

原本有序，时间复杂度：O(n)

最坏情况

原本逆序 时间复杂度O(n**2)

空间复杂度 O(1)

最好情况 空间复杂度O(n)

最坏情况 空间复杂度O(n**2)

平均情况 空间复杂度O(n**2)

优化（折半插入排序）

思路：用折半查找找到要插入的位置，在移动元素。

例如：当前元素为55 先把元素保存到哨兵。 利用二分查找，与左边元素对比，寻找到插入位置。

当low>high时，折半查找停止，将[low，i-1]的所有元素右移。将A[0]复制到low所在的位置。

特殊情况，当前插入值与左边值相等时，不会停止折半查找，继续在mid所指位置的右边插入。

算法实现

因为只改变了比较次数，而没有改变移动次数，所以优化没有什么暖用........复杂度还是O(n**2)，所以优化了个锤子？？？？？

总结