|
排序（Sorting）就是指将一组数据，按特定规则调换位置，使数据具有某种顺序关系（递增或递减），例如数据库内可针对某一字段进行排序，而此字段称为”键“（Key），字段里面的值我们称为”键值“（Key Value）。
在排序的过程中，数据的移动方式可分为”直接移动“和”逻辑移动“两种。直接移动时直接交换存储数据的位置，而逻辑移动并不会移动数据存储的位置，仅改变指向这些数据的辅助指针的值。
排序的分类：
内部排序：排序的数据量小，可以全部加载到内存中进行排序。
外部排序：排序的数据量大，无法全部一次性加载到内存中进行排序，而必须借用辅助存储（如硬盘）进行排序。
常见的排序法：冒泡排序法、选择排序法、插入排序法、合并排序法、快速排序法、堆积排序法、希尔排序法、基数排序法等。
排序的结果与效率决定因素：
1.算法稳定性
2.时间复杂度：最好、最坏、平均
3.空间复杂度
内部排序法
简单排序法：
1.冒泡排序法（Bubble Sort），稳定排序法。空间复杂度为最佳，只需一个额外空间O(1)
2.选择排序法（Selection Sort），不稳定排序法。空间复杂度为最佳，只需一个额外空间O(1)
3.插入排序法（Insertion Sort），稳定排序法，空间复杂度为最佳，只需一个额外空间O(1)
4.希尔排序法（Shell Sort），稳定排序法，空间复杂度为最佳，只需一个额外空间O(1)
高级排序法：
1.快速排序法（Quick Sort），不稳定排序法，空间复杂度最差为O(n)，最佳为O(log2n)
2.堆积排序法（Heap Sort），不稳定排序法，空间复杂度为最佳，只需一个额外空间O(1)
3.基数排序法（Radix Sort），稳定排序法，空间复杂度为O(np)，n为原始数据的个数，p为基底
|