八大排序算法总结

概述说明：

即使大多数语言提供排序函数，但学习排序算法仍然有三大实际意义：

• 对排序算法的分析将有助于全面理解其他比较算法性能的方法；
• 类似的技巧也能有效解决其他类型的问题；
• 排序算法常常是我们解决其他问题的第一步。

（1）排序的定义：就是将一组对象按照某种逻辑顺序重新排列的过程。

（2）评价算法优劣术语说明

        稳定：若果a原本在b前面，而a=b，排序之后a仍然在b的前面；不稳定：若果a原本在b前面，而a=b，排序之后a可能会出现在b的后面。

        时间复杂度：一个算法执行所耗费的时间。空间复杂度：运行一个程序所需要内存的大小。

（3）排序算法图表总结对比分析

1.冒泡排序（Bubble Sort）

算法描述：冒泡排序是一种简单的排序算法。它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

2.选择排序（Selection Sort）

算法描述：首先，找到数组中最小的元素，其次，将它和数组的第一个元素交换位置（如果第一个元素就是最小元素那么它就和自己交换）。再次，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。

3.插入排序（Insertion Sort）

算法描述：每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。为了给要插入的元素腾出空间，我们需要将其余所有元素在插入之前都向右移动一位。

4.希尔排序（Shell Sort）

算法描述：是直接插入排序算法的一种更高效的改进版本，希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

5.归并算法（Merge Sort）

算法描述：该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将两个有序的数组归并成一个更大的有序数组。

6.快速排序（Quick Sort）

算法描述：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

7.堆排序（Heap Sort）

算法描述：堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

8.基数排序（Radix Sort）

算法描述：基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再 按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。

 

以上算法将以Java语言在后续文章中编写实现，若有不正指出欢迎各位大佬留言指正。