[译]算法_排序_开篇

排序问题和排序算法

排序是一个经典的重排元素顺序的问题（其元素可以是整型、浮点型、字符串等可比较的类型）。可以重排为递增序列、非递减序列¹，递减序列，非递增序列²。

排序算法非常多，各有优势与其限制。

排序通常是大学计算机学科中，介绍算法思想的入门问题。

不失一般性的，假定在本教学中我们只以非递减顺序排序整型，元素无需排重。

冒泡排序的演示

思想

排序问题有大量的算法方案，都提现了计算机思想：

1. 比较和非比较的底层策略。
2. 迭代和递归的实现。
3. 分治思想
4. 最好/最差/平均时间复杂度分析。
5. 随机算法

应用

当数组A（整型数组）被排序后，许多问题都变得很容易：

1. 在A中查找值v。
2. 在（静态）数组A中查找最大/最小，第k大/小值。
3. 测试唯一性并删除A中重复的值。
4. 查找A中值v的个数。
5. 计算A与另一个已排序数组B的交集/并集。
6. 在A中找到一对数(x,y)，x∈A且y∈A，满足 x*y=z，等等。

算法的缩写

1. 基于比较的算法
2. BUB - Bubble Sort 冒泡排序
3. SEL - Selection Sort 选择排序
4. INS - Insertion Sort 插入排序
5. MER - Merge Sort(递归实现) 归并排序
6. QUI - Quick Sort(递归实现) 快速排序
7. R-Q - Random Quick Sort(递归实现) 随机快速排序
8. 非比较排序
9. COU - Counting Sort 计数排序
10. RAD - Radix Sort 基数排序

—OU
名词解释

1. 非递减序列
2. 非递增序列

   1,2,3,4,5       递增序列   - 无重复元素
   1,2,2,3,4,4,5,5 非递减序列 - 有重复元素
   5,4,3,2,1       递减序列   - 无重复元素
   5,4,4,3,2,2,1   非递增序列 - 有重复元素