基础排序算法

Ⅰ 八大算法

算法中比较常用的有八种算法，基本算法的题，都是依靠这些基础算法或者结合使用出题的，所以要学会基础算法，才有可能去更好的掌握算法题。

插入排序，又叫直接插入排序。实际中，我们玩扑克牌的时候，就用了插入排序的思想。

基本思想：在待排序的元素中，假设前n-1个元素已有序，现将第n个元素插入到前面已经排好的序列中，使得前n个元素有序。按照此法对所有元素进行插入，直到整个序列有序。但我们并不能确定待排元素中究竟哪一部分是有序的，所以我们一开始只能认为第一个元素是有序的，依次将其后面的元素插入到这个有序序列中来，直到整个序列有序为止。

希尔排序，又称缩小增量法。其基本思想是：

 1>先选定一个小于N的整数gap作为第一增量，然后将所有距离为gap的元素分在同一组，并对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量，重复上述操作…

    2>当增量的大小减到1时，就相当于整个序列被分到一组，进行一次直接插入排序，排序完成。

选择排序，即每次从待排序列中选出一个最小值，然后放在序列的起始位置，直到全部待排数据排完即可。

如何进行堆排序呢？

步骤如下：

 1、将堆顶数据与堆的最后一个数据交换，然后对根位置进行一次堆的向下调整，但是调整时被交换到最后的那个最大的数不参与向下调整。

 2、完成步骤1后，这棵树除最后一个数之外，其余数又成一个大堆，然后又将堆顶数据与堆的最后一个数据交换，这样一来，第二大的数就被放到了倒数第二个位置上，然后该数又不参与堆的向下调整…反复执行下去，直到堆中只有一个数据时便结束。此时该序列就是一个升序。

冒泡排序，该排序的命名非常形象，即一个个将气泡冒出。冒泡排序一趟冒出一个最大（或最小）值。

快速排序是公认的排序之王，快速排序是Hoare于1962年提出的一种二叉树结构的交换排序算法，其基本思想为：

 任取待排序元素序列中的某元素作为基准值，按照该基准值将待排序列分为两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后左右序列重复该过程，直到所有元素都排列在相应位置上为止。

归并排序是采用分治法的一个非常典型的应用。其基本思想是：将已有序的子序合并，从而得到完全有序的序列，即先使每个子序有序，再使子序列段间有序。

计数排序，又叫非比较排序。顾名思义，该算法不是通过比较数据的大小来进行排序的，而是通过统计数组中相同元素出现的次数，然后通过统计的结果将序列回收到原来的序列中。

Ⅱ 基本排序算法原理

算法原理：每次对相邻的两个元素进行比较，若前者大于后者则进行交换，如此一趟下来最后一趟的就是最大元素，重复以上的步骤，除了已经确定的元素 。

算法原理：每次对相邻的两个元素进行比较，若前者大于后者则进行交换，如此一趟下来最后一趟的就是最大元素，重复以上的步骤，除了已经确定的元素

算法步骤

1)  设置两个变量i、j，排序开始的时候：i=0，j=n-1；

2）第一个数组值作为比较值，首先保存到temp中，即temp=A[0]；

3）然后j-- ,向前搜索,找到小于temp后,因为s[i]的值保存在temp中,所以直接赋值,s[i]=s[j]

4）然后i++,向后搜索,找到大于temp后,因为s[j]的值保存在第2步的s[i]中,所以直接赋值,s[j]=s[i],然后j--,避免死循环

5）重复第3、4步，直到i=j,最后将temp值返回s[i]中

6)  然后采用“二分”的思想,以i为分界线,拆分成两个数组 s[0,i-1]、s[i+1,n-1]又开始排序

排序图解

算法原理：从第一个元素开始，左边视为已排序数组，右边视为待排序数组，从左往右依次取元素，插入左侧已排序数组，对插入新元素的左侧数组重新生成有序数组 。需要注意的是，在往有序数组插入一个新元素的过程中，我们可以采用按 顺序循环 比较，也可以通过 折半查找法 来找到新元素的位置，两种方式的效率 取决于数组的数据量

