【九月打卡】第19天 选择排序法+插入排序法

课程名称：算法与数据结构
课程章节：选择排序法+插入排序法
课程讲师： Liuyubobobo

课程内容

数据结构

数据结构研究的是数据如何在计算机中进行组织和存储，使得我们可以高效的获取数据或者修改数据。

算法

Algorithm的本意：解决问题的方法
算法是一系列解决问题的，清晰，可执行的计算机指令

有限性
确定性：不会产生二义性
可行性
输入
输出

排序算法

• 插入、冒泡、选择，希尔
• 快速、归并、堆排序
• 计数排序、桶排序

插入排序

package com.wkq.insertionsort;

import com.wkq.Sort;
import com.wkq.selectionsort.SelectionSort2;
import com.wkq.util.ArrayGenerator;
import com.wkq.util.SortingHelper;

/**
 * 插入排序法
 */
public enum InsertionSort implements Sort {
    INSTANCE;

    @Override
    public <E extends Comparable<E>> void sort(E[] arr) {
        //arr[0,i)已排序，[i,n)未排序，每次都将i插入到已排序数组中的合适位置
        for (int i = 1; i < arr.length; i++) {
            E temp = arr[i];//暂存i位置处的元素
            int j;
            for (j = i; j > 0 && temp.compareTo(arr[j - 1]) < 0; j--) {
                arr[j] = arr[j - 1];
            }
            arr[j] = temp;
        }
    }

    public static void main(String[] args) {
        int[] dataSize = {10000, 100000};
        for (int n : dataSize) {
            Integer[] arr = ArrayGenerator.generatorRandomArray(n, n);
            SortingHelper.sortTest(InsertionSort.INSTANCE, arr);
        }
    }
}

选择排序

package com.wkq.selectionsort;

import com.wkq.Sort;
import com.wkq.util.ArrayGenerator;
import com.wkq.util.SortingHelper;

/**
 * 初始状态：arr[0...n)未排序
 * 外层循环执行操作：arr[i,n)中的最小值要放到arr[i]的位置
 * 内存循环执行操作：找出arr[i,n)中最小值的索引 minIndex
 * 循环不变量：arr[i...n)未排序，arr[0...i)已排序
 * 选择排序法的复杂度分析：
 *  1+2+3+...+n
 *  =(1+n)*n/2
 *  =(1/2)*n^2+(1/2)n
 *  O(n^2)
 */
public enum SelectionSort implements Sort {
    INSTANCE;

    @Override
    public <E extends Comparable<E>> void sort(E[] arr) {
        //循环不变量 arr[0,i)已排序，arr[i,n)未排序
        for (int i = 0; i < arr.length; i++) {
            int minIndex = i;
            //选择arr[i...n)中最小值的索引
            for (int j = i + 1; j < arr.length; j++) {
                minIndex = arr[j].compareTo(arr[minIndex]) < 0 ? j : minIndex;
            }
            SortingHelper.swap(arr, i, minIndex);
        }
    }

    public static void main(String[] args) {
        int[] dataSize = {10000, 100000};
        for (int n : dataSize) {
            Integer[] arr = ArrayGenerator.generatorRandomArray(n, n);
            SortingHelper.sortTest(SelectionSort.INSTANCE, arr);
        }
    }

}

学习收获

今天学习并总结了选择排序法和插入排序法