排序

发表于 | 更新于 | 分类于

插入排序

$O(n^2)$

1
2
3
4
5
6
7
8
9
10
11
12
void insertion_sort()
{
	int i, j;
	cout << "insertion_sort:\n";
	for(i = 1; i < N; i ++ )
	{
		int t = a[i];
		for(j = i - 1; j >= 0 && t < a[j]; j -- )
			a[j + 1] = a[j];
		a[j + 1] = t;
	} 
}

归并排序

$O(nlogn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void merge_sort(int l, int r)
{
	if(l == r)	return;
	int mid = l + r >> 1;
	merge_sort(l, mid);
	merge_sort(mid + 1, r);
	int i = l, j = mid + 1, k = 0; 
	while(i <= mid && j <= r)
		if(a[i] <= a[j])
			w[k ++ ] = a[i ++ ];
		else
			w[k ++ ] = a[j ++ ];		// cnt += mid – i + 1 归并排序求逆序对
	while(i <= mid)		w[k ++ ] = a[i ++ ];
	while(j <= r)		w[k ++ ] = a[j ++ ];
	for(i = l, j = 0; j < k; i ++, j ++ )
		a[i] = w[j];
}

$O(nlogn)$

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
void quick_sort(int l, int r)
{
    if(l >= r)  return ;
    int i = l - 1, j = r + 1, x = a[i + j >> 1];
    while(i < j)		//以中间点为基准，小于的放x左边，大于放右边，
				//遇到不满足情况两指针都停下来，若i < j则交换，否则以i为基点左右递归
    {
        do j --; while(a[j] > x);
        do i ++; while(a[i] < x);
        if(i < j)   swap(&a[i], &a[j]);
        else quick_sort(l, j), quick_sort(j + 1, r);
    }
}

(shell)希尔排序

$O(n^{1.3}) ~ O(n^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void shell_sort()
{
    int gap, i, j, t;
    gap = 1;
    while(gap < N / 3)
        gap = gap * 3 + 1;
    while(gap)
    {
        for(int i = gap; i < N; i ++ )
        {
            t = a[i];
            for(j = i - gap; j >= 0 && t < a[j]; j -- )
                a[j + gap] = a[j];
            a[j + gap] = t;    
        }
        gap >>=  1;
    }
}

堆排序

$O(nlogn)$

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
#include <iostream>
#include <algorithm>
using namespace std;
int h[100006], n;
void down(int u)		//down操作, 往下调整顺序，递归操作实现(循环也可)
{
    int t = u;		//找到父亲与儿子节点中最小的节点
    int l = u * 2, r = u * 2 + 1;	
    if(l <= n && h[l] < h[t])    t = l;     
    if(r <= n && h[r] < h[t])    t = r;
    if(t != u)		//不同则交换
    {
        swap(h[u], h[t]);
        down(t);		//继续down儿子中较大的点
    }
}
int main()
{
    int m;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ )   scanf("%d", &h[i]);
    for (int i = n / 2; i; i -- ) down(i);			//前从下到上前n - 1个建堆方式，接近O(n)
    while(m -- )	//输出前m个小的
    {
        printf("%d ", h[1]);
        swap(h[1], h[n -- ]);
        down(1);
    }
    return 0;
}

0%