数组排序

  |  

$0 关于排序稳定性的结论

不稳定的排序,都可以通过多关键字排序的办法变成稳定排序(第二个关键字是数组下标)

  • 稳定排序:插入排序,基数排序,归并排序,冒泡排序,计数排序
  • 不稳定的排序:快速排序,希尔排序,选择排序,堆排序

$1 基于比较的排序

$1.1 基于插入

插入排序

常用,因为最好情况下的时间复杂度是 O(N), 而最好情况比较容易达到。C++ STL 的 sort 函数基于快排,但又很多特判,当快排递归到的数组长度变得较小的时候会调用插入排序

平均和最坏时间复杂度 $O(N^{2})$,最好时间复杂度 $O(N)$

  • 数组的插入排序,新来一个元素从后往前比,如果更小的话就交换
  • 链表的插入排序,新来一个元素,从前往后找插入位置,然后对链表节点做删除和插入
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    void insertsort(vector<int>& nums)
    {
    if(nums.empty()) return;
    int n = nums.size();
    if(n == 1) return;
    for(int i = 1; i < n; ++i)
    {
    int tmp = nums[i];
    int j;
    for(j = i - 1; j >= 0 && nums[j] > tmp; --j)
    nums[j + 1] = nums[j];
    nums[j + 1] = tmp;
    }
    }

希尔排序

第一个平均时间复杂度突破 $O(N^{2})$ 的排序(O(N^{1.3})),1959 年。现在已经基本淘汰了。思想就是在做基本插入排序之前先让数组大致有序。

最好还是 $O(N)$, 最坏还是 $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
void shellsort(vector<int>& nums)
{
if(nums.empty()) return;
int n = nums.size();
if(n == 1) return;

// 选取 step 与算法复杂度证明有关,参考算法导论
int step = 1;
while(step < n / 3)
step = step * 3 + 1;

// for(int step = n / 2; step > 0; step /= 2)
for(; step > 0; step /= 3)
{
for(int i = step; i < n; ++i)
{
int tmp = nums[i];
int j = i - step;
for(; j >= 0 && nums[j] > tmp; j -= step)
nums[j + step] = nums[j];
nums[j + step] = tmp;
}
}
}

$1.2 基于选择

选择排序

每次都从剩下的数里找一个最小的

平均,最坏,最好时间复杂度均为 $O(N^{2})$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void selectsort(vector<int> &nums)
{
if(nums.empty()) return;
int n = nums.size();
if(n == 1) return;
for(int i = 0; i < n; ++i)
{
int tmp = nums[i];
int min_index = i;
for(int j = i + 1; j < n; ++j)
{
// i ~ n 最小的数放到 i 位置
if(nums[j] < tmp)
{
tmp = nums[j];
min_index = j;
}
}
_swap(nums, i, min_index);
}
}

堆排序

(1) 基本堆操作

push_uppush_down

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void push_down(vector<int>& heap, int size, int u)
{
int t = u, left = u * 2, right = u * 2 + 1;
if(left <= size && heap[left] > heap[t]) t = left;
if(right <= size && heap[right] > heap[t]) t = right;
if(t != u)
{
swap(heap[u], heap[t]);
push_down(heap, size, t);
}
}

void push_up(vector<int>& heap, int size, int u)
{
if(u > size) return;
while(u / 2 && heap[u / 2] < heap[u])
{
swap(heap[u / 2], heap[u]);
u /= 2;
}
}

插入和删除

1
2
3
4
5
6
7
8
9
10
11
void insert(vector<int>& heap, int size, int x)
{
heap[++size] = x;
push_up(heap, size, x);
}

void remove_top(vector<int>& heap, int size)
{
heap[1] = heap[size--];
push_down(heap, size, 1);
}

(2) 堆排序

注意建堆的这一步 for(int i = size; i >= 1; --i) push_down(heap, size, i); 时间复杂度是 $O(N)$ 而不是 $O(N\log N)$。证明涉及到数列求和。

