排序算法算法对比

排序大的分类可以分为两种:内排序和外排序。在排序过程中,全部记录存放在内存,则称为内排序,如果排序过程中需要使用外存,则称为外排序。下面讲的排序都是属于内排序。

内排序有可以分为以下几类:

1、插入排序:直接插入排序、二分法插入排序、希尔排序。

2、选择排序:直接选择排序、堆排序。

3、交换排序:冒泡排序、快速排序。

4、归并排序

5、基数排序

对比

61520931627_.pi

冒泡排序

1.基本思想:两个数比较大小,较大的数下沉,较小的数冒起来。

2.过程:

比较相邻的两个数据,如果第二个数小,就交换位置。

从后向前两两比较,一直到比较最前两个数据。最终最小数被交换到起始的位置,这样第一个最小数的位置就排好了。

继续重复上述过程,依次将第2.3...n-1个最小数排好位置。

image

3.平均时间复杂度:O(n2)

4.优化:

针对问题:

数据的顺序排好之后,冒泡算法仍然会继续进行下一轮的比较,直到arr.length-1次,后面的比较没有意义的。

方案:

设置标志位flag,如果发生了交换flag设置为true;如果没有交换就设置为false。

这样当一轮比较结束后如果flag仍为false,即:这一轮没有发生交换,说明数据的顺序已经排好,没有必要继续进行下去。

5.Python代码实现:

@staticmethoddef bubble_sort(arr):
    for i in range(len(arr)):
        not_change = True
        for j in range(len(arr) - 1, i - 1, -1):           
if arr[j] < arr[j - 1]:
                tmp = arr[j]
                arr[j] = arr[j - 1]
                arr[j - 1] = tmp
                not_change = False
        if not_change:            
break
return arr

选择排序

1.基本思想:

在长度为N的无序数组中,第一次遍历n-1个数,找到最小的数值与第一个元素交换;

第二次遍历n-2个数,找到最小的数值与第二个元素交换;

第n-1次遍历,找到最小的数值与第n-1个元素交换,排序完成。

2.过程:

image

3.平均时间复杂度:O(n2)

4.python代码实现:

@staticmethoddef select_sort(arr):
    for index in range(len(arr)):
        min_index = index        
for j in range(index + 1, len(arr)):            
if arr[j] < arr[min_index]:
                min_index = j        
if min_index != index:
            tmp = arr[index]
            arr[index] = arr[min_index]
            arr[min_index] = tmp    
return arr

插入排序

1.基本思想:

在要排序的一组数中,假定前n-1个数已经排好序,现在将第n个数插到前面的有序数列中,使得这n个数也是排好顺序的。如此反复循环,直到全部排好顺序。

2.过程:

image

image

3.平均时间复杂度:O(n2)

4.python代码实现:

@staticmethoddef insert_sort(arr):
    for index in range(len(arr) - 1):        
for j in range(index + 1, 0, -1):          
if arr[j] < arr[j - 1]:
               tmp = arr[j]
                arr[j] = arr[j - 1]
                arr[j - 1] = tmp            
else:                
break
    return arr

希尔排序

1.基本思想:

希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。

2.过程:

image

3.平均时间复杂度:O(n*logn)

4.python代码实现:

def shell_sort(arr):
    gap = len(arr)    
while True:
        gap = int(gap / 2)        
for arr_index in range(gap):
            print('arr_index:', arr_index)            
for element in range(arr_index, len(arr) - 1, gap):
                print('element:', element)                
for j in range(element, arr_index, -gap):                    
# print('j', j)
                    if arr[j] < arr[element - gap]:
                        tmp = arr[element - gap]
                        arr[element - gap] = arr[j]
                        arr[j] = tmp                    
else:                        
break
        if gap == 1:            
break
    return arr

快速排序

1.基本思想:(分治)

先从数列中取出一个数作为key值;

将比这个数小的数全部放在它的左边,大于或等于它的数全部放在它的右边;

对左右两个小数列重复第二步,直至各区间只有1个数。

2.过程

1)初始时 i = 0; j = 9; key=72 由于已经将a[0]中的数保存到key中,可以理解成在数组a[0]上挖了个坑,可以将其它数据填充到这来。

从j开始向前找一个比key小的数。当j=8,符合条件,a[0] = a[8] ; i++ ; 将a[8]挖出再填到上一个坑a[0]中。

这样一个坑a[0]就被搞定了,但又形成了一个新坑a[8],这怎么办了?简单,再找数字来填a[8]这个坑。

这次从i开始向后找一个大于key的数,当i=3,符合条件,a[8] = a[3] ; j-- ; 将a[3]挖出再填到上一个坑中。

image

2)此时 i = 3; j = 7; key=72 再重复上面的步骤,先从后向前找,再从前向后找。

