排序算法总结

选择排序

选择排序是最简单的排序算法,其想法是对序列A[1]-a[n],进行n趟排序,每趟排序在[i,n]中选择最小元素,将其放到A[i]。对于第i趟排序,排序后a[1]-a[i]即为有序的序列。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void selectSort()
{
for(int i =1;i<=n;i++)
{
k = i;
for(int j=i;j<=n;j++)
if(A[j]<a[k])
k=j;
// 选出[i,n]中最小的元素,下标为k。然后进行交换
int tmp = A[i];
A[i] = A[k];
A[k] = tmp;
}
}

复杂度为O(n2)O(n^2)

插入排序

插入排序的想法和平时玩扑克牌的排序方式很相似。假设A[1]-A[i]是已经有序的,则将A[i+1]移入到有序序列中的正确位置,即把A[i+1]保存于tmp,A[1]-A[i]中大于A[i+1]的逐个往后移,最后将A[i+1]放入空位,由此A[1]-A[i+1]变为有序。

代码

1
2
3
4
5
6
7
8
9
10
11
12
void insertionSort(ElementType A[],int N)
{
int j,P;
ElementType tmp;
for(P=1;P<N;P++)
{
tmp = A[P];
for(j=P;j>0&&A[j-1]>tmp;j--)
A[j] = A[j-1];
A[j] = tmp;
}
}

复杂度O(n2)O(n^2)

希尔排序

希尔排序(Shellsort)是最早冲破二次时间屏障的算法之一。它通过比较相距一定间隔的元素来工作,各趟比较所用的距离随着算法的进行而减小,直到最后一趟排序只比较相邻元素。因此,希尔排序也称最小增量排序。

令$h_1,h_2,…h_t $ 为增量序列increment sequence。只要h1=1h_1=1,任何增量序列都是可行的。在使用hkh_k 的一趟排序后,对于每个i都有A[i]A[i+hk]A[i]\le A[i+h_k] 成立。增量序列一种流行,但是不好的选择是ht=N/2h_t = \lfloor N/2 \rfloor 和$h_k=\lfloor h_{k+1} /2 \rfloor $ 。希尔排序的运行时间倚赖于增量序列的选择,其证明相当复杂。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void shellSort(ElementType A[],int N)
{
int i,j,Increment;
ElementType tmp;
for(Increment = N/2;Increment > 0;Increment /=2)
for(i = Increment;i<N;i++)
{
tmp = A[i];
for(j=1;j>=Increment;j-=Increment)
if(tmp<A[j-Increment])
A[j]=A[j-Increment];
else
break;
A[j]=tmp;
}
}

堆排序

优先队列可以花费O(NlogN)O(N\log N) 的时间排序。基于该想法的算法叫堆排序。

待完整。。

代码

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
#define LeftChild(i)(2*(i)+1)
void PercDown(ElementType A[],int i,int N)
{
int Child;
ElementType tmp;
for(tmp=A[i];LeftChild(i)<N;i=Child)
{
Child = LeftChild(i);
if(Child!=N-1 && A[Child+1]>A[Child])
Child++;
if(tmp<A[Child])
A[i]=A[Child];
else
break;
}
A[i]=tmp;
}

void Heapsort(ElementType A[],int N)
{
int i;
for(i = N/2;i>=0;i--)
PercDown(A,i,N);
for(i = N-1;i>0;i--)
{
Swap(&A[0],&A[i]);
PercDown(A,0,i);
}
}

归并排序

归并排序以O(NlogN)O(N\log N) 的最坏运行时间运行。该算法采用经典的分治策略。

快速排序

快速排序是在实践中最快的已知排序算法,它的平均运行时间是O(NlogN)O(N\log N)

将数组S排序的基本算法由以下四步组成:

  1. 如果S中元素的个数是0或1,返回。
  2. 取S中任一元素v,称之为枢纽元pivot。
  3. 把S中的其余元素分为两个不相交的集合:S1={xS{v}xv}S_1=\{ x \in S -\{v\} | x \le v\}S2={xS{v}xv}S_2=\{ x \in S -\{v\} | x \geq v\}
  4. 返回quicksort(S1S_1)后继续quicksort(S2S_2) 。

与归并排序不同的是S1和S2的这两个子问题并不一定相等,这是导致快排超时的潜在隐患。

除此之外,枢纽元的选取也很重要我,错误的方法是将第一个元素选为枢纽元,如果序列是一些逆序数,则直接进入最坏状况。可以使用三数中值分割法,选取最左边,最右边和中间的元素比较, 以三个数的中间数作为枢纽元,可以消除最坏情形。

代码

1
2


桶排序

外部排序

C++ STL sort

使用sort函数首先需要加上头文件#include 和 using namespace std;

sort使用方式:sort(首元素地址,尾元素地址,比较函数(非必需))

默认的比较函数是<

也可以自己完善比较函数,例如从大到小排序

1
2
3
4
5
bool cmp(int a,int b)
{
return a>b;
}
sort(a,a+4,cmp);

当使用结构体时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct node{
int x,y;
}ssd[10];

bool cmp(node a,node b)
{
return a.x > b.x;
}

sort(ssd,ssd+3,cmp);

//还可以:先比较node中x的大小,如不相等直接按x排序,若x相等则按y排序。
bool cmp(node a,node b)
{
if(a.x != b.x)
return a.x>b.x;
else
return a.y>b.y;
}

vector、string、deque也是可以使用sort排序的,而set、map是以红黑树实现,元素本身有序,故不能用sort排序。

Copyright © 2011 - 2018 活在梦里 All Rights Reserved.

myth 保留所有权利