插入排序与冒泡排序

记录插入排序及其改进算法、希尔排序、冒泡排序，及插入排序与冒泡排序的对比。

插入排序

以升序为例。

没有元素或只有一个元素时，默认就是有序的。
排序过程中，数组分为两部分：前一部分是有序的，后一部分是乱序的。
从乱序部分每次选取前面的一个元素，插入到有序部分。直到所有元素都有序。
1. 从乱序部分每次选取最前面的一个元素v，其下标为i。
2. 在有序部分从右往前查找第一个小于等于v的元素，其下标为j。
3. 在查找的过程中，把所有大于v的元素后移一个位置。
4. 把v插入到位置j+1。


func InsertSort(arr []int) {
    for i, end := 1, len(arr); i < end; i++ {
        j := i - 1
        v := arr[i]

        for ; j >= 0 && arr[j] > v; j-- {
            arr[j+1] = arr[j]
        }

        arr[j+1] = v
    }
}

插入排序改进

插入排序主要有两个操作：在有序部分查找合适的插入位置，在查找过程中移动元素。

在有序数组中查找时，如果使用顺序查找，则时间复杂度是O(n)；所以可以使用时间复杂度为O(lg(n))的折半查找来改进。

在移动元素时，目前都是一次只移动一个位置。希尔排序在这方面进行了改进。

带折半查找的插入排序

在合适的插入位置时，以从左往右的方向看，是要找第一个大于目标元素v的元素。

l, r 分别为指向有序部分的第一个和最后一个元素的指针，当中值元素arr[mid] > v时，可以认为mid之前还有元素大于v；否则，可以认为mid之后还有元素小于等于v。当l大于r时，l即为要找的位置。

实现


 func InsertSortWithBinarySearch(arr []int) {
     for i, end := 1, len(arr); i < end; i++ {
         v := arr[i]
         l, r := 0, i-1                                    //  l, r 分别为指向有序部分的第一个和最后一个元素的指针
         for l <= r {
             mid := l + (r-l)/2                         // 避免溢出，(l+r)/2可能产生溢出。
             if arr[mid] > v {
                 r = mid - 1                              //  认为mid之前还有元素大于v
             } else {
                 l = mid + 1                              //  认为mid之后还有元素小于等于v
             }
         }
         if l < i {
             util.ArrayCopy(arr, l, arr, l+1, i-l)     //  l+1的1表示后移一个元素，i-l 表示需要移动的元素数量
             arr[l] = v
         }
     }
}

注意：这个算法并没有减少移动元素的次数，只是减少了查找元素的比较次数。

希尔排序

希尔排序是插入排序的一种改进，基于：当数组基本有序时，插入排序进行查找和移动操作都是高效的，它把每隔固定间隔的元素当作一个子数组进行插入排序，逐步缩小间隔，最后对整个数组进行插入排序。

子数组间隔的选取不能含有公共的因子，否则会在某个间隔上重复进行排序，一般选取质数作为间隔。最后一个间隔必须是1。

希尔排序的时间复杂度是很复杂的，不仅与输入有关，还取决于不同间隔数组的选择。

实现


func GetSkipTable() []int {
    return []int{19, 13, 7, 5, 3, 1}
}

func ShellSort(arr []int) {
    limit := len(arr)
    for _, jmp := range GetSkipTable() {
        for i := jmp; i < limit; i += jmp {
            j, v := i-jmp, arr[i]
            for ; j >= 0 && arr[j] > v; j -= jmp {
                arr[j+jmp] = arr[j]
            }
            arr[j+jmp] = v
        }
    }
}

冒泡排序

以升序为例：

数组也分为两部分：前面的是乱序的（US），默认是整个数组；后面的是有序的（S），默认是空的。
遍历US，对于相邻的两个元素，如果前面的比后面的大，则交换两个值。
这样，在遍历完整个US时，US的最大元素将被交换至US底部，称为S的一部分，US的数量减一。
循环直至US为空。


func BubbleSort(arr []int) {
    for i, end := 0, len(arr); i < end; i++ {
        for j, innerEnd := 1, end-i; j < innerEnd; j++ {
            if arr[j] < arr[j-1] {
                util.Swap(arr, j, j-1)
            }
        }
    }
}

冒泡排序的改进

在遍历US时，如果整个遍历过程没有了交换操作，说明整个US已经是有序的了，可以提前结束。


func BubbleSortImprove(arr []int) {
    for i, end := 0, len(arr); i < end; i++ {
        isSwaped := false
        for j, innerEnd := 1, end-i; j < innerEnd; j++ {
            if arr[j] < arr[j-1] {
                util.Swap(arr, j, j-1)
                isSwaped = true
            }
        }
        if !isSwaped {
            return
        }
    }
}