从j开始向前找,当j=5,符合条件,将a[5]挖出填到上一个坑中,a[3] = a[5]; i++;

从i开始向后找,当i=5时,由于i==j退出。

此时,i = j = 5,而a[5]刚好又是上次挖的坑,因此将key填入a[5]。

image

3)可以看出a[5]前面的数字都小于它,a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了。

image

3.平均时间复杂度:O(N*logN)

4.Python代码实现:

def quick_sort(self, arr, left, right):
    if left >= right:        return
    key = arr[left]
    i = left
    j = right    while i < j:        
while i < j and arr[j] >= key:
            j -= 1
        if i < j:
            arr[i] = arr[j]
            i += 1
        while i < j and arr[i] < key:
            i += 1
        if i < j:
            arr[j] = arr[i]
            j -= 1

    arr[i] = key
    self.quick_sort(arr, left, i - 1)
    self.quick_sort(arr, i + 1, right)    
return arr

堆排序

堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为O(nlogn),它也是不稳定排序。首先简单了解下堆结构。

堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆;或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆。如下图:

image

同时,我们对堆中的结点按层进行编号,将这种逻辑结构映射到数组中就是下面这个样子

image

该数组从逻辑上讲就是一个堆结构,我们用简单的公式来描述一下堆的定义就是:

大顶堆:arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]

小顶堆:arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

堆排序基本思想及步骤

堆排序的基本思想是:将待排序序列构造成一个大顶堆,此时,整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换,此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆,这样会得到n个元素的次小值。如此反复执行,便能得到一个有序序列了。

步骤一 构造初始堆。将给定无序序列构造成一个大顶堆(一般升序采用大顶堆,降序采用小顶堆)。

image

假设给定无序序列结构如下

1、此时我们从最后一个非叶子结点开始(叶结点自然不用调整,第一个非叶子结点 arr.length/2-1=5/2-1=1,也就是下面的6结点),从左至右,从下至上进行调整。

image

2、找到第二个非叶节点4,由于[4,9,8]中9元素最大,4和9交换。

image

这时,交换导致了子根[4,5,6]结构混乱,继续调整,[4,5,6]中6最大,交换4和6。

image

步骤二 将堆顶元素与末尾元素进行交换,使末尾元素最大。然后继续调整堆,再将堆顶元素与末尾元素交换,得到第二大元素。如此反复进行交换、重建、交换。

3、将堆顶元素9和末尾元素4进行交换

image

4、重新调整结构,使其继续满足堆定义

image

5、再将堆顶元素8与末尾元素5进行交换,得到第二大元素8.

image

后续过程,继续进行调整,交换,如此反复进行,最终使得整个序列有序

501521032602_.pi

再简单总结下堆排序的基本思路:

a.将无需序列构建成一个堆,根据升序降序需求选择大顶堆或小顶堆;

b.将堆顶元素与末尾元素交换,将最大元素"沉"到数组末端;

c.重新调整结构,使其满足堆定义,然后继续交换堆顶元素与当前末尾元素,反复执行调整+交换步骤,直到整个序列有序。

代码实现:

@staticmethoddef heap_sort(arr):
    # 调整大顶堆(仅是调整过程,建立在大顶堆已构建的基础上)
    def adjuct_heap(array, index, length):
        # 先取出当前元素i
        temp = array[index]        
# 从i结点的左子结点开始,也就是2i + 1处开始
        k = index * 2 + 1
        while k < length:            
# 如果左子结点小于右子结点,k指向右子结点
            if k + 1 < length and array[k] < array[k + 1]:
                k += 1
            # 如果子节点大于父节点,将子节点值赋给父节点(不用进行交换)
            if array[k] > temp:
                array[index] = array[k]
                index = k            
else:               
break
            k = 2 * k + 1
        # 将temp值放到最终的位置
        array[index] = temp    
# 构建最大堆
    for i in range(int(len(arr) / 2 - 1), -1, -1):        
# 从第一个非叶子节点从下至上,从右至左调整结构
        adjuct_heap(arr, i, len(arr))    
for j in range(len(arr) - 1, -1, -1):
        tmp = arr[j]
        arr[j] = arr[0]
        arr[0] = tmp
        adjuct_heap(arr, 0, j)    
return arr

归并排序

归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之)。

image

可以看到这种结构很像一棵完全二叉树,本文的归并排序我们采用递归去实现(也可采用迭代的方式去实现)。分阶段可以理解为就是递归拆分子序列的过程,递归深度为log2n。

合并相邻有序子序列

来看看治阶段,我们需要将两个已经有序的子序列合并成一个有序序列,比如上图中的最后一次合并,要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列,合并为最终序列[1,2,3,4,5,6,7,8],来看下实现步骤。

