算法算法

每周一篇算法03:排序算法

2018-11-04  本文已影响740人  千淘萬漉

戳这里【总目录】回到算法系列总目录


排序算法是接触最多也是考察最多的一个知识点,最常用的:冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序、桶排序。其中可以按照时间复杂度把冒泡和插入归并为O(n^2)一类,归并和快排归并为O(n*log(n))一类,后三者归为O(n)一类。

分析排序算法主要从执行效率、内存消耗和稳定性三个角度去衡量,执行效率就是常说的时间复杂度,内存消耗主要说的是空间复杂度,这里还引入了一个原地排序概念(就是特指空间复杂度是 O(1) 的排序算法,可以理解为就在原内存空间上做数值交换),稳定性则是考虑待排序的序列中存在值相等的元素,经过排序之后,相等元素之间原有的先后顺序不变。

一、冒泡or插入

1.冒泡排序
冒泡排序的基本思想是,对相邻的元素进行两两比较,顺序相反则进行交换,这样,每一趟会将最小或最大的元素“浮”到顶端,最终达到完全有序。冒泡排序是只涉及相邻数据的交换操作,只需要常量级的临时空间,所以它的空间复杂度为O(1),是一个原地排序算法。相同大小的数据在排序前后不会改变顺序,所以冒泡排序是稳定的排序算法。最好情况时间复杂度是 O(n),最坏情况时间复杂度为 O(n^2)

冒泡图解
下面给出go实现demo:
import "fmt"

func main() {
    values := []int{4, 93, 84, 85, 80, 37, 81, 93, 27,12}
    fmt.Println(values)
    bubbleSort(values)
}

//冒泡排序(排序10000个随机整数,用时约145ms)  
func bubbleSort(nums []int) {  
    for i := 0; i < len(nums); i++ {  
        for j := 1; j < len(nums)-i; j++ {  
            if nums[j] < nums[j-1] {  
                //交换  
                nums[j], nums[j-1] = nums[j-1], nums[j]  
            }  
        }  
    }  
}

【golang实现冒泡排序】

2.插入排序
直接插入排序基本思想是每一步将一个待排序的记录,插入到前面已经排好序的有序序列中去,直到插完所有元素为止。实现时,不需要额外开辟新数组,只需在原地基础上先寻找需要插入的位置,将插入位置后的元素顺序后移一位,最后才将数据插入目标位置。同样的,插入排序是一个稳定的原地排序算法,时间复杂度上和冒泡排序一致。

插入排序

下面仍然给出go实现的demo:

//插入排序(排序10000个整数,用时约30ms)  
func insertSort(arr []int) {
    for i := 1; i < len(arr); i++ {
        value := arr[i]
        j := i - 1
        //查找插入的位置
        for ; j >= 0; j-- {
            if (arr[j] > value) {
                arr[j+1] = arr[j]
            } else {
                break
            }
        }
        //插入数据
        arr[j+1] = value
    }
}

3.为什么更推荐插入排序方法?
同等情况下,插入排序比冒泡排序效果更好,冒泡交换要比插入交换的数据移动要复杂,冒泡排序需要3个赋值操作,而插入排序只需要 1 个。这种情况在数据量较大的情况下对比会比较明显,同等大数据量的排序算法下插入会比冒泡省1/3的时间。

//冒泡排序中数据的交换操作:
if (a[j] > a[j+1]) { // 交换
   int tmp = a[j];
   a[j] = a[j+1];
   a[j+1] = tmp;
   flag = true;
}

//插入排序中数据的移动操作:
if (a[j] > value) {
  a[j+1] = a[j];  // 数据移动
} else {
  break;
}

二、归并or快排

归并排序和快速排序是两种稍微复杂的排序算法,它们用的都是分而治之的思想,代码通过递归来实现,过程非常相似。归并排序的重点是递推和 merge() 合并函数,而快排的重点递推公式和 partition() 分区函数。归并排序算法是一种在任何情况下时间复杂度都比较稳定的排序算法,但也使之存在致命的缺点,归并排序不是原地排序算法,空间复杂度比较高,是 O(n),数据量大的情况下就很容易消耗内存空间,因此通常情况下这二者之间快速排序的应用更加广泛,这里也主要学习快速排序算法。

图引自《极客时间-数据结构与算法之美》
快速排序的思路是通过递推和partition() 分区函数,partition()方法的目的在于实现了一个原地移动的方法,有点类似选择排序。通过游标 iA[p…r-1] 分成两部分。A[p…i-1] 的元素都是小于 pivot 的,其为“已处理区间”,A[i…r-1] 是“未处理区间”。每次都从未处理的区间 A[i…r-1] 中取一个元素 A[j],与 pivot 对比,如果小于pivot,则将其加入到已处理区间的尾部,也就是 A[i] 的位置。
func main(){
    arr := []int{41, 24, 76, 11, 45, 64, 21, 69, 19, 36}
    fmt.Println("before sort:")
    show(arr)
    quckSort(arr, len(arr))
    fmt.Println("after sort:")
    show(arr)
}

//sort method, arr is array and n is lenth of arr
func quckSort(arr []int, n int){
    quick_sort_re(arr,0,n-1)
}

//quick_sort_re sort method, sorted by recursion
func quick_sort_re(arr []int, p , r int){
    if p>=r {
        return
    }
    q:=partition(arr,p,r)
    quick_sort_re(arr,p,q-1)
    quick_sort_re(arr,q+1,r)
}

//partition method
func partition(arr []int,p,r int) int{
    pivot:=arr[r]
    i:=p
    for j:=p;j<=r-1;j++{
        if arr[j]<pivot{
            swap(arr,i,j)
            i++
        }
    }
    swap(arr,i,r)
    return i
}

//swap method 
func swap(arr []int,i,j int){
    arr[i],arr[j] = arr[j],arr[i]
}

// foreach print the array
func show(arr []int) {
    for _, value := range arr {
        fmt.Printf("%d\t", value)
    }
    fmt.Println()
}

快排是一种原地、不稳定的排序算法。快速排序算法虽然最坏情况下的时间复杂度是O(n^2),但是平均情况下时间复杂度都是O(nlogn)。不仅如此,快速排序算法时间复杂度退化到 O(n^2) 的概率非常小。

【图解数据结构——排序】包含各种排序算法的对比
【go语言实现快速排序】
【图解排序算法(一)之3种简单排序(选择,冒泡,直接插入)】

上一篇 下一篇

猜你喜欢

热点阅读