【算法课作业】那些排序算法

Filed in: 数据结构与算法 Add comments

第二次上课的作业之一是实现所有会的排序算法（之二是实现查找欧拉回路的算法），用了总计大概两天的时间写好了这九个排序算法。没有一个算法是一次通过的，都经过了调试，甚至冒泡，而且后来才发现我第一次写的冒泡程序竟然是错误的，囧。
这还是第一次把这些算法全部亲手实现，收获还是很大的，真的加深了理解。期待通过这门课有效地提高自己的编程能力。
废话不说，上代码。
以下算法，没给出参数的默认排序范围为data[]的第0位到第N位。有些采用分治思想的算法需要范围参数，如快排和归并。
为了优化，在递归过程中如果待排序长度较短则使用插入排序代替递归，因此插入排序函数有一个带参数版本为此所用。桶排序需要一个算法实现桶内排序，这里选择了快排，因此快排有一个带三个参数的重载版本。
另外堆排序的实现用了一个类加一个外部函数。
genData函数用于生成随机数据；
check函数用于检查数据是否有序；
exchange函数用于交换两个数据；
show函数用于打印；
digit函数返回数据的某一位（用于基数排序）；

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

#include <cstdlib>
#include <iostream>
#include <time.h>
 
using namespace std;
 
#define N 10000000
#define MAX 100000
 
int data[N];
 
void genData()				//~generate data
{
	srand((unsigned)time(NULL));
	for(int i = 0;i < N;i++)
	{
		data[i] = rand()%MAX; 		 
	}
}
 
void show()					//~show the data sequentially
{
 	 for(int i = 0;i < N;i++)
	     cout<<data[i]<<"\t";
	 cout<<endl; 	 
}
 
void show(int i,int j)
{
 	for(int k = i;k <= j;k++)
	    cout<<data[k]<<"\t";
	cout<<endl;	 
}
 
void exchange(int i,int j)	//~exchange two data by index,too frequently used
{
 	 int t;
 	 t = data[i];
 	 data[i] = data[j];
 	 data[j] = t;
}
 
void exchange(int i,int j,int* data)	//for BucketSort's QuickSort's use
{
 	int t = data[i];
	data[i] = data[j];  
	data[j] = t;
}
 
void check()	//~show if the data is sorted
{
	for(int i = 0;i < N-1;i++)
	{
		if(data[i] > data[i+1])
		{
			cout<<"unsorted!"<<endl;
			return; 		   
		}	
	} 	 
	cout<<"sorted!"<<endl;
}

1.冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

void BubbleSort()
{
	int t;
	for(int i = N-1;i > 0;i--)
	{
		for(int j = 0;j < i;j++)
		{
			if(data[j] > data[i])
			{
				t = data[i];
				data[i] = data[j];
				data[j] = t; 			
			} 		  		 
		} 		 
	}
}

2.插入排序

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

void InsertionSort(int l,int r)
{
	int t;
	int pos = l+1;	//pos as the beginning of the unsorted area 
	for(int i = pos;i <= r;i++)
	{
		t = data[i];
		int j;
		for(j = i - 1;j >= l && data[j] > t;j--)
		{
			data[j+1] = data[j];
		}
		data[j+1] = t;  		 
	}
}
 
void InsertionSort()
{
	int t;
	int pos = 1;	//pos as the beginning of the unsorted area 
	for(int i = pos;i < N;i++)
	{
		t = data[i];
		int j;
		for(j = i - 1;j >= 0 && data[j] > t;j--)
		{
			data[j+1] = data[j];
		}
		data[j+1] = t;  		 
	}
}

3.选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

void SelectionSort()
{
	int t; 
	int pos = 0,min = MAX + 1;
	for(int i = 0;i < N;i++)
	{
		min = MAX + 1;
		for(int j = i;j < N;j++)
		{
			if(data[j] < min)
			{
				pos = j;
				min = data[j]; 		   
			} 		
		}
		exchange(pos,i);
	}  
}

4.快速排序

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

void QuickSort(int l,int r,int* data)	//this version of QuickSort is for BucketSort's use
{
	int length = r-l+1;
	// when length <= 20,use InsertionSort instead.
	/*if(length <= 20)
	{
	InsertionSort(l,r);
	return; 		   
	}*/
	if(length <= 1)
		return;
 
	int pos = rand()%(r - l + 1) + l;
 
	exchange(l,pos,data);
 
	int i = l+1,j = r;
 
	while(i <= j)
	{
		while(data[i] <= data[l] && i <= r)
			i++;
		while(data[j] >= data[l] && j >= l+1)
			j--;
		if(i < j)
			exchange(i,j,data); 	
	}
	exchange(l,j,data);
 
	QuickSort(l,j-1,data);
	QuickSort(j+1,r,data);
}
 