平均,最好,最坏的时间复杂度均为 $O(N\log N)$。

  • 数组的堆排序,因为堆是完全二叉树,本身一般就是在数组实现,因此堆排序可以本地实现,空间 O(1)。
  • 链表的堆排序,需要额外的空间建堆,空间 O(N) 空间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void heapsort(vector<int>& nums)
{
if(nums.empty()) return;
int n = nums.size();
_heapsort(nums, n);
}

void _heapsort(vector<int>& heap, int size)
{
heap.push_back(0);
int n = size;
for(int i = n - 1; i >= 0; --i) heap[i + 1] = heap[i]; // 堆中元素在内部数组中的下标从 1 开始
for(int i = 1; i <= size; ++i) push_down(heap, size, i); // 时间复杂度 O(N) 不是 O(NlogN)
for(int i = n; i >= 1; --i)
{
swap(heap[1], heap[size--]);
push_down(heap, size, 1);
}
for(int i = 0; i < n; ++i) heap[i] = heap[i + 1];
heap.pop_back();
}

堆排序一般不单独用于排序,而是在 topK 及其变种问题上常用:topK问题分类汇总

$1.3 基于交换

最坏和平均时间复杂度为 $O(N^{2})$,最好时间复杂度为 $O(N)$

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void bubblesort(vector<int>& nums)
{
if(nums.empty()) return;
int n = nums.size();
if(n == 1) return;
int i, j;
bool flag; // 记录一趟起泡时有无交换, 冒泡排序的基本优化
// for(i = 1; i < n; ++i)
for(i = n - 1; i >= 1; --i)
{
flag = false;
// for(j = 0; j < n - i; ++j) // 第 i 次起泡
for(j = 0; j <= i - 1; ++j) // 第 i 次起泡
{
if(nums[j + 1] < nums[j])
{
_swap(nums, j, j + 1);
flag = true;
}
}
if(!flag) break;
}
}

快速排序

快速排序的最好和平均时间复杂度是 $O(N\log N)$,最坏时间复杂度是 $O(N^2)$

快速排序在最坏的情况下是 $O(N^2)$ 的,但是最坏情况极难达到,且可以通过随机选 pivot 点避免,所以说快排时间复杂度时候一般是说 $O(N\log N)$。

快排有很多实现方式,主要有两个维度:

  • 递归版,非递归版(开栈保存区间端点)
  • 双指针 partition 操作;单指针 partition 操作 (单链表的快排只能用单指针 partition 操作)

(2) partition 操作

  • 单指针划分
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int divide1(vector<int>& nums, int low, int high)
{
// 单指针划分
int randIdx = rand() % (high - low + 1) + low; // 随机选择 pivot
_swap(nums, randIdx, low);
int pivot = nums[low]; // 标准元素, 支点元素取最左边
int index = high;
for(int i = high; i > low; --i)
{
if(nums[i] >= pivot)
{
_swap(nums, i, index);
--index;
}
}
_swap(nums, index, low);
return index;
}
  • 双指针划分
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
int divide2(vector<int>& nums, int low, int high)
{
// 双指针划分
int randIdx = rand() % (high - low + 1) + low; // 随机选择 pivot
_swap(nums, randIdx, low);
int pivot = nums[low]; // 标准元素, 支点元素取最左边
while(low < high)
{
while(low < high && nums[high] >= pivot)
--high;
if(low < high)
{
nums[low] = nums[high];
++low;
}
while(low < high && nums[low] <= pivot)
++low;
if(low < high)
{
nums[high] = nums[low];
--high;
}
}
nums[low] = pivot;
return low;
}

partition 算法是一种减治算法,这种减治的思想在其它问题中经常有用,例如:力扣215-快速选择算法,划分树

(2) 快排

1
2
3
4
5
6
7
8
// 快排
void quicksort(vector<int> &nums)
{
if(nums.empty()) return;
int n = nums.size();
if(n == 1) return;
_quicksort3(nums, 0, n - 1);
}
  • 递归
