计数排序 发表于 2018-04-17 分类于 OI&ACM ， 算法基础 ， 排序 本文字数： 984 阅读时长 ≈ 1 分钟 【基本思想】计数排序是非比较类排序一种，其基本思想是：对于给定的输入序列中的每一个元素 $x$，确定该序列中值小于 $x$ 的元素的个数，一旦有了这个信息，就可以将 $x$ 直接存放到最终的输出序列的正确位置上 例如，如果输入序列中只有 $17$ 个元素的值小于 $x$ 的值，则 $x$ 可以直接存放在输出序列的第 $18$ 个位置上 阅读全文 »
基数排序 发表于 2018-04-17 分类于 OI&ACM ， 算法基础 ， 排序 本文字数： 1.7k 阅读时长 ≈ 2 分钟 【基本思想】基数排序借助多关键字排序的思想，对单逻辑关键字进行排序，简单来说，其是基于关键字各位的大小进行排序 假设长度为 $n$ 的线性表中每个结点 $a_j$ 的关键字由 $d$ 元组 $(k_j^{d_-1},k_j^{d_-2},…,d_j^1,d_j^0)$ 组成，满足 $0\leq k_j^i\leq r-1$，其中 $k_j^{d-1}$ 为最主关键字，$k_j^0$ 为最次关键字，且 $0\leq j <n,0\leq i\leq d-1$ 阅读全文 »
桶排序 发表于 2018-04-17 分类于 OI&ACM ， 算法基础 ， 排序 本文字数： 606 阅读时长 ≈ 1 分钟 【基本思想】桶排序，是非比较排序中最简单一种排序方法，适用于待排序数据值域较大但分布比较均匀的情况 其基本思想是：假设待排序记录的值都在 $0$ 到 $m-1$ 之间，那么就设置 $m$ 个桶，将值为 $i$ 的记录分配到第 $i$ 个桶中，然后再将各个桶中的数据依次收集起来 阅读全文 »
逆序对问题 发表于 2018-03-29 分类于 OI&ACM ， 算法基础 ， 排序 本文字数： 931 阅读时长 ≈ 1 分钟 【问题】设 $A$ 为一个有 $n$ 个数字的有序集，其中所有数字各不相同，如果存在整数 $i,j$，使得 $1\leq i < j \leq n$ 且 $A[i]>A[j]$，则 $\{A[i],A[j]\}$ 这个有序对称为 $A$ 的一个逆序对 例如：集合 $\{3,1,4,5,2\}$ 的逆序对有 $\{3,1\}$、$\{3,2\}$、$\{4,2\}$、$\{5,2\}$ 共 $4$ 个 阅读全文 »
归并排序 发表于 2018-03-29 分类于 OI&ACM ， 算法基础 ， 排序 本文字数： 1.3k 阅读时长 ≈ 1 分钟 【基本思想】归并排序是分治策略的一个非常典型的应用，其基本思想是将 $n$ 个待排序的记录看成是 $n$ 个长度为 $1$ 的有序序列，然后两两进行归并，第一轮得到 $\frac{n}{2}$ 个长度为 $2$ 的有序序列，第二轮得到 $\frac{n}{4}$ 个长度为 $4$ 的有序序列，以此类推，直到得到一个长度为 $n$ 的有序序列 归并排序的核心是归并操作，即将两个已经排序的序列合并成一个序列的操作，其步骤如下： 阅读全文 »
快速排序 发表于 2018-03-21 分类于 OI&ACM ， 算法基础 ， 排序 本文字数： 1.9k 阅读时长 ≈ 2 分钟 【基本思想】快速排序对冒泡排序的一种改进，在冒泡排序中，记录的比较与移动是在相邻位置进行的，记录每次交换只能后移一个位置，因而总的比较次数与移动次数较多；而在快速排序中，记录的比较与移动是从两端向中间进行的，关键码较大的记录一次就能从前面移动到后面，关键码较小的记录一次就能从后面移动到前面，由于记录移动的距离较远，从而减少了总的比较次数与移动次数 快速排序利用了分治策略，其基本思想是：首先选一个轴值，作为比较的基准，将待排序记录划分为独立的两部分，左侧记录均小于等于轴值，右侧记录均大于等于轴值，然后分别对这两部分重复上述过程，直至序列有序 阅读全文 »
鸡尾酒排序 发表于 2018-03-18 分类于 OI&ACM ， 算法基础 ， 排序 本文字数： 1.3k 阅读时长 ≈ 1 分钟 【基本思想】鸡尾酒排序也称双向冒泡排序、定向冒泡排序，是原始冒泡排序的改进 双向冒泡排序与冒泡排序的不同在于其从低到高比较，然后再从高到低比较，如此循环往复，直到序列有序，而冒泡排序仅是从低到高的去比较序列中的每个元素 阅读全文 »
原始冒泡排序 发表于 2018-03-18 分类于 OI&ACM ， 算法基础 ， 排序 本文字数： 1.3k 阅读时长 ≈ 1 分钟 【基本思想】原始冒泡排序是交换排序中最简单的排序方法，其基本思想是：两两比较相邻记录的关键码，若反序则交换，直到没有反序为止 原始冒泡排序的具体的排序过程如下： 阅读全文 »
堆排序 发表于 2018-03-15 分类于 OI&ACM ， 算法基础 ， 排序 本文字数： 1.4k 阅读时长 ≈ 1 分钟 【基本思想】堆排序利用了堆这一数据结构来进行排序，其基本思想是：将待排序的记录构成堆，然后不断将堆顶元素移走，并将剩余的记录调整成堆，直到堆空 对于大根堆来说，其堆排序结果为降序序列，对于小根堆来说，其堆排序结果为升序序列 阅读全文 »