void QuickSort(int l,int r)
{
	int length = r-l+1;
	// when length <= 20,use InsertionSort instead.
	if(length <= 20)
	{
		InsertionSort(l,r);
		return; 		   
	}
 
	int pos = rand()%(r - l + 1) + l;
 
	exchange(l,pos);
 
	int i = l+1,j = r;
 
	while(i <= j)
	{
		while(data[i] <= data[l] && i <= r)
			i++;
		while(data[j] >= data[l] && j >= l+1)
			j--;
		if(i < j)
			exchange(i,j); 	
	}
	exchange(l,j);
 
	QuickSort(l,j-1);
	QuickSort(j+1,r);
}

5.堆排序

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

class Heap
{
	//1 for root
	//for each node i,2*i is its left child,2*i+1 is its right child
public:
 
	Heap(int n):m_MaxSize(n),m_NumOfData(0)
	{
		m_pData = new int[m_MaxSize + 1];
	};
 
	~Heap()
	{
		delete m_pData;   
	}
 
	void exchange(int i,int j)
	{
		int t = m_pData[i];
		m_pData[i] = m_pData[j];
		m_pData[j] = t; 	 
	}
 
	void insert(int NewData)
	{
		if(m_NumOfData >= m_MaxSize)
		{
			cout<<"full! can not insert!"<<endl;
			return;
		}
		m_pData[++m_NumOfData] = NewData;
		int cur = m_NumOfData;
 
		while(cur > 0 && m_pData[cur] < m_pData[(int)(cur/2)])
		{
			exchange(cur,(int)(cur/2));
			cur = (int)(cur/2); 				   
		}
	}
 
	int deleteNode()
	{
		int cur = 1;
		int result = m_pData[cur];
		m_pData[cur] = m_pData[m_MaxSize--];
		while(cur <= m_MaxSize)
		{
 
			if(cur*2 > m_MaxSize)
				break;
			else if(cur*2+1 > m_MaxSize)
			{
				if(m_pData[cur] > m_pData[2*cur])
					exchange(cur,2*cur);
				break;
			}
			else if(m_pData[cur] < m_pData[cur*2] && m_pData[cur] < m_pData[cur*2+1])
				break;
			else if(m_pData[2*cur] > m_pData[2*cur+1])
			{
				exchange(cur,2*cur+1);
				cur = 2*cur+1;
			}
			else
			{
				exchange(cur,2*cur);	  
				cur = 2*cur;
			}
		}
		return result;
	}
 
	void Print()
	{
		cout<<"Print:"<<endl; 
		for(int i = 1;i <= m_MaxSize;i++)
			cout<<m_pData[i]<<"\t"; 
		cout<<endl;	 
	}
 
 
private:
	int* m_pData;	
	int m_NumOfData;     
	int m_MaxSize;
};
 
void HeapSort()
{
	Heap h(N);
	for(int i = 0;i < N;i++)
	{
		h.insert(data[i]);	
	}
 
	for(int i = 0;i < N;i++)
	{
		data[i] = h.deleteNode();	
	}
}

6.归并排序

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
49
50
51
52

void MergeSort(int l,int r)
{
	int length = r - l + 1;
 
	// when length <= 20,use InsertionSort instead.
	if(length <= 20)
	{
		InsertionSort(l,r);
		return; 		   
	} 
 
	/*
	if(length <= 1)
	return;
	*/
	else
	{
		MergeSort(l,l+length/2-1);
		MergeSort(l+length/2,r);
	}
	int* tempBuf = new int[r-l+1];
 
	int pos_1 = l,pos_2 = l+length/2;
	int i;
 
	for(i = 0;i < length && pos_1 <= l+length/2-1 && pos_2 <= r;i++)
	{
		if(data[pos_1] < data[pos_2])
		{
			tempBuf[i] = data[pos_1++];		
		}	 
		else
		{
			tempBuf[i] = data[pos_2++];
		}
	}  
 
	while(pos_1 <= l+length/2-1)
	{
		tempBuf[i++] = data[pos_1++];		 
	}
	while(pos_2 <= r)
	{
		tempBuf[i++] = data[pos_2++];		 
	}
 
	for(int i = l;i <= r;i++)
	{
		data[i] = tempBuf[i-l]; 		 
	}
	delete tempBuf;
}

7.计数排序

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

void CountingSort()
{
	int* b = new int[N];
	int* c = new int[MAX+1];
 
	for(int i = 0;i <= MAX;i++)
		c[i] = 0;	
 
	for(int i = 0;i < N;i++)
		c[data[i]]++;	 
 
	for(int i = 1;i <= MAX;i++)
		c[i] += c[i-1];	
 
	for(int i = N-1;i >= 0;i--)
	{
		b[c[data[i]]-1] = data[i];
		c[data[i]]--; 		
	}
 
	for(int i = 0;i < N;i++)
		data[i] = b[i];
 
	delete b;
	delete c;
}

8.桶排序

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

