内排序

所谓排序

就是把对元素进行比较然后移动他们

然后形成递增或者递减的序列


插入排序算法是所有排序算法里最简单了

这里分类进行介绍

直接插入排序

对表内的元素依次作为关键字插入到有序表

用顺序查找算法在有序表中寻找要插入的位置

然后插入元素

例:3 1 7 5 2 4 9 6 升序排列

我们从3开始,把3作为关键字

3比1大所以插入到1的右侧,注意此时3是另一张(有序)表里的元素了

1比有序表中的3小所以插入3的左侧

7比有序表中的3大所以插入3的右侧

5比有序表中的7小比3大所以插入7的左侧

。。。。。以此类推

折半插入排序

相比直接排序,把查找的方法换成了二分法而已

希尔排序

先将整个记录表分割成若干部分,分别进行直接插入排序

然后再对整个记录表进行一次直接插入排序

一般在记录的数量多的情况下,希尔排序的排序效率较直接插入排序高


交换排序(冒泡排序)

经典的排序算法了

以前我们也学过

有多少个元素就要冒泡多少次

所有元素都按照升序的时候冒泡就结束了


快速排序

冒泡排序的改进版

通过一次排序将整个无序表分成相互独立的两部分

其中一部分中的数据都比另一部分中包含的数据的值小

重复直到每一个小部分不可再分得到的就是有序的了

{49,38,65,97,76,13,27,49}

我们需要先选取一个枢轴,一般选第一个例如49

把大于49的放到49右边,小于49的放到49左边(按顺序)

得到27,38,13,49,65,97,76,49

将整个无序表分割成了两个部分,分别为{27,38,13}{65,97,76,49}

前半部分用27作为枢轴排序,后半部分则是65

{13,27,38},此部分已经有序,后部分为{49,65,97,76}

所以后部分再来一次以65

再来一次以97

最后才得到{13,27,38}{49}{49}{65}{76,97}


简单选择排序

一句话概括,每一次挑一个最小的和第i个位置进行交换

第1次挑一个最小的和第一个位置交换,第2次在剩下的挑最小的和第二个位置交换

以此类推


树形选择排序

利用完全二叉树中节点的关系进行筛选

所有记录采取两两分组,筛选出较小(较大)的值

然后从筛选出的较小(较大)值中再两两分组选出更小(更大)值

依次类推,直到最后选出一个最小(最大)值

同样可以采用此方式筛选出次小(次大)值等


堆排序

首先要明确堆的概念是什么

  • ki ≤ k2i 且 ki ≤ k2i+1(在 n 个记录的范围内,第 i 个关键字的值小于第 2*i 个关键字,同时也小于第 2*i+1 个关键字)
  • ki ≥ k2i 且 ki ≥ k2i+1(在 n 个记录的范围内,第 i 个关键字的值大于第 2*i 个关键字,同时也大于第 2*i+1 个关键字)

n个元素的序列只要满足其一就叫做堆

也可以使用完全二叉树来解释

因为在完全二叉树中第 i 个结点的左孩子恰好是第 2i 个结点

右孩子恰好是 2i+1 个结点


归并排序

如图,把每个元素都视作单独的个体

然后两两合成,同时进行排序

直到最后重新合成一个整体


基数排序

我们数据的位数不一定都是相同的

个十百千,由低到高对数据进行筛选,被称为最低位优先法LSD

千百个十,由高到低对数据进行筛选,被称为最高位优先法MSD

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注