这里只讲 QuickSort(快排)、HeapSort(堆排)、MergeSort(归并)、ShellSort(希尔)。

首先是各个排序算法的时间空间复杂度。(不是我做的…)

排序算法

然后会讲Shell排序、堆排序、快速排序、归并排序。

 

先讲快速排序吧:

快速排序是找出一个元素(理论上可以随便找一个)作为基准(pivot),然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值 都不小于基准值,如此作为基准的元素调整到排序后的正确位置。

递归快速排序,将其他n-1个元素也调整到排序后的正确位置。

最后每个元素都是在排序后的正 确位置,排序完成。

所以快速排序算法的核心算法是分区操作,即如何调整基准的位置以及调整返回基准的最终位置以便分治递归。

代码如下:

 

 

堆排序:

在我眼里就是三步,建堆,交换,调整

建堆是从下到上调整为大根堆或者小根堆(即从最后一个非叶子节点开始),若用数组存储,则最后一个非叶子节点应该是size/2。例如:12345,他们的下标是01234,size=5,最后一个非叶子节点是2。

调整节点的过程如下:先判断左右子树大小,如果左子树小于或大于右子树,则用右子树的值和节点的值进行交换,然后再调整用来交换的子树,比如刚才交换的是左子树和节点,则调整左子树,否则调整右子树。

代码如下:

 

归并排序:

分治法,先排序左边,再排序右边,再合并。

归并排序

代码如下:

 

最后是Shell排序,又叫缩小增量排序法…

算法思想:将待排序的序列分割成若干个子序列,分别进行插入排序。

 

大致就是这四个…效率比较高的…我一般喜欢归并,因为效率高,思路简单…

【Sort】排序算法小结.
Tagged on:     
0 0 vote
Article Rating
订阅
提醒
0 评论
Inline Feedbacks
View all comments