0%

算法笔记(01):排序算法

更新:

删去了其他比较trivial的排序,留下了算法竞赛中用的略微多的排序思维。

删掉了useless的排序方法(希尔等等)。

修正了代码语言,Java语言由于当时第一版所写的错误过多,因而删除,再加上在运行速度上不及C++。

1.快速排序

是一种基于分治的排序方法。

思路

对需要排序的区间[l,r]进行下面的操作:

(1) 如果区间长度小于等于1直接退出,否则在区间中选择一个数字x作为比较元素。

(2) 将大于x的数字放右边,小于x的数字放左边,等于x的可左可右,将x放在两组数字中间。

**(3)**此时x的位置确认,对其左右两边的区间分别进行递归即可。

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void quicksort(int l,int r) {
if(l >= r) return;
std::swap(a[l], a[l + rand() % (r - l + 1)]);
int x = a[l];
int i = l,j = r;
while(i < j) {
while(i < j && a[i] > x) {
j--;
if(i < j) {
a[i++] = a[j];
}
}
while(i < j && a[i] < x) {
i++;
if(i < j) {
a[j--] = a[i];
}
}
}
a[i] = x;
quicksort(l, i - 1);
quicksort(i + 1, r);
}

2.归并排序

是一种基于分治的排序方法。

思路

对需要排序的区间[l,r]进行下面的操作:

(1) 如果区间长度小于等于1直接退出,否则将区间分为[l,m],[m + 1,r]两个部分,其中 m = (l + r) / 2。

(2) 递归对两个子区间进行归并排序。

(3) 将两个已经排好序的子区间进行合并。

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void mergesort(int l,int r) {
if(l == r) return;
int m = (l + r) / 2;
mergesort(l,m);
mergesort(m + 1, r);
int p1 = l, p2 = m + 1,tot = 0;
while(p1 <= m && p2 <= r) {
if(a[p1] <= a[p2])
c[++tot] = a[p1++];
else
c[++tot] = a[p2++];
}
while(p1 <= m)
c[++tot] = a[p1++];
while(p2 <= r)
c[++tot] = a[p2++];
for(int i=1;i <= tot; i++) {
a[i + l - 1] = c[i];
}
}

3.计数排序

思路

计数排序适合于值域范围校的数字排序

(1) 统计每个数字出现了几次。

(2) 统计完每个元素的出现次数后,求一边前缀和,我们就知道了每个数字在排完序后的序列中出现位置的范围。

(3) 把数字填入对应的位置即可。

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#define endl "\n"
int n, m, a[N + 1], c[M + 1], r[N + 1];

inline void countingsort() {
memset(c,0,sizeof(c));
for(int i=1;i<=n;i++) {
++c[a[i]];
}
for(int i=1;i<=m;i++)
for(int j=1;j<=c[i];j++)
std::cout << i << " ";
std::cout << endl;

for(int i=2;i<=m;i++) {
c[i] += c[i - 1];
}
for(int i=n; i; --i) {
r[i] = c[a[i]]--;
}
for(int i=1;i<=n;i++) {
std::cout << r[i] << " ";
}
std::cout << endl;
}

4.基数排序

思路

将每个待排序的元素拆分成m个关键字,然后从后往前依次对这m个关键字进行排序。

特别的

(基数排序经常被用于进行字符串的排序,比如说后缀数组的核心就是基数排序)。

(1) 我们只要把数字按第 i 个及以后的关键字从小到大的顺序放到数组里,再做一次计数排序就好。

代码
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 n, m, a[N + 1], sa[N + 1], v[N + 1], r[N + 1], c[10];

inline void countingsort() {
memset(c,0,sizeof(c));
for(int i=1;i<=n;i++)
++c[v[i]];
for(int i=1;i<=9;i++)
c[i] += c[i - 1];
for(int i=n;i;--i)
r[sa[i]] = c[v[sa[i]]]--;
for(int i=1;i<=n;i++)
sa[r[i]] = i;
}

inline void radixsort() {
for(int i=1;i<=n;i++)
sa[i] = i;
int x = i;
for(int i=1;i<=m;i++,x *= 10) {
for(int j=i;j<=n;j++)
v[j] = a[j] / x % 10;
countingsort();
}
}