Hexo

[TOC]

插入排序

直接插入排序

1
2
3
4
5
6
7
8
9
10
11
12
template<class > void InsertSort( Array[], int n) {
Record temp;
for (int i = 1; i < n; i++) {
temp = Array[i];
int j = i - 1;
while (j >= 0 && Array[j] > temp) {
Array[j + 1] = Array[j];
j--;
}
Array[j + 1] = temp;
}
}
  • 稳定

  • 空间代价:$O(1)$

  • 时间代价:

    • 最佳情况:$n-1$次比较,$2(n-1)$次移动,$O(n)$

    • 最差情况:$O(n^2)$

      • 比较次数为:$sum_{i=1}^{n-1}i=n(n-1)/2=O(n^2)$
      • 移动次数为:$sum_{i=1}^{n-1}=(n-1)(n+4)/2=O(n^2)$
      • 平均情况:$O(n^2)$

Shell希尔排序

算法步骤:

  1. 先将序列转化为若干小序列,在这些小序列内进行插入排序
  2. 逐渐增加小序列的规模,而减少小序列个数,使得待排序序列逐渐处于更有序的状态
  3. 最后对整个序列进行扫尾直接插入排序,从而完成排序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

template<class > void SheelSort( Array[], int n) {
int i, delta;
for (delta = n / 2; delta > 0; delta /= 2)
for (i = 0; i < delta; i++)
Mod_InsertSort(&Array[i], n - i, delta);
}
//修改过的直接插入排序
template<class > void Mod_InsertSort(Record Array[], int n, int delta) {
int i, j;
Record temp;
for (i = delta; i < n; i += delta) {
j = i - delta;
temp = Array[i];
while (j >= 0 && Array[j] > temp) {
Array[j + delta] = Array[j];
j -= delta;
}
Array[j + delta] = temp;
}
}
  • 不稳定
  • 空间代价:$O(1)$
  • 时间代价
    • 增量每次除以2递减,$O(n^2)$
      • 选取的增量之间并不互质,间距为$2^{k-1}$的子序列,都是由那些间距为$2^k$的子序列组成的,上一轮循环中这些子序列都已经排过序了,导致处理效率不高
    • 选择适当的增量序列,可以使时间代价接近$O(n)$
      • Shell(3)和Hibbard增量序列${2^k -1 ,2^{k-1},..,7,3,1}$的Shell排序的效率可以达到$O(n^{3/2})$
      • Shell最好的代价:呈$2^p 3^q$的一系列整数:${1,2,3,4,6,8,9,12}$,效率可达$O(nlog_2n)$

选择排序

直接选择排序

依次选出剩下的未排序记录中的最小记录

1
2
3
4
5
6
7
8
9
template<class Record> void SelectSort(Record Array[], int n) {
for (int i = 0; i < n - 1; i++) {
int smallest = i;
for (int j = i + 1; j < n; j++)
if (Array[j] < Array[smallest])
smallest = j;
swap(Array[i], Array[smallest]);
}
}
  • 不稳定
  • 空间代价:$O(1)$
  • 时间代价
    • 比较次数:$O(n^2)$
    • 交换次数:$n-1$
    • 总时间代价:$O(n^2)$

堆排序

基于最大堆来实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// just for HeapSort
template<class Record>
class Max_Heap {
private:
Record* array;
int node_num;
public:
Max_Heap(Record Array[], int n) {
array = Array;
node_num = n;
for (int i = n / 2; i >= 1; i--)
Shift_Down(i);
}
//节点的序号为1,2,3,4,5...
//数组的下标为0,1,2,3,4...
void Shift_Down(int k) {
if(node_num == 0) return;
Record temp = array[k - 1];
int i = k;
int j = 2 * k;
while (j <= node_num) {
if (j + 1 <= node_num && array[j] > array[j - 1])
j++;
if (array[j - 1] < temp)break;
array[i - 1] = array[j - 1];
i = j;
j = i * 2;
}
array[i - 1] = temp;
}
void RemoveMax() {
Record t = array[0];
array[0] = array[node_num - 1];
array[node_num - 1] = t;
node_num--;
Shift_Down(1);
}
};
//堆排序
template<class Record> void HeapSort(Record Array[], int n) {
int i;
Max_Heap<Record> max_heap = Max_Heap<Record>(Array, n);
for (i = 0; i < n - 1; i++)
max_heap.RemoveMax();
}
  • 不稳定
  • 空间代价为$O(1)$
  • 时间代价:
    • 建堆:$O(n)$,删除堆顶:$O(logn)$
    • 一次建堆,n次删除堆顶,总时间代价为$O(nlogn)$

交换排序

冒泡排序

算法思想:

  • 不停地交换相邻的记录,如果不满足排序要求,就交换相邻记录,知道所有的记录都已经排好序
  • 检查每次冒泡过程是否发生过交换,如果没有,则表明整个数组都已经排好序了,排序结束
1
2
3
4
5
6
7
8
9
10
11
12
13
14
template<class Record> void BubbleSort(Record Array[], int n) {
int i, j;
bool Noswap;
for (int i = 0; i < n - 1; i++) {
Noswap = true;
for (j = n - 1; j > i; j--) {
if (Array[j] < Array[j - 1]) {
swap(Array[j], Array[j - 1]);
Noswap = false;
}
}
if (Noswap)return;
}
}

算法分析:

  • 稳定
  • 空间代价:$O(1)$
  • 时间代价分析:
    • 比较次数:
      • 最少:$O(n)$
      • 最多:$sum_{i=1}^{n-1}(n-i)=n(n-1)/2=O(n^2)$
    • 交换次数最多为$O(n^2)$,最少为0,平均为$O(n^2)$
  • 时间代价结论
    • 最大,平均时间代价为$O(n^2)$
    • 最小时间代价为$O(n)$:最佳情况下只运行第一轮循环

