常见算法基础题思路简析(一)-排序篇

原创
2017/09/28 22:04
阅读数 296

常见算法基础题思路简析(一)-排序篇

标签: algorithms


[TOC]


本文对和 排序 有关的常见算法基础题思路进行分析和总结,并以 Java 为例,适当指出需要注意的编程细节

记号约定:按升序排,数组 A 大小记为 n

冒泡排序

思路:

  1. 依次交换相邻两个数,使大的在后,每趟在末尾确定一个最大值
  2. 外循环 n 趟依次确定最大值,次大值,....,确定排序

注意:

  • 内循环的相邻元素下标写法和内循环下标起始

计数排序

思路:

  1. 找到数组最大值 max 和最小值 min,以差值(max-min)作为桶数组的长度
  2. 遍历数组入桶计数
  3. 遍历桶,写回原数组

注意:

  • 入桶时,对应桶下标为 A[i]-min
  • 写回数组时下标依次递增, A[i++] = j + min;

堆排序

思路:

  1. 初始化成大根堆
  2. 将堆顶元素(即最大值)和末尾元素交换,并下沉该换上来的末尾元素
  3. 将堆的长度减1,重复第二步

注意:

  • 下标从 1 开始较方便,子节点下标就对应为 2*i2*i+1
  • 初始化时从一半位置依次递减下标使用下沉操作
  • 下沉操作挑子节点中较大值与父节点交换,直至 满足父节点大于两个子节点
private static void sink(Comparable[] pq, int k, int N) {
    while (2 * k <= N) {
        int j = 2 * k;
        if (j < N && less(pq, j, j + 1)) j++;
        if (!less(pq, k, j)) break;
        exch(pq, k, j);
        k = j;
    }
}

插入排序

思路:

  1. 将数组前一部作为一个“有序数组”,该“有序数组”长度逐步扩大
  2. 每趟循环将当前元素依次和前一个元素比对,插入到“有序数组”中的相应位置

注意:

  • 注意下标起始,外循环 n-1 次,内循环下标递减
  • 插入效果可以使用两两相邻交换来实现

归并排序

这里使用非递归的 bottom-up 的实现方式

思路:

  1. 每次合并的单位长度为 size , size 依次取 1,2,... ,直到 size>=n
  2. 对于每个 size,从前往后按照步长为 2*size 依次合并
  3. 归并的内部逻辑是,先从原数组拷贝一份到辅助数组,再按序填回原数组

注意:

  • 需要分配一个辅助数组用于合并
  • 每次合并需要传递五个参数:原数组,辅助数组以及合并的起止下标和中点下标
  • 归并的截止下标需要取小避免越界 Math.min(n, i + 2 * size);
  • 内循环的终止条件是 i + size < n,步长是 2*size

快速排序

思路:

  1. shuffle(可选):先把原数组随机打乱
  2. partition:随机选一个数作为参考值,比其小的放左边,大的放右边
  3. 递归地排序上述结果的左半部分和右半部分

注意:

  • 一般参考值就取第一个元素,对后面的元素进行划分
  • 划分时注意循环终止条件,大于小于带不带等号,都要注意

选择排序

思路:

  1. 每次遍历一趟挑取最小元素,将该元素与起始元素交换
  2. 起始元素下标依次为0,1,...,n-1

注意:

  • 比较的是值,记录的是下标

基数排序

以元素小于等于 2000 为例,位数为 4

思路:

  1. 准备一个 10*n 的桶数组(10 代表 0~9 的数字,n代表某个数字下最多容纳的个数,这里为原数组大小 n)
  2. 由低位到高位,将3,4步执行位数次循环
  3. 遍历数组,按照某一位的数字将元素入桶
  4. 从大数字到小数字,依次将桶内元素从后往前写回原数组

注意:

  • 需要两个辅助数组,一个用于存放元素,一个用于记录每个数字桶的元素个数
  • 入桶时一定要先低位,再高位,这样才能保证最高位影响最大
  • 取桶内元素返到数组时一定要倒着取,这样才能保证之前排序的顺序

希尔排序

思路:

  1. 对数组进行步长为1,4,13,...,(3*前一个步长+1)的插入排序,步长由大到小

注意:

  • 最外层先计算好最大步长,每次除以三
  • 插入排序的外层起始下标为 h,每次下标递增 1
  • 插入排序的内层递减步长为 h

合并两个有序数组

题目:Merge

思路:

  1. 从两个数组末端取值,每次取较大者,从后往前填空
  2. 当数组 B 的元素分配完时结束

判断数组中是否有重复值

题目见 Checker

时间最快 O(n),遍历一遍使用哈希表即可。

若要保证额外空间复杂度为O(1),则使用排序,再遍历,看相邻是否有重值

行列排序矩阵找值

题目见 lectures.sort.Finder

思路:由于行列分别有序(升序),从矩阵右上/左下开始找均可在 O(行数+列数) 时间复杂度找到。以右上为例,当前数大于待找数,则同行往前找,否则同列往下找。

排序后相邻两数的最大差值

题目见 Gap

直接排序做最快是 O(n*log n)的时间复杂度,这里讨论的是 O(n) 的时间复杂度

思路:来源于桶排序

  1. 找到数组的最大值和最小值,准备 n+1 个桶(n为数组元素个数)
  2. 最大值放在第 n+1 个桶中,其它桶以 (max-min)/n 的间隔均匀分布(所以最小值一定落在第一个第一个桶中)
  3. 将数组中元素依次落入桶中,找出空桶前的桶内元素的最大值和空桶后的桶内元素的最小值,求差即可

注意:

  • n+1 个桶放 n 个元素,一定会有空桶,同一桶内元素的差值一定小于桶区间,所以来自不同桶之间的相邻元素差值更大。
  • 分别使用 hasNum[n+1], maxs[n+1], mins[n+1] 来表示桶是否为空以及桶内元素的最大最小值

计算需要排序的最短子数组的长度

题目见 Subsequence

思路:

  1. 从左到右遍历,记录元素值比该元素左边的最大值要小的最右下标 right
  2. 从右往左遍历,记录元素值比该元素右边的最小值要大的最左下标 left
  3. 如果 right > left,则需要排序的长度为 right-left +1

注意:

  • right 的初始值为 0,left 的初始值为 n-1
  • 遍历的每一步,要么满足递增(减),更新最大(小)值;要么更新下标

荷兰旗问题

题目见 ThreeColor

思路一:计数排序,先入桶再出桶即可。

思路二:类似三路快排,下标[0,lo],(lo,mid],(mid,n-1] 之间的元素各表示一个数值区间

注意:

  • lo, hi, mid 的起始值要注意
  • 交换时的增减顺序要注意,参考示例:
int lo = -1;
int hi = n;
int mid = 0;
while (mid < hi) {
    if (A[mid] < 1) {
        swap(A, ++lo, mid++);
    } else if (A[mid] > 1) {
        swap(A, --hi, mid);
    } else {
        mid++;
    }

}

作者@brianway更多文章:个人网站 | CSDN | oschina

展开阅读全文
加载中

作者的其它热门文章

打赏
0
0 收藏
分享
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部