常见的排序算法

总结：

直接插入排序：按顺序插入关键字，插入时依次查找对应的位置，直接插入，后面的依次后移。

冒泡排序：依次把相邻的两个数值进行比较，然后交换位置。重复上述操作，直至排序完成。

简单选择排序：每次选择最小的，与第一个没有排过序的数值的位置交换。

希尔排序：通过增量分成若干个子序列，进行直接插入排序。逐渐减少增量，继续上述操作，将增量缩小到1为止。

快速排序：设两个指针指示头尾，从尾开始，首尾交替轮流和基数进行比较，并交换位置。

归并排序：两两归并，在这基础上在进行两两归并，直到最后得到一个有序的序列

将要比较的序列分为有序的序列和无序的序列。排序第 i 个数的时候，前 i- 1 个数是有序数组，后面是无序数组，需要将第 i 个数与前 i- 1 个数倒序比较，找到适合的位置插入，原来这个位置的数及以后的数往后移一位。直至排序完成为止。

例：4,2,6,1,8,7

排序过程：

将要排序的序列的第一个值和第二个值作为关键字，进行比较，如果是逆序的话，调换位置。然后关键字换为第二个值和第三个值继续进行比较，由此类推。

例：5,2,7,4,2,3,9

排序过程：

找出要排序的序列中最小的值，和第一个位置的值交换。在除最小值之外的序列中，找出最小的值，与第二位置的值交换。在除最小值和第二小值之外的序列中，找出最小值，与第三位置的值交换。由此类推。

例：3,1,4,2,5

将要排序的序列通过增量（一般第一个增量为序列长度的一般，是整数）分成若干个子序列，然后对每个子序列中相同位置的数值进行直接插入排序。然后减少增量（比上一个增量小），在进行上述操作，直至序列有序。

例：32,5,23,67,43,12,4,5

设定一个基数(一般是第一个)，在设置两个双指针(i,j)分别指向第一个和最后一个元素。

(1)，让 j 指向的元素与基数进行对比，如果比他小的话，则互换 i ， j 位置上的数值，并使 i ++（然后下次对比由 i 与基数对比，比基数小的话，i++，继续对比。比基数大的话，互换 i ， j 位置上的数值，并使 j–。重复(1)(2)操作）

(2)，如果比他大的话，让 j– 。然后继续 (1)(2) 操作。直到 i=j的时候，可以得到两个序列，由基数进行分隔，前面序列小于后面序列。然后再分别对前后两个序列进行上述递归操作。

例：39,58,32,47,46,19,25,55

(基数=39,i=1,j=8):39,58,32,47,46,19,25,55
(基数=39,i=1,j=7):25,58,32,47,46,19,39,55
(基数=39,i=2,j=7):25,39,32,47,46,19,58,55
(基数=39,i=2,j=6):25,19,32,47,46,39,58,55
(基数=39,i=3,j=6):25,19,32,47,46,39,58,55
(基数=39,i=4,j=6):25,19,32,39,46,47,58,55
(基数=39,i=4,j=5):25,19,32,39,46,47,58,55
(基数=39,i=j=4):25,19,32,39,46,47,58,55
由基数 39 进行分隔成两个子序列，再进行上述操作，直到最后排序成功

将长度为 n 的序列进行两两归并，得到 n/2 个长度为 2/1 的有序的子序列，然后再两两归并，如此重复，直到最后得到一个长度为 n 的有序序列

例：30,2,23,43,54,12,20

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/11418.html