目录

一、总体分类

1、内部排序

2、外部排序

二、算法思想概述

1、内部排序

1.1插入排序

（1）直接插入排序

（2）希尔排序（缩小增量排序）

1.2选择排序

（1）简单选择排序

（2）堆排序

1.3交换排序

（1）冒泡排序

（2）快速排序

1.4归并排序（二路归并排序）

1.5基数排序

三、算法的稳定性

一、总体分类

1、内部排序

内部排序概念：

是指待排序列完全存放在内存中所进行的排序过程，整个过程只是在内存中完成。

1.1插入排序

①直接插入排序

②希尔排序

1.2选择排序

①简单选择排序

②堆排序

1.3交换排序

①冒泡排序

②快速排序

1.4归并排序

1.5基数排序

2、外部排序

外部排序概念：

是指大文件的排序，即待排序的记录存储在外存，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，才能完成排序。

2.1多路归并排序

2.2置换—选择排序

2.3最佳归并树（哈夫曼树）

二、算法思想概述

1、内部排序

1.1插入排序

（1）直接插入排序

算法思想：每趟将一个待排序的关键字按照其值的大小插入到已经排好的部分有序序列的适当位置上，直到所有待排关键字都被插入到有序序列中为止。

时间复杂度：O(n²)

（2）希尔排序（缩小增量排序）

算法思想：将待排序列按增量的选取规则分为几个子序列，分别对这几个子序列进行直接插入排序。然后继续将上一次选取出来的增量按照规则继续选取增量，并将上一次排序后的序列继续分组，分成几个子序列后继续进行直接插入排序，这样循环，直至增量选取为1时停止。此时序列大致有序，只需简单调整即可。

增量的选取规则：每次将序列的长度除以2并向下取整，所得的值即为增量。

时间复杂度：O(n²)

例如：

增量为1，就是直接插入排序。

增量为2，就是下标为0，2，4，6，8 、、、的关键字分为一组，

                下标为1，3，5，7，9 、、、的关键字为另一组。

增量为5，就是下标为0，5，10，15 、、、的关键字分为一组，

                下标为1，6，11，16 、、、的为一组，

                下标为2，7，12，17 、、、的为一组，等等。

即增量为n，则每隔n-1设一个关键字，把序列分为n组子序列。

1.2选择排序

（1）简单选择排序

算法思想：从头到尾顺序扫描序列，找出最小的一个关键字，然后和第一个关键字交换，接着从剩下的关键字中继续扫描找出最小的一个关键字，再与剩下的这些关键字的第一个关键字交换，直到序列有序。

时间复杂度：O(n²)

（2）堆排序

算法思想：首先将关键字按从上到下从左到右的顺序来建一棵完全二叉树，然后将该完全二叉树调整为大顶堆（或小顶堆），每次调整完之后取下根节点，然后取最下层最右边的结点填充过去，继续调整为大顶堆（或小顶堆）。如此循环，直到取完所有关键字，每次取下的根节点按顺序列出即可得到一个有序序列。

大顶堆：每个父节点的值都大于或等于其孩子节点的值。

小顶堆：每个父节点的值都小于或等于其孩子节点的值。

如何将初始无序的完全二叉树调整为大顶堆或小顶堆？

首先找到最后一个非叶节点，从它开始由右至左，由下至上，对每个结点进行调整。具体调整的是将当前非叶节点与其孩子节点作比较，如果存在大于当前父节点的孩子节点，则相交换，直到父节点比它的孩子节点都大，然后按顺序继续比较其他非叶节点。

时间复杂度：O(nlogn)

1.3交换排序

（1）冒泡排序

算法思想：首先第一个关键字和第二个关键字比较，如果前者大，则二者交换，否则不交换，然后第二个关键字和第三个关键字比较，一直这样进行下去，最终最大的关键字被交换到了最后，这样一趟冒泡排序完成，经过多趟这样的排序，直到一趟排序中没有发生交换，此时便结束，整个序列有序。

时间复杂度：O(n²)

（2）快速排序

算法思想：通过多次划分实现排序，每一趟选择当前所有子序列中的一个关键字（通常是第一个）作为枢轴。

设i和j分别指向头、尾指针，以第一个数作为枢轴，首先j从后往前扫描，当遇到比枢轴小的关键字时，将j此时对应的数和i此时对应的数交换，然后i开始从前往后扫描，当遇到比枢轴大的关键字时，将i此时对应的数和j此时对应的数交换，一直如此交替，直到i和j相遇，扫描结束，此时序列以枢轴关键字为中心可分为两个子序列，按同样的方法对子序列继续划分，直至整个序列有序。

注意：

①交换过程中，可以划掉枢轴，空出其位置，直到扫描结束i和j相遇时，再将枢轴填到i和j相遇的位置。

②序列越无序，效率越高，反之效率越低。

时间复杂度：

①最好情况下为O(nlogn)

②最坏情况下为O(n²)

③平均情况下为O(nlogn)

1.4归并排序（二路归并排序）

算法思想：以原始序列含7个关键字为例，首先将序列看成7个含有一个关键字的子序列，然后两两归并，形成若干个有序二元组，最后一个没有归并对象，单独一个组，之后继续两两归并，形成若干个有序的四元组，直到归并完全部的关键字，形成一个有序七元组。

时间复杂度：O(nlogn)

1.5基数排序

算法思想：若分配的是数字，数字范围是0~9，所以需假设有10个桶来放关键字，每个桶分别代表0，1，2，3 、、、9，然后所有数字要位数相同，不够用0来补（如12，补为012），以三位数为例（原始序列中，位数最长的关键字是三位数），需要进行三次分配，第一次按个位分配，个位是几就放入几号桶，全部放完之后，从0号桶开始按顺序取出桶内的数，注意如果一个桶内放了多个关键字，则要按先进先出的原则取出桶内的关键字。第二次按十位分配，原理同上，第三次按百位分配，最后按原则取出关键字后即可得到一个有序序列。

三、算法的稳定性

排序前后相同关键字的次序（相对位置）若一致则稳定，不一致则不稳定。

（1）稳定的有：冒泡排序、直接插入排序、归并排序、基数排序

（2）不稳定的有：快速排序、希尔排序、堆排序、简单选择排序

最后

以上就是细腻月亮为你收集整理的数据结构排序算法总结一、总体分类二、算法思想概述三、算法的稳定性的全部内容，希望文章能够帮你解决数据结构排序算法总结一、总体分类二、算法思想概述三、算法的稳定性所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。