快速排序

算法思想:

  • 选择轴值(pivot)
  • 将序列划分为两个子序列L和R,使得L中所有记录都小于或等于轴值,R中记录都大雨轴值
  • 对子序列L和R递归进行快速排序
image-20191010095315105

轴值选择:

  • 尽可能使L,R长度相等
  • 选择策略:
    • 选择最左边记录
    • 随机选择
    • 选择平均值
image-20191010095713077
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//选择轴值
int SelectPivot(int left, int right) {
return (left + right) / 2;
}
//分割函数,最右端为轴值,返回值为分界位置
template<class Record> int Partition(Record Array[], int left, int right) {
Record temp = Array[right];
while (left != right) {
while (Array[left] <= temp && left < right) left++;
if (left < right) Array[right] = Array[left], right--;
while (Array[right] >= temp && left < right)right--;
if (left < right)Array[left] = Array[right], left++;
}
Array[left] = temp;
return left;
}
template<class Record>void QuickSort(Record Array[], int left, int right) {
if (left >= right)return;
int pivot = SelectPivot(left, right);
swap(Array[pivot], Array[right]);
pivot = Partition(Array, left, right);
QuickSort(Array, left, pivot - 1);
QuickSort(Array, pivot + 1, right);
}

算法分析:

  • 长度为n的序列,时间为$T(n)$ ,那么 $T(0)=T(1)=1$

  • 选择轴值时间为常数

  • 分割时间为cn

    • 分割后的长度分别为$i$ 和$n-i-1$
    • 左右子序列$T(i)$和$T(n-i-1)$
  • 求解递推方程

    • 最差情况:
      $$
      begin{eqnarray}
      T(n)&=&T(i)+T(n-1-i)+cn
      T(n)&=&T(n-1)+cn
      T(n-1)&=&T(n-2)+c(n-1)
      T(n-2)&=&T(n-3)+c(n-2)
      &…
      T(2)&=&T(1)+c(2)
      end{eqnarray}
      $$
      总的时间代价为:$T(n)=T(1)+csum_{i=2}^{n}i=O(n^2)$

      空间代价:$O(n)$

    • 最佳情况:
      $$
      begin{eqnarray}
      T(n)&=&2T(n/2)+cn
      frac{T(n)}{n}&=&frac{T(n/2)}{n/2}+c
      frac{T(n/2)}{n/2}&=&frac{n/4}{n/4}+c
      &…
      frac{T(2)}{2}&=&frac{T(1)}{1}+c
      frac{T(n)}{n}&=&frac{T(1)}{1}+clog_n
      end{eqnarray}
      $$
      总的时间代价为:$T(n)=cnlog_n+n=O(nlog_n)$

      空间代价:$O(log_n)$

    • 平均情况下时间代价为:$T(n)=O(nlog_n)$,空间代价:$O(log_n)$

  • 快速排序可能的优化:

    • 轴值选择RQS
    • 小子串不递归(阈值28?)
    • 消除递归

归并排序

归并排序思想:

  1. 划分为两个子序列

  2. 分别对每个子序列归并排序

  3. 有序子序列合并

    image-20191013101646168

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template<class Record> void MergeSort(Record Array[], Record TempArray[], int left, int right) {
int mid;
if (left < right) {
mid = (left + right) / 2;
MergeSort(Array, TempArray, left, mid);
MergeSort(Array, TempArray, mid + 1, right);
Merge(Array, TempArray, left, right, mid);
}
}
template<class Record> void Merge(Record Array[], Record TempArray[], int left, int right, int mid) {
int i = left, j, index1 = left, index2 = mid + 1;
for (j = left; j <= right; j++)
TempArray[j] = Array[j];
while (index1 <= mid && index2 <= right)
Array[i++] = TempArray[index1] <= TempArray[index2] ? TempArray[index1++] : TempArray[index2++];
while (index1 <= mid) Array[i++] = TempArray[index1++];
while (index2 <= right) Array[i++] = TempArray[index2++];
}

归并算法优化:

  • 同优化的快速排序一样,对基本有序的序列直接插入排序
  • R.Sedgewick优化:归并时从两端开始处理,向中间推进,简化边界判断

image-20191013110021629

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//优化后的归并排序
const int MAXLENGTH = 5;
template<class Record> void ModMerge(Record Array[], Record TempArray[], int left, int right, int mid);
template<class Record> void ModMergeSort(Record Array[], Record TempArray[], int left, int right) {
int mid;
if (right - left + 1 > MAXLENGTH) {
mid = (left + right) / 2;
ModMergeSort(Array, TempArray, left, mid);
ModMergeSort(Array, TempArray, mid + 1, right);
ModMerge(Array, TempArray, left, right, mid);
} else InsertSort(&Array[left], right - left + 1);

}
template<class Record> void ModMerge(Record Array[], Record TempArray[], int left, int right, int mid) {
int i = left, j, index1 = left, index2 = right;
for (j = left; j <= mid; j++) TempArray[j] = Array[j];//正序复制左侧子序列
for (j = mid + 1; j <= right; j++)TempArray[right + mid + 1 - j] = Array[j]; //倒序复制右侧子序列
while (i <= right)
Array[i++] = TempArray[index1] <= TempArray[index2] ? TempArray[index1++] : TempArray[index2--];
}

算法复杂度分析:

  • 空间代价:$O(n)$

  • 时间代价:$O(nlog_n)$

  • 不依赖原始数组的输入情况,最大、最小以及平均时间代价均为$O(nlog_n)$