首页>内容详情

【算法题】排序类型题目

大熊•2023-10-14 17:11:44

排序类型题目

排序算法在面试题经常被问题，文章对排序类的面试进行了总结，前面的几个排序在面试中经常会出现，后边的桶排序和堆排序较少遇到，可以作为知识进行拓展，不必要必须会写。最后在面试中经常遇到的排序的一些变种题目。希望在面试中进行顺利。

下图是常见的排序算法的时间和空间复杂图。先从宏观上有个了解。

冒泡排序

冒泡排序作为基础的排序，在面试中也经常性的被问到。以及如何优化性能。
算法：比较相邻的元素。如果第一个比第二个大，就交换他们两个. 一次下来找到一个最大的。

时间复杂度为 O(n^2), 空间复杂度为 O(1)

func bubbleSort(nums []int) []int {
    size := len(nums)
    for l:=0; l<size-1; l++ {
        flag := false
        for i:=0; i< size-1-l; i++ {
            if nums[i] > nums[i+1] {
                nums[i], nums[i+1] = nums[i+1], nums[i]
                flag = true
            }
        }
        if flag == false {
            break
        }
    }
    return nums
}

选择排序

SelectionSort 选择排序: 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

时间复杂度为 O(n^2), 空间复杂度为 O(1)

func selectionSort(nums []int) []int {
    size := len(nums)
    for i:=0; i<size; i++ {
       for j:=i+1; j<size; j++ {
           if nums[i] > nums[j] {
               nums[i], nums[j] = nums[j], nums[i]
           }
       }
    }
    return nums
} 
func sortArray(nums []int) []int {
    return selectionSort(nums)
}

插入排序

insertionSort 插入排序: 类似于打扑克牌，分为两个有序队列和待排的序列，从待排中一次找到位置
第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。

从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

时间复杂度为 O(n^2), 空间复杂度为 O(1)

func selectionSort(nums []int) []int {
    size := len(nums)
    for i:=1; i<size; i++ {
       for j:=i; j>0; j-- {
           if nums[j] < nums[j-1] {
               nums[j], nums[j-1] = nums[j-1], nums[j]
           } else {
               break
           }
       }
    }
    return nums
}

shell排序

希尔排序目的为了加快速度改进了插入排序，交换不相邻的元素对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。

在此我们选择增量 gap=length/2，缩小增量以 gap = gap/2 的方式，用序列 {n/2,(n/2)/2...1} 来表示。

func shellSort(arr []int) []int {
    len := len(arr)
    if len <= 1 {
        return arr
    }
    var i, j, gap int
    for gap = len / 2; gap > 0; gap = gap / 2 {
        for i = gap; i < len; i++ {
            for j = i - gap; j >= 0 && arr[j] > arr[j+gap]; j = j - gap {
                arr[j], arr[j+gap] = arr[j+gap], arr[j]
            }
        }
    }
    return arr
}

快排

快排在面试中经常会遇到，快排在实际应用中也多。建议必须要会写。

快速排序的最坏运行情况是 O(n²)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。

所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。

快排的步骤如下：

从数列中挑出一个元素，称为 "基准"（pivot）;
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序


func partition(nums []int, left int, right int) int {
    pivot := left
    index := left + 1
    for i:=index; i<=right; i++ {
        if nums[i] < nums[pivot] {
            nums[i], nums[index] = nums[index], nums[i]
            index++
        }
    }
    nums[pivot], nums[index-1] = nums[index-1], nums[pivot]
    return index - 1
}


func quickSort(arr []int, left int, right int) []int {
    if len(arr) <= 1 {
        return arr
    }
    if left < right {
         pivot := partition(arr, left, right)
         quickSort(arr, left, pivot-1)
         quickSort(arr, pivot+1, right)
    }
    return arr
} 
func sortArray(nums []int) []int {
    return quickSort(nums, 0, len(nums)-1)
}

归并排序

归并排序在面试中也经常会被问起，尤其是一些归并排序的变种题，面试。

算法步骤：

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
设定两个指针，最初位置分别为两个已经排序序列的起始位置；
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
重复步骤 3 直到某一指针达到序列尾；
将另一序列剩下的所有元素直接复制到合并序列尾。

归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。

func merge(arr1 []int, arr2 []int) []int {
    ans := []int{}
    for len(arr1)>0  && len(arr2) > 0 {
        if arr1[0] < arr2[0] {
            value := arr1[0]
            arr1 = arr1[1:]
            ans = append(ans, value)
        }else {
            value := arr2[0]
            arr2 = arr2[1:]
            ans = append(ans, value)
        }
    }
    if len(arr1) > 0 {
        ans = append(ans, arr1...)
    }
    if len(arr2) > 0 {
        ans = append(ans,  arr2...)
    }
    return ans
}


func mergeSort(arr []int) []int {
    if len(arr) <=1 {
        return arr
    }
    mid := len(arr) >> 1
    return merge( mergeSort(arr[0: mid]), mergeSort(arr[mid: len(arr)]) )
} 
func sortArray(nums []int) []int {
    return mergeSort(nums)
}

计数排序

面试中用到的较少，可以作为只是进行扩充下。核心思想是数字有大量重复的。如年龄分布等。

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。

算法的步骤如下：

找出待排序的数组中最大和最小的元素
统计数组中每个值为i的元素出现的次数，存入数组C的第i项
对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。

堆排序

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

大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

桶排序

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

在额外空间充足的情况下，尽量增大桶的数量
使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。
什么时候最快？当输入的数据可以均匀的分配到每一个桶中。
什么时候最慢？当输入的数据被分配到了同一个桶中。

基数排序

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：
基数排序：根据键值的每位数字来分配桶；
计数排序：每个桶只存储单一键值；
桶排序：每个桶存储一定范围的数值；

三中算法在数据量特别大的情况下经常用到。三个方法主要区别是分🪣的方式不一样。

其它相关面试题

1. 使用归并排序完成二维数组合并

使用归并排序完成下面数组的合并。
例如：[[1,2,3],[4,5,6],[7,8,9],[1,2,3],[4,5,6]] 进行合并为一个

这个题很不错，稍微变动了点，但是整体的思想没变。就在合并的地方
骚操作.. [[1,2,3],[4,5,6],[7,8,9],[1,2,3],[4,5,6]].flat(Infinity).sort((a,b)=>{ return a-b;})
最关键是的 arr[0] 的返回，与之前全部返回不一样。过程略。。。

2. 求的数组的中位数

利用的是快排中的partition函数返回的数，确定中位数是什么。

上一篇：【面试题】回文类型题目

下一篇：【算法题】字符串和数组类型题目