image

image

Python代码:

def merge_sort(self, lists):
    def merge(left, right):
        i, j = 0, 0
        result = []        
while i < len(left) and j < len(right):            
if left[i] <= right[j]:
                result.append(left[I])
                i += 1
            else:
                result.append(right[j])
                j += 1
        result += left[I:]
        result += right[j:]        
return result   
# 归并排序
    if len(lists) <= 1:        
return lists
    num = int(len(lists) / 2)
    left = self.merge_sort(lists[:num])
    right = self.merge_sort(lists[num:])    
return merge(left, right)

基数排序

不需要直接对元素进行相互比较,也不需要将元素相互交换,你需要做的就是对元素进行“分类”。这也是基数排序的魅力所在,基数排序可以理解成是建立在“计数排序”的基础之上的一种排序算法。在实际项目中,如果对效率有所要求,而不太关心空间的使用时,我会选择用计数排序(当然还有一些其他的条件),或是一些计数排序的变形。

基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog(r)m),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的稳定性排序法。

如果我们的无序是 T = [ 2314, 5428, 373, 2222, 17 ],那么其排序的过程就如下两幅所示。

image

上面这幅图,或许你已经在其他的博客里见到过。这是一个很好的引导跟说明。在基数排序里,我们需要一个很大的二维数组,二维数组的大小是 (10 * n)。10 代表的是我们每个元素的每一位都有 10 种可能,也就是 10 进制数。在上图中,我们是以每个数的个位来代表这个数,于是,5428 就被填充到了第 8 个桶中了。下次再进行填充的时候,就是以十位进行填充,比如 5428 在此时,就会选择以 2 来代表它。

image

基数排序过程图-1

image

基数排序过程图-2

image

python代码:

@staticmethoddef radix_sort(lists, radix=10):
    # k = int(math.ceil(math.log(max(lists), radix)))
    k = radix
    bucket = [[] for i in range(radix)]    
for i in range(k):        
for j in lists:
            bucket[int(j / (radix ** (i - 1)) % (radix))].append(j)            
# bucket[int(j % (radix))].append(j)
        del lists[:]        
for z in bucket:
            lists += z            
del z[:]
        print(lists)    
return lists

参考链接: http://python.jobbole.com/82270/ https://www.jianshu.com/p/ae97c3ceea8d https://www.cnblogs.com/chengxiao/p/6194356.html

原文发布于微信公众号 - 目标检测和深度学习(The_leader_of_DL_CV)

原文发表时间:2018-04-11

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏IT杂记

求一个数组中子数组的最大和算法(Java实现)

    前几天在微信订阅号“待字闺中”中看到的一篇文章《小技巧求一个数组中子数组的最大和》,提供下Java的实现,并且在对题目做下小修改,本来打算直接在微信里直...

36280
来自专栏人工智能头条

写算法,用 C++ 还是用 Java ,差别大吗?

今天带来的文章,是 GitChat 签约作者王晓华在不断被读者吐槽:“好好一本算法书为什么要用 C++ 来写” 时,万般无奈下憋出来的。

36420
来自专栏用户2442861的专栏

从头到尾彻底理解KMP(2014年8月22日版)

作者:July 时间:最初写于2011年12月,2014年7月21日晚10点 全部删除重写成此文,随后的半个多月不断反复改进。

21030
来自专栏我的技术专栏

图说C++对象模型:对象内存布局详解

46730
来自专栏极客慕白的成长之路

视觉直观感受 7 种常用的排序算法

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。...

9340
来自专栏云霄雨霁

排序算法总结

14000
来自专栏chenjx85的技术专栏

leetcode-162-寻找峰值

给定一个输入数组 nums,其中 nums[i] ≠ nums[i+1],找到峰值元素并返回其索引。

24230
来自专栏python小白到大牛

安利一波Python编程中非常实用的那些黑魔法

编者按:Python是机器学习的主流语言,没有之一。今年5月,它首次在PYPL排行榜上超越JAVA,成为全球第一大编程语言。而一个月后,Stack Overfl...

14820
来自专栏PPV课数据科学社区

【学习】视觉直观感受 7 种常用排序算法

10月14日发布《统计世界的十大算法》后,很多朋友在后台询问,哪里有“视觉直观感受 7 种常用排序算法”,今天分享给大家,感谢todayx.org。 1. 快速...

32950
来自专栏ACM算法日常

How many integers can you find(容斥原理) - HDU 1796

看这题之前先复习一下容斥原理,不然肯定看不懂,呃,如果第一次接触容斥原理的题,可能弄懂了容斥原理你还是看不懂代码,是的,等会你就知道了。

10220

扫码关注云+社区

领取腾讯云代金券