排序算法
直接插入算法
将待排元素依次加入队列中，并进行比较，插入应该的位置
待排序列：35 12 67 29 51
第1步：35
第2步：12 35
第3步：12 35 67
第4步：12 29 35 67
第5步：12 29 35 51 67
冒泡排序
首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则交换两个记录的值，然后比较第二个记录和第三个记录的关键字，依此类推。
简单选择排序
通过n-i次关键字之间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i（1≤i≤n）个记录进行交换，当i等于n时所有记录有序排列。
待排序列：35 12 67 29 51
①：找出最小值12，与第一个关键字进行交换： 12 35 67 29 51
②：找出剩下4个记录中的最小值29，与第二个关键字交换：12 29 67 35 51
③：找出剩下3个记录中的最小值35，与第三个关键字交换：12 29 35 67 51
④：找出剩下2个记录中的最小值51，与第四个关键字交换：12 29 35 51 67
希尔排序
- 希尔排序又称“缩小增量排序”，是对直接插入排序方法的改进
- 先将整个待排记录序列分割成若干子序列，然后分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。
- 如，待排数量为n，第一次d=n/2,直至d=d/2=1为止，排序结束
- 每间隔d，划分一组，进行位置上的直接插入
快速排序
- 第一步：选取对比数据元素（第一个记录）
- 第二步：设定下标i,j分别位于队列的最左最右两侧
- 第三步：行动从j开始，如果数值小于对比元素，与i上的元素交换位置，如没有j向左移动直至达到条件
- 第四步：行动交给i，如果该数值小于对比元素，与j上的元素交换位置，如没有i往右侧移动一位直至达到条件
- 第五步：当i,j相遇，停止所有行动。此时左侧全部小于右侧（以对比元素为界限）
- 前、后两部分可以再采用同样的方法进行排序。
堆排序
- 大顶堆：每个结点的值都大于或等于其左右孩子结点的值
- 小顶堆：每个结点的值都小于或等于其左右孩子结点的值
对一组待排序记录的关键字，首先把它们按堆的定义排成一个序列（即建立初始堆），从而输出堆顶的最小关键字（对于小顶堆而言）。然后将剩余的关键字再调整成新堆，便得到次小的关键字，如此反复，直到全部关键字排成有序序列为止。
归并排序
把一个有n个记录的无序文件看成是由n个长度为1的有序子文件组成的文件，然后进行两两归并，得到ｎ/2个长度为2或1的有序文件，再两两归并，如此重复，直至最后形成包含ｎ个记录的有序文件为止。
待排序列：39 19 32 25 46 58 47 55
[39 19][32 25][46 58][47 55]
[19 39][25 32][46 58][47 55]
[19 25 32 39] [46 47 55 58]
[19 25 32 39 46 47 55 58]
总结与比较
一句话总结
- 1、直接插入排序：按顺序插入待排关键字，插入时依次查找位置，直接插入，后面的依次后移。
- 2、冒泡排序：依次把相邻的两个记录进行比较，然后交换位置。
- 3、简单选择排序：每次选择最小的，与第一个没有排过序的记录交换。
- 4、希尔排序：间隔若干个空的记录分为一组，进行直接插入排序，依次将间隔缩小到1为止。
- 5、快速排序：设两个指针指示头尾，从尾开始，首尾交替轮流和枢轴记录（第一个记录）进行比较，并交换位置。
- 6、堆排序：反复将待排序列建立成堆，并取堆顶。
- 7、归并排序：两两归并为一组，再四个记录归并为一组，依此类推。
图源
冒泡排序（Bubble Sort）含gif动图_冒泡排序gif-CSDN博客
【基本排序算法】排序思路/GIF动图/C语言代码/算法改良-KuangStudy-文章
【排序】java代码实现，万字详解常见的八大排序，直接插入排序，希尔排序，选择排序，堆排序，冒泡排序，快速排序，归并排序，计数排序-CSDN博客
八大排序算法——堆排序（动图演示 思路分析 实例代码java 复杂度分析） – 测试开发喵 – 博客园