排序方法有哪几种（几种经典排序算法介绍）

算法和数据结构是一个程序员的内功，所以经常在一些笔试中都会要求手写一些简单的排序算法，以此考验面试者的编程水平。下面我就简单介绍八种常见的排序算法，一起学习一下。

排序方法有哪几种（几种经典排序算法介绍）

一、冒泡排序

思路：比较相邻的元素。如果第一个比第二个大，就交换它们两个；

排序方法有哪几种（几种经典排序算法介绍）

对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素就是最大的数；

排除最大的数，接着下一轮继续相同的操作，确定第二大的数...

重复步骤1-3，直到排序完成。

平均时间复杂度：O(n²)

空间复杂度：O(1)

算法稳定性：稳定

二、插入排序

思路：从第一个元素开始，该元素可以认为已经被排序；

取出下一个元素，在前面已排序的元素序列中，从后向前扫描；

如果该元素（已排序）大于新元素，将该元素移到下一位置；

重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；

将新元素插入到该位置后；

重复步骤2~5。

平均时间复杂度：O(n²)

空间复杂度：O(1)

算法稳定性：稳定

三、选择排序

思路：第一轮，找到最小的元素，和数组第一个数交换位置。

第二轮，找到第二小的元素，和数组第二个数交换位置...

直到最后一个元素，排序完成。

算法复杂度：O(n²)算法空间复杂度：O(1)算法稳定性：不稳定

四、希尔排序

思路：把数组分割成若干(h)个小组(一般数组长度length/2)，然后对每一个小组分别进行插入排序。每一轮分割的数组的个数逐步缩小，h/2->h/4->h/8，并且进行排序，保证有序。当h=1时，则数组排序完成。

算法复杂度：O(nlog2n)算法空间复杂度：O(1)算法稳定性：稳定

本文网址：https://www.dingshengweb.cn/jzzs/421.html

版权声明： 1.本站内容部分为潍坊鼎晟科技编辑原创文章，部分来源于网络，如需转载，请标注来源网站名字和文章出处链接。 2.本站内容为传递信息使用，仅供参考，也不构成相关建议。 3.部分内容和图片来源于网络，如有侵权，请联系我们处理。