面试 - 排序算法总结

Myth丶恋晨 2022-10-23 01:59 148阅读 0赞

### 文章目录 ###

*  冒泡排序(BubbleSort) O(n2)
 *  选择排序(SelctionSort)
 *  插入排序(Insertion Sort)
 *  希尔排序(Shell Sort)
 *  快速排序(Quicksort)
 *  归并排序(Merge Sort)
 *  堆排序(HeapSort)
 *  基数排序(RadixSort)
 *  参考

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4ODcxNA_size_16_color_FFFFFF_t_70_pic_center]

# 冒泡排序(BubbleSort) O(n2) #

基本思想：两个数比较大小，较大的数下沉，较小的数冒起来。

# 选择排序(SelctionSort) #

在长度为N的无序数组中，第一次遍历n-1个数，找到最小的数值与第一个元素交换；  
第二次遍历n-2个数，找到最小的数值与第二个元素交换；  
。。。  
第n-1次遍历，找到最小的数值与第n-1个元素交换，排序完成。

# 插入排序(Insertion Sort) #

在要排序的一组数中，假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。

# 希尔排序(Shell Sort) #

在要排序的一组数中，根据某一增量分为若干子序列，并对子序列分别进行插入排序。  
然后逐渐将增量减小,并重复上述过程。直至增量为1,此时数据序列基本有序,最后进行插入排序。

# 快速排序(Quicksort) #

基本思想：（分治）

先从数列中取出一个数作为key值；  
将比这个数小的数全部放在它的左边，大于或等于它的数全部放在它的右边；  
对左右两个小数列重复第二步，直至各区间只有1个数。

# 归并排序(Merge Sort) #

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。  
首先考虑下如何将2个有序数列合并。这个非常简单，只要从比较2个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。

# 堆排序(HeapSort) #

先把数组构造成一个大顶堆（父亲节点大于其子节点），然后把堆顶（数组最大值，数组第一个元素）和数组最后一个元素交换，这样就把最大值放到了数组最后边。把数组长度n-1,再进行构造堆，把剩余的第二大值放到堆顶，输出堆顶(放到剩余未排序数组最后面)。依次类推，直至数组排序完成。

# 基数排序(RadixSort) #

BinSort想法非常简单，首先创建数组A\[MaxValue\]；然后将每个数放到相应的位置上（例如17放在下标17的数组位置）；最后遍历数组，即为排序后的结果。

--------------------

# 参考 #

https://www.runoob.com/w3cnote/sort-algorithm-summary.html  
https://www.cnblogs.com/maluning/p/7944809.html

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4ODcxNA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/51bac85eb79a4dc09c79afd7fe38c220.png