1
2
3
4
5
6
7
8
9
void _quicksort1(vector<int> &nums, int low, int high)
{
// 递归
int mid;
if(low >= high) return;
mid = divide1(nums, low, high); // 分治的划分点 mid 不一定是数组中点,而是与 pivot 元素具体值有关系
_quicksort1(nums, low, mid - 1); // 排序左边一半
_quicksort1(nums, mid + 1, high);
}
  • 非递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void _quicksort2(vector<int>& nums, int low, int high)
{
// 非递归版快排
stack<int> st;
st.push(low);
st.push(high);
while(!st.empty()){
int r = st.top();
st.pop();
int l = st.top();
st.pop();
if(l >= r) continue;
int mid = divide1(nums, l, r);
st.push(l);
st.push(mid - 1);
st.push(mid + 1);
st.push(r);
}
}
  • 快排最短模板, 不带 partition
1
2
3
4
5
6
7
8
9
10
11
12
13
// 快排最短模板, 不带 partition
void _quicksort3(vector<int>& nums, int l, int r)
{
if(l >= r) return;
int i = l - 1, j = r + 1, x = nums[(l + r) >> 1];// pivot 取中间点的值已经很好了,随机更好
while(i < j)
{
do j--; while(nums[j] > x);
do i++; while(nums[i] < x);
if(i < j) _swap(nums, i, j);
else _quicksort3(nums, l, j), _quicksort3(nums, j + 1, r); // 这一行代替了 partition
}
}

1.4 归并排序

归并排序的最好,最坏,平均时间复杂度均为 $O(N\log N)$。

归并排序有两种实现方式:自底向上和自顶向下。空间复杂度上都是自底向上更好。

(1) 归并操作

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
// 非常经典的归并操作
// 类似问题例如链表的二路归并,多路归并等
void _merge(vector<int>& nums, int low, int mid, int high)
{
// 归并时候的辅助数组
vector<int> tmp(high - low + 1, 0);
// 下面这么写的话,往辅助数组里插入需要 push_back
// static vector<int> tmp;
// tmp.clear();

int i = low, j = mid, k = 0;
while(i < mid && j <= high)
{
if(nums[i] < nums[j])
{
tmp[k] = nums[i];
++k;
++i;
}
else
{
tmp[k] = nums[j];
++k;
++j;
}
}
while(i < mid) tmp[k++] = nums[i++];
while(j <= high) tmp[k++] = nums[j++];
for(k = 0, i = low; i <= high; ++k, ++i)
nums[i] = tmp[k];
}

(2) 归并排序

1
2
3
4
5
6
7
8
9
// 归并, 两种实现方式, 自顶向下
void mergesort(vector<int>& nums)
{
if(nums.empty()) return;
int n = nums.size();
if(n == 1) return;
// _mergesort_topdown(nums, 0, n - 1);
_mergesort_buttomup(nums, n);
}

自顶向下

1
2
3
4
5
6
7
8
9
// 自顶向下
void _mergesort_topdown(vector<int>& nums, int low, int high)
{
int mid = low + (high - low) / 2;
if(low == high) return;
_mergesort_topdown(nums, low, mid);
_mergesort_topdown(nums, mid + 1, high);
_merge(nums, low, mid + 1, high); // 归并左右两个有序表
}

自底向上

1
2
3
4
5
6
7
8
9
10
11
12
// 自底向上
void _mergesort_buttomup(vector<int >& nums, int n)
{
int left, size;
for(size = 1; size < n; size *= 2)
for(left = 0; left < n - size; left += 2 * size)
{
int right = min(left + 2 * size - 1, n - 1);
int mid = left + size - 1; // mid > right 时,直接就是半边有序的
_merge(nums, left, mid + 1, right);
}
}

一般写排序不会写归并排序,但是很多分治算法都基于归并排序的思想:分的阶段进行排序,合的阶段做归并同时借助有序的特性更高效地统计目标信息。

例如求数组中的逆序对个数(剑指 Offer 51. 数组中的逆序对),这个问题等价于对数组做冒泡排序一共需要执行交换的次数。


Share