算法和数据结构（一）—— 查找和排序
2016-08-04 本文已影响1188人
eagleRock
查找和排序都是程序设计中经常用到的算法。查找相对而言较为简单，不外乎顺序查找、二分查找、哈希表查找和二叉排序树查找。排序常见的有插入排序、冒泡排序、归并排序和快速排序。其中我们应该重点掌握二分查找、归并排序和快速排序，保证能随时正确、完整地写出它们的代码。同时对其他的查找和排序必须能准确说出它们的特点、对其平均时间复杂度、最差时间复杂度、额外空间消耗和稳定性烂熟于胸。
-
内排序：
-
插入排序：直接插入排序(InsertSort)、希尔排序（ShellSort）
-
交换排序：冒泡排序(BubbleSort)、快速排序(QuickSort)
-
选择排序：直接选择排序(SelectSort)、堆排序(HeapSort)
-
归并排序(MergeSort)
-
基数排序(RadixSort)
-
外排序：
-
磁盘排序
-
磁带排序
-
查找：
-
线性表的查找：顺序查找、折半查找（二分查找）、索引存储结构和分块查找
-
树表的查找：二叉排序树、平衡二叉树、B-树、B+树
-
哈希表查找
快速排序(QuickSort)
- 平均/最好时间复杂度：O(nlogn)
- 最差时间复杂度：O(n^2)
- 平均空间复杂度：O(logn)
- 最差空间复杂度：O(n)
- 稳定性：不稳定
- 时间复杂度分析：
快速排序总体的平均效果是最好的，当如果数组本身已经排好序或几乎有序的情况下，每轮排序又都是以最后一个数字作为比较的标准，那么排序的效率就只有O(n^2)。 - 空间复杂度分析：
快速排序通过递归来实现，递归造成的栈空间的使用，最好情况，递归树的深度为log2n，其空间复杂度为O(logn)，最坏情况，需要进行n‐1递归调用，其空间复杂度为O(n)，平均情况，空间复杂度也为O(logn)。 - 稳定性分析：
由于关键字的比较和交换是跳跃进行的，因此，快速排序是一种不稳定的排序方法。 - 排序思想：
快速排序是对冒泡排序的一种改进。通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 - 经典实现：
void quickSort(int[] data, int length, int start, int end) {
if (start == end)
return ;
int index = partition(data, length, start, end);
if (index > start)
quickSort(data, length, start, index-1);
if(index < end)
quickSort(data, length, index+1, end);
}
int partition(int[] data, int length, int start, int end) {
if (data == null || length <= 0 || start < 0 || start >= length)
throw new RuntimeException("Invalid Parameters");
int index = randomInRange(start, end);
swap(data, index, end);
int small = start - 1;
for (index = start; index < end; index++)
if (data[index] < data[end]) {
++ small;
if (small != index)
swap(data, small, index);
}
++ small;
swap(data, small, end);
return small;
}
int randomInRange(int start, int end) {
return new Random().nextInt(end-start+1)+start;
}
void swap(int[] data, int a, int b) {
int tmp = data[a];
data[a] = data[b];
data[b] = tmp;
}
归并排序(MergeSort)
- 平均/最好/最差时间复杂度：O(nlogn)
- 平均空间复杂度：O(n)
- 稳定性：稳定
- 复杂度分析：
归并排序比较占用内存，但却是一种效率高且稳定的算法。 - 代码实现：
void mergeSort(int[] data, int low, int high) {
if (data == null || low < 0 || high >= data.length)
throw new RuntimeException("Invalid Parameters!");
if (low < high) {
int mid = (low + high) / 2;
mergeSort(data, low, mid);
mergeSort(data, mid + 1, high);
merge(data, low, mid, high);
}
}
void merge(int[] data, int low, int mid, int high) {
int startFrist = low, endFrist = mid, startSecond = mid + 1, endSecond = high;
int[] tmp = new int[data.length];
int i = startFrist, j = startSecond, index = startFrist;
while (i <= endFrist && j <= endSecond)
if (data[i] < data[j])
tmp[index++] = data[i++];
else
tmp[index++] = data[j++];
while (i <= endFrist)
tmp[index++] = data[i++];
while (j <= endSecond)
tmp[index++] = data[j++];
for (index = low; index <= high; index++)
data[index] = tmp[index];
}
二分查找
- 平均/最差时间复杂度：O(logn)
- 平均查找长度ASL：log2(n+1) - 1
- 空间复杂度：O(1)
- 算法分析：折半查找要求线性表是有序表。另外，由于折半查找需要确定查找的区间，所以只适用于顺序存储结构，不适用于链式存储结构。为保持顺序表的有序，表的插入和删除操作都需要移动大量元素，所以折半查找特别适用于一旦建立就很少改动，又经常需要进行查找的线性表。
- 实现代码
public BinarySearch(int[] data, int length, int key) {
if (data == null || length <= 0)
throw new RuntimeException("Invalid parameters");
int low = 0, high = length - 1;
while (low <= high) { // 当前区间存在元素时循环
int mid = (low + high) / 2;
if (data[mid] == key) // 查找成功返回其逻辑序号mid+1
return mid + 1;
else if (data[mid] < key) // 继续在data[mid+1 .. high]中查找
low = mid + 1;
else
high = mid - 1; // 继续在data[low .. mid-1]中查找
}
return 0; // 查找失败返回0
}
索引存储结构和分块查找
-
索引存储结构
索引存储结构是在存储数据的同时，还建立附加的索引表。索引表中的每一项称为索引项，索引项的结构一般形式为（关键字，地址）。
关键字唯一标识一个节点，地址是指向该关键字对应节点的指针，也可以是相对地址。
- 索引存储结构的优缺点
- 优点：线性结构采用索引存储后，可以对节点进行随机访问。在进行插入、删除运算时，由于只需要修改索引表中相关节点的存储地址，而不必移动存储在节点表中的节点，所以仍可保存较高的运算效率。
- 缺点：为了建立索引表需要增加时间和空间的开销。
-
分块查找
分块查找又称索引顺序查找，它是一种性能介于顺序查找和二分查找之间的查找方法。
分块查找需要按照如下的索引方式建立存储线性表：将表R[0.. n-1]均分为b块，前b-1块中元素个数为s=⌈n/b⌉，最后一块即第b块的元素个数等于或小于s；每一块的关键字不一定有序，但是前一块中的最大关键字必须小于后一块中的最小关键字，即要求表是“分块有序”的。
分块查找的基本思路是：首先查找索引表，因为索引表是有序表，故可以用折半查找或顺序查找，以确定待查的元素在哪一块；然后在已确定的块中进行顺序查找（因块内元素无序，只能用顺序查找）。
- 采用折半查找来确定块元素所在块的平均查找长度ASL：log2(b+1) + s/2，s越小，即每块长度越小越好
- 采用顺序查找来确定块元素所在块的平均查找长度ASL：(b+s)/2 + 1，s=√￣n时，ASL取极小值√￣n+1，即采用顺序查找确定块时，各块元素个数取√￣n最佳。
- 分块查找的缺点：增加一个索引表的存储空间和建立索引表的时间。
冒泡排序（BubbleSort）
- 平均/最差时间复杂度：O(n^2)
- 最好时间复杂度：O(n)
- 平均空间复杂度：O(1)
- 稳定性：稳定
- 算法思想：
从最下面的元素开始，对每两个相邻的元素的关键字进行比较，且使关键字小的元素换至关键字大的元素之上，使得一趟排序后，关键字最小的元素到达最上端。 - 代码实现：
void bubbleSort(int[] data, int length) {
if (data == null || length <= 0)
throw new RuntimeException("Invalid Paramemers");
for (int i = 0; i < length-1; i++) {
boolean isExchange = false;
for (int j = length-1; j > i; j--) {
if (data[j] < data[j-1]) {
swap(data, j, j-1);
isExchange = true;
}
}
if(!isExchange)
return;
}
}
选择排序（SelectSort）
- 平均/最好/最差时间复杂度：O(n^2)
- 空间复杂度：O(1)
- 稳定性：不稳定
- 性能分析：适用于从大量元素中选择一部分排序元素，例如从1w个元素中找出前10个元素
- 排序思路
第i趟排序开始时，R[0 .. i-1]是有序区，而R[i .. n-1]是无序区。该趟排序是从当前无序区中选出关键字最小的元素R[k]，将它和无序区的第一个元素R[i]交换，使得R[0.. i]和R[i+1 .. n-1]变成新的有序区和新的无序区。 - 代码实现：
void selectSort(int[] data, int length) {
if (data == null || length <= 0)
throw new RuntimeException("Invalid Paramemers");
for (int i = 0; i < length-1; i++) {
int minIndex = i;
for (int j = i+1; j < length; j++)
if (data[j] < data[minIndex])
minIndex = j;
if (minIndex != i)
swap(data, minIndex, i);
}
}
堆排序（heapSort）
- 平均/最好/最差时间复杂度：O(nlogn)
- 空间复杂度：O(1)
- 稳定性：不稳定
- 性能分析：由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。
- 排序思路：
堆排序是一种树形选择排序方法，在排序过程中，将data[1 .. n]看成一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲节点和孩子节点之间的内在关系，在当前无序区中选择关键字最大（或最小）的元素。 - 代码实现：
void heapSort(int[] data, int length) { // 为了与二叉树的顺序存储结构一致，堆排序的数据序列的下标从1开始
if (data == null || length <= 0)
throw new RuntimeException("Invalid Paramemers");
for (int i = length/2; i >= 1; i--) //初始化堆
sift(data, i, length);
for (int i = length; i >=2; i--) { //进行n-1趟堆排序，每一趟堆排序的元素个数减1
swap(data, i, 1); //将最后一个元素同当前区间内data[1]对换
sift(data, 1, i-1); //筛选data[1]节点，得到i-1个节点的堆
}
}
void sift(int[] data, int low, int high) {
int i = low, j = 2 * i; //data[j]是data[i]的左孩子
int tmp = data[i];
while (j <= high) {
if (j < high && data[j] < data[j + 1]) //若右孩子较大，把j指向右孩子
j++;
if (tmp < data[j]) {
data[i] = data[j]; //将data[j]调整到双亲节点位置上
i = j; //修改i和j值，以便继续向下筛选
j = 2 * i;
} else
break; //筛选结束
}
data[i] = tmp; //被筛选节点的值放入最终位置
}
插入排序（InsertSort）
- 平均/最差时间复杂度：O(n^2)
- 最好时间复杂度：O(n)
- 空间复杂度：O(1)
- 稳定性：稳定
- 算法思想：
每次将一个待排序元素，按其关键字大小插入到已经排好序的子表中的恰当位置，知道全部元素插入完成为止。 - 实现代码：
void insertSort(int[] data, int length) {
if (data == null || length <= 0)
throw new RuntimeException("Invalid Paramemers");
for (int i = 1; i < length; i++) {
int tmp = data[i];
int j = i-1; //从右向左在有序区data[0 .. i-1]中找data[i]的插入位置
while (j >= 0 && data[j] > tmp) {
data[j+1] = data[j]; //将大于data[i]的元素后移
j--;
}
data[j+1] = tmp;
}
}
希尔排序（ShellSort）
- 平均时间复杂度：O(n^1.3)
- 空间复杂度：O(1)
- 稳定性：不稳定
- 算法分析：希尔排序和插入排序基本一致，为什么希尔排序的时间性能会比插入排序优呢？直接插入排序在表初态为正序时所需时间最少，实际上，当表初态基本有序时直接插入排序所需的比较和移动次数都比较少。另一方面，当n值较小时，n和n2的差别也比较小，即直接插入排序的最好时间复杂度O(n)和最差时间复杂度O(n2)差别也不大。在希尔排序开始时，增量d1较大，分组较多，每组的元素数目少，故各组内直接插入排序较快，后来增量di逐渐缩小，分组数逐渐减少，而各组内的元素数目逐渐增多，但由于已经按di-1作为增量排过序，使表教接近有序状态，所以新的一趟排序过程也较快。因此，希尔排序在效率上较直接插入排序有较大的改进。
- 代码实现：
void shellSort(int[] data, int length) {
int gap = length / 2;
while (gap > 0) {
for (int i = gap; i < length; i++) {
int tmp = data[i];
int j = i - gap;
while (j >= 0 && tmp < data[j]) {
data[j + gap] = data[j];
j -= gap;
}
data[j + gap] = tmp;
}
gap /= 2;
}
}
基数排序（RadixSort）
- 平均/最好/最差时间复杂度：O(d(n+r))
- 空间复杂度：O(r)
- 稳定性：稳定
- 算法思想：
- 实现代码：
class Node{
int num;
Node next;
}
void RadixSort(Node p, int r, int d) {
if (p == null || r <= 0 || d <= 0)
throw new RuntimeException("Invalid Parameters");
Node[] head = new Node[10];
Node[] tail = new Node[10];
Node t = null;
for (int i = 0; i <= d - 1; i++) {
t = p;
for (int j = 0; j < r; j++)
head[j] = tail[j] = null;
while (p.next != null) {
p = p.next;
int k = getDigit(p.num, i);
if (head[k] == null) {
head[k] = p;
tail[k] = p;
} else {
tail[k].next = p;
tail[k] = p;
}
}
p = t;
p.next = null;
for (int j = 0; j < r; j++)
if (head[j] != null) {
if (p.next == null)
p.next = head[j];
else
t.next = head[j];
t = tail[j];
}
t.next = null;
}
}
public static int getDigit(int x, int d) {
int a[] = { 1, 10, 100 }; // 如果实例的最大数是百位数，那就只要到100就可以了
return ((x / a[d]) % 10);
}
各种内排序方法的比较和总结
-
按平均时间复杂度将排序分为3类：
- 平方阶O(n^2)排序，一般称为简单排序，例如直接插入排序，直接选择排序和冒泡排序
- 线性对数阶O(nlogn)排序，如快速排序、堆排序和归并排序
-
线性阶O(n)排序，如基数排序（假定数据的位数d和进制r为常量时）
各种排序方法的性能
-
因为不同排序方法适应于不同的应用环境和要求，所以选择适合的排序方法应综合考虑下列因素：
- 待排序的元素数目n（问题规模）；
- 元素的大小（每个元素的规模）；
- 关键字的结构及其初始状态；
- 对稳定性的要求；
- 语言工具的条件；
- 存储结构；
- 时间和空间复杂度等。
-
没有一种排序方法是绝对好的。每一种排序方法都各有其优缺点，适用于不同的环境。因此，在实际应用中，应根据具体情况做选择。首先考虑排序对稳定性的要求，若要求稳定，则只能在稳定方法中选取，否则可以在所有方法中选取；其次要考虑待排序节点数n的大小，若n较大，则可在改进方法中选取，否则在简单方法中选取；然后在考虑其他因素。综合考虑以上几点可以得出的大致结论：
- 若n较小（如n<=50），可采用直接插入排序或直接选择排序。当元素规模较小时，直接插入排序较好；否则因为直接选择排序移动的元素少于直接插入排序，应选直接选择排序。
- 若文件初始状态基本有序（指正序），则应选用直接插入、冒泡或随机的快速排序。
- 若n较大，则应采用时间复杂度为O(nlogn)的排序方法：快速排序、堆排序或归并排序。快速排序被认为是目前基于比较的内部排序中较好的方法，当待排序的关键字随机分布时，快速排序的平均时间最短；但堆排序所需的辅助空间比快速排序少，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的，若要求稳定，则可选用归并排序。
- 若要将两个有序表合并成一个新的有序表，最好的方法是归并排序。
- 在基于比较的排序方法中，至少是需要O(nlogn)的时间。而基数排序只需要一步就会引起r种可能的转移，即把一个元素装入r个队列之一，因此一般情况下，基数排序可能在O(n)时间内完成对n个元素的排序。但遗憾的是，基数排序只适用于像字符串和整数这类有明显结构特征的关键字，而当关键字的取值范围属于某个无穷集合（例如实数型关键字）时，无法使用基数排序，这时只有借助于“比较”的方法来排序。由此可知，若n很大，元素的关键字位数较少且可以分解时，采用基数排序较好。
