快速排序

func sortArray(nums []int) []int {
    var quick_sort func(nums []int,l,r int)
    quick_sort=func(nums []int,l,r int){
        if l>=r{
            return 
        }
        //这x取l、r、(l+r)>>1都行。下面用i来区分边界的时候，这不能写l！！！！否则有边界问题，会死循环，死循环样例1 2
        x,i,j:=nums[l],l-1,r+1

        for i<j{
            //golang模拟do while写法
            // var _tk=true
            // for _tk||nums[i]<x{
            //     _tk=false
            //     i++
            // }
            for i++;nums[i]<x;{
                i++
            }
            for j--;nums[j]>x;{
                j--
            }
            if i<j{
                nums[i],nums[j]=nums[j],nums[i]
            }
        }
        //或者
        // quick_sort(nums,l,i-1)
        // quick_sort(nums,i,r)
        
        quick_sort(nums,l,j)
        quick_sort(nums,j+1,r)
    } 
    quick_sort(nums,0,len(nums)-1)
    return nums
}

• 时间复杂度：平均情况O（nlogn），最好O（nlogn），最坏O（n^2）

• 最佳情况：T(n) = O(nlogn)，快速排序最优的情况就是每一次取到的元素都刚好平分整个数组
• 最差情况：T(n) = O(n²)，最差的情况就是每一次取到的元素就是数组中最小/最大的，这种情况其实就是冒泡排序了(每一次都排好一个元素的顺序)
• 平均情况：T(n) = O(nlogn)
• 稳定性：不稳定

归并排序

func sortArray(nums []int) []int {
    t:=make([]int,len(nums))
    var MergeSort func(l,r int)
    MergeSort=func(l,r int){
        if l>=r{
            return 
        }
        
        mid:=(l+r)>>1
        MergeSort(l,mid)
        MergeSort(mid+1,r)
        i,j,k:=l,mid+1,0
        for i<=mid&&j<=r{
           if nums[i]<nums[j]{
               t[k]=nums[i]
               i,k=i+1,k+1
           }else{
               t[k]=nums[j]
               j,k=j+1,k+1
           }
        }
        for ;i<=mid;i,k=i+1,k+1{
            t[k]=nums[i]
        }
        for ;j<=r;j,k=j+1,k+1{
            t[k]=nums[j]
        }
        for i,k=l,0;i<=r;i,k=i+1,k+1{
            nums[i]=t[k]
        }
    }
    MergeSort(0,len(nums)-1)
    return nums
}

• 时间复杂度：最好最坏平均都是O（nlogn）

总结

原文地址：http://www.cnblogs.com/JujunWang/p/16910585.html