十大排序算法（一）_换位法排序

目录

1.选择排序

2.冒泡排序

3.插入排序

3.1插入排序递归实现

4.希尔排序

5.归并排序

1.选择排序

算法步骤

1. 首先在未排序序列中找到最小元素，与排序序列的起始位置交换位置；
2. 再从剩余未排序元素中继续寻找最小元素放入到已排序序列的末尾；
3. 重复第二步，直到所有元素排序完毕。

由于每次排序操作需要比较次数都一样，所以无论什么数据进去都是O(n2)的时间复杂度。需要常数个外部内存，空间复杂度O(1)。不稳定。

 public static int[] sortSelect(int[] a){
        //遍历N-1次
        for (int i = 0; i < a.length - 1; i++) {
            int min = a[i];
            for (int j = i + 1; j < a.length; j++) {
                if (a[j] < min) {
                    min = a[j];
                    a[j] = a[i];
                    a[i] = min;
                }
            }
        }
        return a;

2.冒泡排序

算法步骤

1. 比较相邻的元素，如果前一个元素大于后一个元素，就交换这两个元素，对每一对相邻元素做同样的工作；
2. 针对所有元素重复上述的步骤。

冒泡每次都会让数列排序更为优化，多数情况下优于选择排序，当输入的数据已经是正序时，速度最快，输入反序时速度最慢，排完序之后相同元素相对次序一样（相等时不交换位置），算法稳定。时间复杂度O（n2），空间复杂度O（1）。

        public static int[] sortBubb(int[] a){
        //遍历N-1次
        boolean flag=true;//标记，判断无序时退出循环
        for (int i = 0; i < a.length - 1; i++) {