排序/Sort

发表于 更新于 分类于 ， 阅读次数： 本文字数： 439 阅读时长 ≈ 2 分钟

开个贴，写一些排序相关的东西

c的qsort()与c++的st::sort()：

实际上sort比快排qsort还要快，因为c++对sort()函数进行了优化，在C++11标准中排序的复杂度在最坏情况下为 O(nlogn),二者差距一到二个数量级。

参考链接

选择排序 Selection sort

找到最值，与第一个指针交换。

$\mathbf{time}:best:\omicron(n),worst:\omicron(n^2)$

$\mathbf{spcae}:\omicron(1)$

插入排序 Insertion sort

找到最值，移动数组，插入空隙。

$\mathbf{time}:best:\omicron(n),worst:\omicron(n^2)$

$\mathbf{spcae}:\omicron(1)$

Compara Selection sort with Insertion sort

希尔排序 Shell sort

让每间隔 $h$ 的小数组是有序的，那么整体就是有序的$（当 h \rightarrow 1）$

复杂度与 $h$ 有关。

$\mathbf{time}:best:\omicron(nlog n),worst:\omicron(n^2)$

$\mathbf{spcae}:\omicron(1)$

归并排序 Merge sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//需要tmp[]数组
void merge_sort(int q[],int l,int r){
	if(l>=r)return;

	int mid=l+r>>1;
	merge_sort(q,l,mid);
	merge_sort(q,mid+1,r);

	int k=0,i=l,j=mid+1;
	while(i<=mid && j<=r)
		if (q[i]<=q[j])tmp[k++] =q[i++];
		else tmp[k++]=q[j++];

	while(i<=mid)tmp[k++]=q[i++];
	while(j<=r)tmp[k++]=q[j++];

	for(i=l,j=0;i<=r;i++,j++)q[i]=tmp[j];
}

适用分而治之的方法（两两排序、归并、再排序、再归并）（可用简单排序归并）

快排 Quick sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*Lomuto，选自ACwing*/
void quick_sort_(int q[], int l, int r)//左右指针向内运动，相遇终止
{
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

将数据分区，（小于<->大于）/（小于<->等于<->大于），再分而治之。

分区方案有：Lomuto partition scheme & Hoare partition scheme:

Lomuto：

Lomuto

Hoare：

hoare

堆排 Heap sort