选择排序和插入排序

0.排序中离不开两个方法

排序中最常用的就是比较和互换两个方法，为了简便，在此处提取出来

//交换
public static void exch(int[] arr,int i,int j){
  int temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}
//比较
public static boolean less(int x, int y){
  return x < y;
}

1.选择排序

1.1排序方式

1.找到数组中最小的元素，将它和数组的第一个元素交换位置。
2.在剩下的元素中找到最小的元素，将它与第二个元素交换位置
3.重复进行...

1.2实现

  public static void selectionSort(int[] arr) {
        int len = arr.length;
        for (int i = 0; i < len; i++) {
            int min = i;
            for (int j = i + 1; j < len; j++) {
                if (less(arr[j], arr[min])) {
                    min = j;
                }
            }
            exch(arr, i, min);
        }
    }

选择排序轨迹图.png

1.3复杂度

• 对于长度为N的数组，选择排序需要 N^2/2次比较和N次替换

1.4特点

• 优点：移动数据是最少的，只需要N次
• 缺点：花费时间与输入无关，一个升序的数组和一个倒序的数组所花费的时间是一样，因为此特点，下面来讲一下插入排序

2.插入排序

和选择排序不同的是，插入排序所需的时间取决于输入中元素的初始顺序。例如，对一个很大且其中已经有序（接近有序）的数组进行排序比对随机顺序或者逆序的数组进行排序要快的多。

2.1排序方式

索引 i 从1开始,依次比较i左侧相邻的元素(逆序)，如arr[i]与arr[i-1], arr[i-1]与arr[i -2]... 如果左侧的小于右侧的，就交换这两个元素，这样就保证了i左侧的元素都是有序的。
下一轮循环时，索引为i+1,由于上一次的排序导致i左侧的数据是有序的，所以只要找出i+1左侧需要交换的位置后，将元素插入此位置，就可以跳入到下一次循环了，即i+2

2.2实现

public static void insertSort(int[] arr){
        
        int len = arr.length;
        
        for(int i = 1; i < len; i++){
            for(int j = i; j > 0 && less(arr[j],arr[j-1]); j--){
                exch(arr,j,j-1);
            }
        }
    }

2.3复杂度

• 平均情况：N^2 /4次比较和N^2/4次交换
• 最差情况，如逆序的数组，N^2 /2次比较和N^2/2次交换
• 最好情况，如顺序的数组，N-1次比较和0次交换

2.4用二分查找优化插入排序

由于插入排序索引左侧的数组是有序的，可以考虑采用二分查找法减少比较次数，代码如下

public static void sort(int[] a) {
        int n = a.length;
        for (int i = 1; i < n; i++) {
            int v = a[i];
            int lo = 0, hi = i;
            while (lo < hi) {
                int mid = lo + (hi - lo) / 2; 
                if (less(v, a[mid])) hi = mid;
                else                 lo = mid + 1;
            }
            // insetion sort with "half exchanges"
            // (insert a[i] at index j and shift a[j], ..., a[i-1] to right)
            for (int j = i; j > lo; --j)
                a[j] = a[j-1];
            a[lo] = v;
        }
    }

4.对比

选择排序不会访问索引左侧的元素，插入排序不会访问索引右侧的元素，如下图所示：

对比.png

参考资料：https://algs4.cs.princeton.edu/21elementary/