void CountingSort()
{
	int* b = new int[N];
	int* c = new int[MAX+1];
 
	for(int i = 0;i <= MAX;i++)
		c[i] = 0;	
 
	for(int i = 0;i < N;i++)
		c[data[i]]++;	 
 
	for(int i = 1;i <= MAX;i++)
		c[i] += c[i-1];	
 
	for(int i = N-1;i >= 0;i--)
	{
		b[c[data[i]]-1] = data[i];
		c[data[i]]--; 		
	}
 
	for(int i = 0;i < N;i++)
		data[i] = b[i];
 
	delete b;
	delete c;
}

9.基数排序

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
49
50
51
52

int digit(int data,int i)	//return the ith digit of data,from right to left is 0,1,2...
{
	while(i>0)
	{
		data /= 10;	   
		i--;
	}
 
	return data % 10;
}
 
void RadixSort()
{
	int digits = 0;
 
	int max = MAX;
 
	while(max != 1)
	{
		max /= 10;	  
		digits++; 		  
	} 
 
	int** pData = new int*[10];
	int len[10];
 
	for(int i = 0;i < 10;i++)
	{
		pData[i] = new int[N];
		//len[i] = 0;
	}    
 
	for(int i = 0;i < digits;i++)
	{
		for(int j = 0;j < 10;j++)
			len[j] = 0;
		for(int j = 0;j < N;j++)
		{
			pData[digit(data[j],i)][len[digit(data[j],i)]++] = data[j];	
		} 	
		//system("PAUSE");
		int pos = 0;
 
		for(int j = 0;j < 10;j++)
		{
			for(int k = 0;k < len[j];k++)
			{
				data[pos++] = pData[j][k];	
			} 	
		}
	}
}
测试代码 
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
49
50
51
52
53
54
55
56
57
58
59

int main(int argc, char *argv[])
{
	LARGE_INTEGER BegainTime; 
	LARGE_INTEGER EndTime; 
	LARGE_INTEGER Frequency;
	int TotalTime = 0;
 
	//sort M groups of data and calculate the average run time
	for(int i = 1;i <= M;i++)
	{
 
		genData(i);	
		//check();
 
		QueryPerformanceFrequency(&Frequency);
		QueryPerformanceCounter(&BegainTime);
 
		//BubbleSort();
		//InsertionSort();
		//SelectionSort();
		//QuickSort(0,N-1);
		//HeapSort();
		//MergeSort(0,N-1);
		//CountingSort();
		//BucketSort();
		RadixSort();
 
		QueryPerformanceCounter(&EndTime);
		//cout<<"run time : "<<(EndTime.QuadPart - BegainTime.QuadPart)*1000/Frequency.QuadPart<<" MS."<<endl;
		TotalTime += (int)((EndTime.QuadPart - BegainTime.QuadPart)*1000/Frequency.QuadPart);
		//check();
	}
 
	cout<<"Average run time : "<<TotalTime/M<<" MS."<<endl;
 
 
	//sort only one group of data
	/*
	genData();
	check();
	QueryPerformanceFrequency(&Frequency);
	QueryPerformanceCounter(&BegainTime);
	BubbleSort();
	//InsertionSort();
	//SelectionSort();
	QuickSort(0,N-1);
	//HeapSort();
	//MergeSort(0,N-1);
	//CountingSort();
	//BucketSort();
	//RadixSort();
	QueryPerformanceCounter(&EndTime) ;
	cout<<"run time : "<<( EndTime.QuadPart - BegainTime.QuadPart )*1000 / Frequency.QuadPart<<"MS."<<endl;
 
	check();
	*/
	system("PAUSE");
	return EXIT_SUCCESS;
}
测试数据如下，短时间的测50次，超过十秒的都测10次，没耐心。。 
函数名		|10^5	|10^6	|10^7		|
		|	|	|		|
   BubbleSort	|17751	|	|		|
InsertionSort 	|11037	|	|		|
SelectionSort	|14616	|	|		|
    QuickSort	|   19	|297	|      7808	|
     HeapSort	|   54	|981	|     15307	|
    MergeSort	|   30	|397	|      4211	|
   BucketSort	|   28	|427	|       645	|
 CountingSort	|    3	| 69	|out of mem	|
    RadixSort	|   28	|313	|out of mem	|

3 Responses to “【算法课作业】那些排序算法”

  1. dutor Says:
    十月 18th, 2010 at 12:43 上午

    接口好混乱啊。
    我也都写了，而且对这些算法的效率都测试了。
    另外，请教大牛选择排序是不是稳定的呢？
    另外，好像没有ShellSort，那个东西真的很神奇。
    另外，代码缩进是怎么回事？
    最后，你好啊！

  2. dutor Says:
    十月 18th, 2010 at 12:43 上午

    还有，不错不错，加油啊！

  3. chris Says:
    十月 19th, 2010 at 3:03 下午

    u r right on the “interface”topic
    我觉得应该把所有排序函数的接口都统一成void func(int* data,int l,int r)
    缩进应该是DEV C++的原因
    最后，看看我的测试数据，有点奇怪的是，最大数据量下归并比快排表现要好。

Leave a Reply