常用的排序算法大汇总(C++语言实现)

排序方法 是否基于分治 是否原地 最好情况运行时间 最坏情况运行时间 平均情况运行时间
插入排序 n n2 n2
归并排序 nlog(n) nlog(n) nlog(n)
堆排序 nlog(n) nlog(n) nlog(n)
快速排序 nlog(n) n2 nlog(n)
冒泡排序 n n2 n2

测试环境

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
using namespace std;
#define INT_INFINITY 0x7FFFFFFF // assume int has 32 bit
#define INT_EXCHANGE(X,Y) if((X)!=(Y)) { (X) ^= (Y); \
(Y) ^= (X); \
(X) ^= (Y); }


template <class T> T* const toArray(vector<T> &va)
{
int len = va.size();
T* array = new T[len];
for(int i=0;i<len;i++)
array[i] = va.at(i);
return array;
}

#define PRINT_BEFORE cout<<"Before sort:"<<endl
#define PRINT_AFTER cout<<"After sort:"<<endl
#define PRINT_ARRAY(X,LEN) { for(int i=0;i<LEN;i++) cout<<X[i]<<' '; \
cout<<endl; }

const string src("87 23 546 123 467 65 7 1593 223 62 895 60");

int main()
{
vector<int> va;
istringstream sin(src);
int i;
while(sin >> i) va.push_back(i);
int* const array = toArray(va);
int len = va.size();
PRINT_BEFORE;
PRINT_ARRAY(array,len);
// call sort functions here:
//insert_sort(array,len);
//merge_sort(array,0,len-1);
//heap_sort(array,len);
//quick_sort(array,0,len-1);
//bubble_sort(array,len);
PRINT_AFTER;
PRINT_ARRAY(array,len);
delete[] array;
system("pause");
}

插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*****************************************************
insert sort
*****************************************************/
void insert_sort(int* array, int len)
{
for(int i=1;i<len;i++)
{
int key = array[i];
int j = i - 1;
while(j>=0 && array[j]>key)
{
array[j+1] = array[j];
j--;
}
array[j+1] = key;
}
}

归并排序

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
32
33
34
/*****************************************************
merge sort
*****************************************************/
void merge_sort(int* array, int start, int end)
{
if(start >= end) return;
int mid = (start+end)/2;
merge_sort(array,start,mid);
merge_sort(array,mid+1,end);

int leftlen = mid-start+1;
int rightlen = end-mid;

int* left = new int[leftlen+1];
int* right = new int[rightlen+1];

for(int i=0;i<leftlen;i++)
left[i] = array[i+start];
for(int i=0;i<rightlen;i++)
right[i] = array[i+mid+1];

left[leftlen] = INT_INFINITY;
right[rightlen] = INT_INFINITY;

int i = 0,j = 0;
for(int k=start;k<=end;k++)
if(left[i]<right[j])
array[k] = left[i++];
else
array[k] = right[j++];

delete[] left;
delete[] right;
}

堆排序

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/*****************************************************
heap sort
*****************************************************/
// the heap is a zero-index-based array
#define PARENT(i) ((i-1)/2)
#define LEFT(i) (2*i+1)
#define RIGHT(i) (2*i+2)
// assume the sub-trees rooted by the children of i are max-heaps
// then this function maintain the sub-tree rooted by node i a max-heap
// note: a max-heap guarantee the parent is greater than the children
void max_heapify(int* array, int heapsize, int i)
{
int left = LEFT(i);
int right = RIGHT(i);
int max = i;
if(left<heapsize && array[left]>array[max])
max = left;
if(right<heapsize && array[right]>array[max])
max = right;

if(max == i) return;
INT_EXCHANGE(array[i],array[max]);
max_heapify(array,heapsize,max);
}

// build a max-heap from a random array
// just call max_heapify to every non-leaf node by reverse order
// note: the last non-leaf node is floor(len/2)-1
void build_max_heap(int* array, int len)
{
for(int i=len/2-1;i>=0;i--)
max_heapify(array,len,i);
}

// note: the root of the heap tree is always the maximum
void heap_sort(int* array, int len)
{
build_max_heap(array,len);
int heapsize = len;
for(int i=heapsize-1;i>=1;i--)
{
INT_EXCHANGE(array[0],array[i]);
heapsize--;
max_heapify(array,heapsize,0);
}
}

快速排序

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
/*****************************************************
quick sort
*****************************************************/
// locally rearrange the array, return a mid index
// guarantee the members before mid is less than array[mid]
// and the members after mid is greater than array[mid]
int partition(int* array, int start, int end)
{
int mid = end;
int midkey = array[mid];
int i = start;
for(int j=start;j<=end-1;j++)
if(array[j]<midkey)
{
INT_EXCHANGE(array[i],array[j]);
i++;
}
INT_EXCHANGE(array[i],array[mid]);
return i;
}

void quick_sort(int* array, int start, int end)
{
if(start >= end) return;
int mid = partition(array,start,end);
quick_sort(array,start,mid-1);
quick_sort(array,mid+1,end);
}

冒泡排序

1
2
3
4
5
6
7
8
9
10
/*****************************************************
bubble sort
*****************************************************/
void bubble_sort(int* array, int len)
{
for(int i=len-1;i>0;i--)
for(int j=0;j<i;j++)
if(array[j]>array[j+1])
INT_EXCHANGE(array[j],array[j+1]);
}