排序算法对比、总结(Python代码)

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

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

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

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

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

4、归并排序

5、基数排序

对比

冒泡排序

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

2.过程:

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

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

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

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

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.过程:

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]挖出再填到上一个坑中。

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]。

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

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),它也是不稳定排序。首先简单了解下堆结构。

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

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

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

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

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

堆排序基本思想及步骤

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

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

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

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

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

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

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

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

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

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

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

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

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)的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之)。

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

合并相邻有序子序列

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

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 ],那么其排序的过程就如下两幅所示。

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

基数排序过程图-1

基数排序过程图-2

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

原文发布于微信公众号 - 人工智能LeadAI(atleadai)

原文发表时间:2018-03-22

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏目标检测和深度学习

排序算法算法对比

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

35760
来自专栏IT杂记

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

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

35880
来自专栏机器学习算法与Python学习

动画+原理+代码,解读十大经典排序算法

排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。常见...

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

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

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

9140
来自专栏Python小白进阶之旅

Python基本的排序算法比较,sorted的实现方法

简介:依次检查需要排序的列表,每次取出一个元素放入另一个排好序的列表中的适当位置。

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

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

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

32550
来自专栏云霄雨霁

排序算法总结

13800
来自专栏chenjx85的技术专栏

leetcode-162-寻找峰值

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

23430
来自专栏我的技术专栏

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

42530
来自专栏趣谈编程

希尔排序

21560

扫码关注云+社区

领取腾讯云代金券