算法原理：希尔排序也是利用插入排序的思想来排序。希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了，插入效率比较高。

排序图解

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

归并排序，顾名思义就是一种 “递归合并” 的排序方法（这个理解很重要）。对于一个数列，我们把它进行二分处理，依次递归下去，然后将小范围的数进行排序，最后将其合并在一起。就实现了归并排序。

这实际上是运用了 分治思想 ，显然，想要把一个数列排好序，最终达到的目的就是它的任何一部分都是有序的。这样的话，我们可以考虑分别把数列分成N多个部分，让每个部分分别有序，然后再将其统一，变成所有的东西都有序。这样就实现了排序。这个想法就叫分治思想。

排序图解

排序图解

Ⅲ 排序法的排序法的基本步骤

排序法是根据一些特定的标准（例如工作的复杂程度、对组织的贡献大小等对各个职位的相对价值）进行整体比较，进而将职位按照相对价值的高低排列出一个次序。其基本步骤是：
1、对排序的标准达成共识。虽然排序法是对岗位的整体价值进行评价而排序，但也需要参与评估的人员对什么样的“整体价值”更高达成共识，如责任更大，知识技能更高，工作更加复杂，环境因素恶劣等。
2、选定参与排序的职位。如果公司较小可以选取全部职位进行排序。
3、评定人员根据事先确定评判标准，对公司同类岗位的重要性逐一作出评判，最重要的排在第一位，次要的、再次要的顺次往下排列。
4、将经过所有评定人员评定的每个岗位的结果加以汇总，得到序号和。然后将序号和除以评定人数，得到每一岗位的平均序数。最后，按平均序数的大小，由小到大评定出各岗位的相对价值的次序。

Ⅳ vb三种基本排序算法

三种基本排序算法（与哪种编程语言无关）：
冒泡排序算法、选择排序算法、插入排序算法

Ⅳ 几种排序算法的比较

一、八大排序算法的总体比较

4.3、堆的插入：

每次插入都是将新数据放在数组最后。可以发现从这个新数据的父结点到根结点必然为一个有序的数列，然后将这个新数据插入到这个有序数据中

（1）用大根堆排序的基本思想

先将初始数组建成一个大根堆，此对为初始的无序区；

再将最大的元素和无序区的最后一个记录交换，由此得到新的无序区和有序区，且满足<=的值；

由于交换后新的根可能违反堆性质，故将当前无序区调整为堆。然后再次将其中最大的元素和该区间的最后一个记录交换，由此得到新的无序区和有序区，且仍满足关系的值<=的值，同样要将其调整为堆；

..........

直到无序区只有一个元素为止；

4.4：应用

寻找M个数中的前K个最小的数并保持有序；

时间复杂度：O(K)[创建K个元素最大堆的时间复杂度] +（M-K）*log(K)[对剩余M-K个数据进行比较并每次对最大堆进行从新最大堆化]

5.希尔排序

（1）基本思想

先将整个待排序元素序列分割成若干子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序（因为直接插入排序在元素基本有序的情况下，效率很高）；

（2）适用场景

比较在希尔排序中是最主要的操作，而不是交换。用已知最好的步长序列的希尔排序比直接插入排序要快，甚至在小数组中比快速排序和堆排序还快，但在涉及大量数据时希尔排序还是不如快排；

6.归并排序

（1）基本思想

首先将初始序列的n个记录看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2的有序子序列，在此基础上，再对长度为2的有序子序列进行两两归并，得到若干个长度为4的有序子序列，以此类推，直到得到一个长度为n的有序序列为止；

（2）适用场景

若n较大，并且要求排序稳定，则可以选择归并排序；

7.简单选择排序

（1）基本思想

第一趟：从第一个记录开始，将后面n-1个记录进行比较，找到其中最小的记录和第一个记录进行交换；

第二趟：从第二个记录开始，将后面n-2个记录进行比较，找到其中最小的记录和第2个记录进行交换；

...........

第i趟：从第i个记录开始，将后面n-i个记录进行比较，找到其中最小的记录和第i个记录进行交换；

以此类推，经过n-1趟比较，将n-1个记录排到位，剩下一个最大记录直接排在最后；