常见排序算法(二) 插入排序

1、直接插入排序

• 算法思想
  若下个升序排序，将数组中的元素依次与前面的元素(前面的元素已是排序好的状态)进行比较，找到合适的位置插入，后面的元素则后移一位。
• 代码实现

public class InsertSort
{
    public static void insertSort(int[] arr)
    {
        for(int i = 1; i < arr.length; i++)
        {
            int temp = arr[i];
            for(int j = i; j >= 0; j--)
            {
               //往前比较，如果比i位大就后移一位
                if(j > 0 && arr[j-1] > temp)
                {
                    arr[j] = arr[j-1];
                }
                else
                {
                    arr[j] = temp;
                    break;
                }
            }
        }
    }
    public static void main(String[] args)
    {
        int[] array = new int[]{22,44,77,88,189,22,22,35,666,33,99,66};
        insertSort(array);
        for(int i = 0; i<array.length;i++)
        {
            System.out.println(array[i]);
        }
    }
}

• 复杂度
  时间复杂度：初始有序比较n-1次时间复杂度最好O(n)，最坏O(n^2)
• 稳定性
  稳定
• 使用场景
  对于数据量比较小且基本有序的状况效率比较高

2、希尔排序

• 算法思想
  递减增量排序算法
  将数组分割成若干个子序列分别进行直接插入排序，使得整个数组基本有序，再对全体记录进行依次直接插入排序。
  以步长分组排序
• 代码实现

public class ShellSort
{
    public static void shellSort(int[] arr) {
        int gap = arr.length/2;
        for (; gap > 0; gap /= 2) {
            for (int i = 0; i + gap < arr.length; i++)
                for (int j = i; j + gap < arr.length; j+=gap) {
                    if (arr[j] > arr[j + gap]) {
                        int temp = arr[j];
                        arr[j] = arr[j + gap];
                        arr[j + gap] = temp;
                    }
                }
            }
        }
    }
    public static void main(String[] args)
    {
        int[] array = new int[]{22,44,77,88,189,22,22,35,666,33,99,66};
        shellSort(array);
        for(int i = 0; i<array.length;i++)
        {
            System.out.println(array[i]);
        }
    }
}

• 复杂度
  时间复杂度：
  最好时间复杂度：正序，只比较不交换，O(n)
  最坏时间复杂度：初始步长大，分组多但每组元素少，所以速度快；后续排序变慢。最坏时间复杂度和步长序列的选择有关。代码实现中的方式最坏时间复杂度为 O(n^2) 。其他的步长序列后续补充。
• 稳定性
  多次排序会导致相等的元素位置交换，不稳定
• 使用场景
  数据量非常大没有快速排序快，但是数据规模中等表现良好。