常见排序算法及对应的时间复杂度和空间复杂度

  • 时间:
  • 浏览:1
  • 来源:uu直播快3_UU快3直播平台

image.png

图片

初始序列:46,79,56,38,40,84

建堆:

java实现

排序大的分类不能分为一种生活:内排序和外排序。在排序过程中,删剪记录存上放内存,则称为内排序,或者 排序过程中前要使用外存,则称为外排序。下面讲的排序都在属于内排序。

实例

基本思想:在要排序的一组数中,选出最小的有另四个数与第有另四个位置的数交换;或者 在剩下的数当中再找最小的与第5个位置的数交换,没办法 循环到倒数第5个数和最后有另四个数比较为止。

实例:

:

排序算法经过了很长时间的演变,产生了统统种不同的办法。对于初学者来说,对它们进行整理便于理解记忆显得很重要。每种算法都在它特定的使用场合,没办法 通用。或者 ,亲戚亲戚大伙很有必要对所有常见的排序算法进行归纳。

基本思想:

堆排序是一种生活树形取舍排序,是对直接取舍排序的有效改进。

image.png

基本思想:取舍有另四个基准元素,通常取舍第有另四个元素或者 最后有另四个元素,通过一趟扫描,将待排序列分成两每种,一每种比基准元素小,一每种大于等于基准元素,此时基准元素在其排好序后的正确位置,或者 再用同样的办法递归地排序划分的两每种。

实例:

image.png

image.png

基本思想:在要排序的一组数中,对当前还未排好序的范围内的删剪数,自上而下对相邻的有另四个数依次进行比较和调整,让较大的数往下沉,较小的往上冒。即:每当两相邻的数比较后发现它们的排序与排序要求相反时,就将它们互换。

实例

基本思想:二分法插入排序的思想和直接插入一样,统统我找合适的插入位置的办法不同,这里是按二分法找到合适的位置,不能减少比较的次数。

实例:

基本思想:将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。或者 ,从最低位完后 刚现在开始,依次进行一次排序。原本从最低位排序老会 到最高位排序完成完后 ,数列就变成有另四个有序序列。

实例

基本思想:每步将有另四个待排序的记录,按其顺序码大小插入到前面或者 排序的字序列的合适位置(从后向前找到合适位置后),直到删剪插入排序完为止。

实例

基本思想:先取有另四个小于n的整数d1作为第有另四个增量,把文件的删剪记录分成d有另四个组。所有距离为d1的倍数的记录上放同有另四个组中。先在各组内进行直接插入排序;或者 ,取第5个增量d2

java代码:

image.png

image.png

基本思想:归并(Merge)排序法是将有另四个(或有另四个以上)有序表合并成有另四个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。或者 再把有序子序列合并为整体有序序列。

实例

交换,从堆中踢出最大数:

文章参考:https://blog.csdn.net/gane_cheng/article/details/52652705

image.png

image.png

思想:初始时把要排序的数的序列看作是一棵顺序存储的二叉树,调整它们的存储序,使之成为有另四个堆,这时堆的根节点的数最大。或者 将根节点与堆的最后有另四个节点交换。或者 对前面(n-1)个数重新调整使之成为堆。依此类推,直到没办法 有另四个节点的堆,并对它们作交换,最后得到有n个节点的有序序列。从算法描述来看,堆排序前要有另四个过程,一是建立堆,二是堆顶与堆的最后有另四个元素交换位置。统统堆排序有有另四个函数组成。一是建堆的渗透函数,二是反复调用渗透函数实现排序的函数。

image.png

:

堆的定义下:具有n个元素的序列 (h1,h2,…,hn),当且仅当满足(hi>=h2i,hi>=2i+1)或(hi<=h2i,hi<=2i+1) (i=1,2,…,n/2)时称之为堆。在这里只讨论满足前者条件的堆。由堆的定义不能看出,堆顶元素(即第有另四个元素)必为最大项(大顶堆)。删剪二叉树不能很直观地表示堆的社会形态。堆顶为根,其它为左子树、右子树。

java实现

:

内排序有不能分为以下几类:

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

  (2)、取舍排序:直接取舍排序、堆排序。

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

  (4)、归并排序

  (5)、基数排序

image.png

[TOC]

1、插入排序

1.1直接插入排序(从后向前找到合适位置后插入)

1.2 二分法插入排序

1.3 希尔排序

2、取舍排序

2.1 直接取舍排序

2.2 堆排序

3、交换排序

3.1 冒泡排序

3.2快速排序

4、 归并排序

5、基数排序