冒泡算法是最快的排序算法吗（排序算法冒泡选择）

快秋招了，面试的时候算法也是必备的本文介绍几种常见的排序算法，建议背下来，面试的时候提前手写一遍快排(快速排序)可以提高手感，事半功倍，今天小编就来说说关于冒泡算法是最快的排序算法吗?下面更多详细答案一起来看看吧!

冒泡算法是最快的排序算法吗

快秋招了，面试的时候算法也是必备的。本文介绍几种常见的排序算法，建议背下来，面试的时候提前手写一遍快排(快速排序)可以提高手感，事半功倍。

1. 冒泡排序

冒泡排序是通过比较两个相邻元素的大小实现排序，如果前一个元素大于后一个元素，就交换这两个元素。这样就会让每一趟冒泡都能找到最大一个元素并放到最后。

func bubbleSort(nums []int) { for i := 0; i < len(nums)-1; i { for j := 0; j < len(nums)-1-i; j { if nums[j] > nums[j 1] { nums[j], nums[j 1] = nums[j 1], nums[j] } } } }

稳定性：它是指对同样的数据进行排序，会不会改变它的相对位置。比如 [ 1, 3, 2, 4, 2 ] 经过排序后，两个相同的元素 2 位置会不会被交换。冒泡排序是比较相邻两个元素的大小，显然不会破坏稳定性。

空间复杂度：由于整个排序过程是在原数据上进行操作，故为 O(1);

时间复杂度：由于嵌套了 2 层循环，故为 O(n*n);

2. 选择排序

选择排序是每次循环选择最大值，在该次循环结束时将最大值同数组最后的数进行交换

func selectSort(nums []int) { for i := 0; i < len(nums)-1; i { var idx int var m = nums[0] for j := 1; j < len(nums)-i; j { if nums[j] > m { m = nums[j] idx = j } } nums[len(nums)-i-1], nums[idx] = nums[idx], nums[len(nums)-i-1] } }

稳定性：它是从后往前遍历已排序好的序列，相同元素不会改变位置，故为稳定排序；

空间复杂度：它是在原序列进行排序，故为 O ( 1 );

时间复杂度：排序的过程中，首先要遍历所有的元素，然后在已排序序列中找到合适的位置并插入。共需要 2 层循环，故为 O ( n * n );

---

3. 希尔排序

它的核心思想是把一个序列分组，对分组后的内容进行插入排序，这里的分组只是逻辑上的分组，不会重新开辟存储空间。它其实是插入排序的优化版，插入排序对基本有序的序列性能好，希尔排序利用这一特性把原序列分组，对每个分组进行排序，逐步完成排序。

func shellSort(nums []int) { // l = 9 l := len(nums) for gap := l / 2; gap > 0; gap = gap / 2 { // i = 4; i < 9; i for i := gap; i < l; i { // j=0,1,2,3,4 // [0]-[4] [1]-[5] [2]-[6] [3]-[7] [4]-[8] for j := i - gap; j >= 0; j = j - gap { if nums[j] > nums[j gap] { nums[j], nums[j gap] = nums[j gap], nums[j] } } } } }

稳定性：它可能会把相同元素分到不同的组中，那么两个相同的元素就有可能调换相对位置，故不稳定。

空间复杂度：由于整个排序过程是在原数据上进行操作，故为 O(1);

时间复杂度：希尔排序的时间复杂度与增量序列的选取有关，例如希尔增量时间复杂度为O(n²)，而Hibbard增量的希尔排序的时间复杂度为O(log n的3/2)，希尔排序时间复杂度的下界是n*log2n

---

4. 快速排序

首先选择一个点作为base，通过从左侧和从右侧遍历，把小于base的数放在左侧，把大于base的数放在右侧，中间是base；接下来以base为中心，分为两部分，每部分再进行快速排序。

func fastSort(nums []int, start, end int) { if end == start { return } base := nums[start] left := start right := end for left < right { for left < right && nums[right] > base { right-- } nums[left] = nums[right] for left < right && nums[left] <= base { left } nums[right] = nums[left] } nums[left] = base fastSort(nums, start, left-1) fastSort(nums, left 1, end) }

稳定性：不稳定

空间复杂度：不使用额外空间，O(1)

时间复杂度：需要使用递归，时间复杂度nlgn

---

5. 归并排序

采用分治的思想，把数组分为一个一个子序列，直到子序列只有一个元素停止拆分，然后对每个子序列进行边排序边合并。

func mergeSort(nums []int, start, end int) { if end == start { return } mid := start (end-start)/2 mergeSort(nums, start, mid) mergeSort(nums, mid 1, end) merge(nums, start, mid, end) } func merge(nums []int, start, mid, end int) { for i := mid 1; i <= end; i { base := nums[i] j := i - 1 for j >= 0 && nums[j] > base { nums[j 1] = nums[j] j-- } nums[j 1] = base } }

稳定性：在元素拆分的时候，虽然相同元素可能被分到不同的组中，但是合并的时候相同元素相对位置不会发生变化，故稳定。

空间复杂度：需要用到一个数组保存排序结果，也就是合并的时候，需要开辟空间来存储排序结果，故为 O ( n );

时间复杂度：最好最坏都为 O(nlogn);

---

6. 计数排序

使用和需排序数组的最大最小值相关的下标数组进行计数，最后根据计数得出排序后的数组。比如nums[8,1,4,6,2,3,5,4]，那么下标数组为atr[1,1,1,2,1,1,0,1]

func countSort(nums []int) { if len(nums) == 0 { return } big := nums[0] small := nums[0] for i := 1; i < len(nums); i { big = max(nums[i], big) small = min(nums[i], small) } atr := make([]int, big-small 1) for _, n := range nums { atr[n-small] } i := 0 for j, n := range atr { if n > 0 { for k := 0; k < n; k { nums[i] = j small i } } } } func max(a, b int) int { if a > b { return a } return b } func min(a, b int) int { return a b - max(a, b) }

稳定性：在元素往 countArr 中记录时按顺序遍历，从 countArr 中取出元素也是按顺序取出，相同元素相对位置不会发生变化，故稳定。

空间复杂度：需要额外申请空间，复杂度为“桶”的个数，故为 O ( k )， k 为“桶”的个数，也就是 countArr 的长度;

时间复杂度：最好最坏都为 O(n k)， k 为“桶”的个数，也就是 countArr 的长度;

,