排序算法（未完）

未完）"/>

排序算法（未完）

诸神缄默不语-个人CSDN博文目录

同步在做讲解视频系列。

文章目录

• 0. 排序算法的稳定性分析
• 1. 插入排序/直接插入排序
• • 1.1 希尔排序
  • 2. 简单选择排序
• 3. 堆排序
• 4. 冒泡排序
• 5. 快速排序
• 6. 归并排序
• 7. 桶排序/箱排序
• 8. 基数排序/分配式排序/桶子法
• • 1. 最低位优先(Least Significant Digit first) LSD法
  • 2. 最高位优先(Most Significant Digit first) MSD法
• 9. 计数排序
• 参考资料

0. 排序算法的稳定性分析

1. 插入排序/直接插入排序

类似手工排序扑克牌，每次把一个元素按顺序放到最前面顺序排好的子数组里（一开始这个子数组只有第一个元素）
在实现中一般是目标元素一步一步一边比大小一边往左挪，直到挪到顺序为止
时间复杂度 O(N^2)，空间复杂度 O(1)
稳定的

1.1 希尔排序

分组进行插入排序，组数逐渐减到1
不稳定的

2. 简单选择排序

每次迭代找最小的元素，放到最前面

3. 堆排序

先建立一个无序的堆，然后迭代所有非叶节点（从最后一个开始）对每一个进行堆化（大概来说就是研究这个节点是不是该往子节点下沉，一路下沉到合适的位置上）

每次取出根节点，进行自顶向下堆化，将新的根节点放在原本最后一个节点那里的位置

4. 冒泡排序

一个指针滑，比较后一位与指针位的大小差异，如果前大后小就交换一下，总之每次都把一个最大的保送到最后一位。（可以增加flag标记，如果已经有序即无需移动，就停止下一次迭代）

5. 快速排序

每次将数字分成一大组和一小组

6. 归并排序

1. 把整个数组拆成很多顺序的小数组（从1个数字开始），将小数组顺序合并
2. 将两个顺序序列合并成一个顺序序列。两个序列每个放一个指针，对比元素大小，然后把小的元素放进新空间，然后指针往后走，这样一直走到一个序列被遍历完。

7. 桶排序/箱排序

分桶，对每个桶各自进行排序

8. 基数排序/分配式排序/桶子法

稳定的

O ( n log ⁡ ( r ) m ) O (n\log(r)m) O(nlog(r)m)

1. 最低位优先(Least Significant Digit first) LSD法

（这简称看起来也太容易产生误会了）

以最低位的数开始进行分配，每次分配完后再按组合并，再重新分配，直至分完所有数位

适合位数小的数列

2. 最高位优先(Most Significant Digit first) MSD法

与LSD法相反，从最高位为基底开始进行分配，每次分配之后再在分组中建立子桶进行分配，直至分到最后一位

9. 计数排序

就是非常粗暴地直接按元素放到新数组的索引里

参考资料

1. 基数排序_百度百科
2. JAVA之基数排序LSD顺序_lsd算法 java_二个二个二的博客-CSDN博客
3. 八大排序算法稳定性分析，原来稳定性是这个意思…-腾讯云开发者社区-腾讯云