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