常见排序算法的归纳

比较两个相邻的元素，并将具有最大值的元素切换到右边。

依次比较两个相邻的数，小数在前，大数在后。

即在第一遍中:先将数字1与第二个数进行比较，小数在前，大数在后。然后将第二个数与第三个数进行比较，小数放在前面，大数放在后面，以此类推，直到最后两个数比较完毕，小数放在前面，大数放在后面。然后重复第一步，直到所有排序完成。

第一次比较后，最后一个数字必须是数组中最大的数字，所以最后一个数字不会参与第二次比较。

第二遍完成后，倒数第二个数字也必须是数组中第二大的数字，因此最后两个数字在第三遍时不会参与比较。

依次类推......

输出结果:

冒泡排序的优点:每次排序都会比较少，因为每次排序都会发现更大的值。例如，在第一次比较之后，最后一个数字必须是最大的数字。在第二次排序时，只需要比较除最后一个数字外的其他数字，也可以发现最大的数字在参与第二次比较的数字后面。第三次比较，只需要比较除最后两个数以外的其他数，以此类推...也就是说，没有比较。

就时间复杂度而言:

从一个数组中随机选取一个数n，通过一次排序将数组分为三部分，即1、面积2小于n、面积3等于n、面积大于n，然后按照这种方法分别递归处理面积小于n和面积大于n的和，使整个数据成为一个有序的数组。

如下图所示:

假设初始基准面是数组的第一个元素23，我们先用一个临时变量存储基准面，即tmp=23，然后分别从数组两端扫描数组，设置两个指标:低点到起始位置，高点到结束位置。

第一，从后半段开始，如果扫描值大于基准数据，就让它高-1；如果发现一个元素小于基准数据，比如18

然后开始从前到后扫描。如果扫描值小于基准数据，则让low+1。如果发现某个元素大于基准数据，例如上面的图46 >:= tmp，然后将低位的值赋给高位的值。指针移动并交换数据后，结果如下:

然后开始从前到后遍历，直到low=high结束循环，此时low或high的下标是数组中引用数据23的正确索引位置，如下图所示:

一次次往下走，我们可以清楚的知道，快速排序的本质就是把所有小于基准数据的数放在基准数的左边，所有大于基准数的数放在基准数的右边，从而找到数据在数组中的正确位置。

然后对前半部分和后半部分进行递归排序，最终结果自然有序。

输出结果:

在最好的情况下，快速队列每次都能恰好分割出序列，所以时间复杂度为O(nlogn)。最坏的情况下，快速队列每次只能把序列分成一个元素和其他元素。此时快速队列退化为冒泡排序，时间复杂度为O (N 2)。

插入排序的基本操作是将一个数据插入到有序数据中，从而得到一个编号加一的新的有序数据。该算法适合对少量数据进行排序，时间复杂度为O (n 2)。是一种稳定的排序方法。

将数据插入到已排序的有序数据中。

第一次排序:

将数组的第二个数字与第一个数字进行比较(视为有序数据)

第二次排序:

将数组的第三个数字与已经排序的数据{2，3}(刚才排列在第一行)进行比较。

第二步:

...

诸如此类。

输出结果:

选择性排序是一种简单直观的排序算法。它的工作原理是每次从要排序的数据元素中选择最小(或最大)的元素，存储在序列的开头。然后，继续从剩余的未排序元素中搜索最小(或最大)的元素，并将其放在排序序列的末尾。等等，直到所有要排序的数据元素都被排列好。选择性排序是一种不稳定的排序方法。

例如，对数组int进行合并和排序。我们首先使用分治思想的“点”来分割数组。

输出结果: