插入排序与冒泡排序

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

插入排序

以升序为例。

  1. 没有元素或只有一个元素时,默认就是有序的。
  2. 排序过程中,数组分为两部分:前一部分是有序的,后一部分是乱序的。
  3. 从乱序部分每次选取前面的一个元素,插入到有序部分。直到所有元素都有序。
    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
        }
    }
}

冒泡排序

以升序为例:

  1. 数组也分为两部分:前面的是乱序的(US),默认是整个数组;后面的是有序的(S),默认是空的。
  2. 遍历US,对于相邻的两个元素,如果前面的比后面的大,则交换两个值。
  3. 这样,在遍历完整个US时,US的最大元素将被交换至US底部,称为S的一部分,US的数量减一。
  4. 循环直至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
        }
    }
}

插入排序与冒泡排序的对比

  1. 两者的时间复杂度最差都是O(n^2),最好都是O(n)。
  2. 插入排序可以利用在已经有序部分上使用折半查找来加速查找插入位置。
  3. 冒泡排序可以利用冒泡过程是否有交换操作来判断是否已经有序。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据