八大排序算法C++实现

发表于   |   分类于   |  

八大排序算法C++实现

1、选择排序

思路：从第一个元素开始，找出之后的元素比它小的进行替换。
时间复杂度：$O(N^2)$
空间复杂度：$O(1)$
不稳定

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void select_sort(int *data, int len)
{
	for (int i = 0; i < len; ++i)
	{
		int min_idx = i;
		int min_val = data[i];
		for (int j = i + 1; j < len; ++j)
		{
			if (data[j] < min_val)
			{
				min_idx = j;
				min_val = data[j];
			}
		}
		if (min_idx != i)
			swap(data[i], data[min_idx]);
	}
}

2、插入排序

思路：假设前i个元素已经排好序，将i+1个元素插入到合适的位置。
时间复杂度：$O(N^2)$
空间复杂度：$O(1)$
稳定

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void insert_sort(int *data, int len)
{
	for (int i = 1; i < len; ++i)
	{
		int pos = i;
		for (int j = 0; j < i; ++j)
		{
			if (data[i] < data[j])
			{
				pos = j;
				break;
			}
		}
		if (pos != i)
		{
			int temp = data[i];
			for (int j = i; j>pos; --j)
			{
				data[j] = data[j - 1];
			}
			data[pos] = temp;
		}
	}
}

3、冒泡排序

思路：每一轮通过相邻元素交换将最小元素移到开头，开头已经冒泡完成的元素不再移动。
时间复杂度：$O(N^2)$
空间复杂度：$O(1)$
稳定

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void bubble_sort(int *data, int len)
{
	for (int i = 0; i < len-1; ++i)
	{
		bool changed = false;
		for (int j = len-1; j > i; --j)
		{
			if (data[j-1]>data[j])
			{
				changed = true;
				swap(data[j-1], data[j]);
			}
		}
		if (!changed)
			break;
	}
}

快速排序

思路：选择中间的数作为基准，比它小的移到左边，比它大的移到右边，对左右两部分进行递归。
时间复杂度：$O(NlogN)$
空间复杂度：$O(logN)$
不稳定

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 quick_sort(int *data, int left, int right)
{
	if (left >= right)
		return;
	int mid = left + (right - left) / 2;
	swap(data[mid], data[right]);
	int small_idx = left;
	for (int i = left; i < right; ++i)
	{
		if (data[i] < data[right])
		{
			swap(data[i], data[small_idx]);
			++small_idx;
		}
	}
	swap(data[small_idx], data[right]);
	quick_sort(data, left, mid - 1);
	quick_sort(data, mid + 1, right);
}
void quick_sort(int *data, int len)
{
	quick_sort(data, 0, len - 1);
}

5、归并排序

思路：将数组递归分成两部分，假设每部分都已排好序，进行组合。
时间复杂度：$O(NlogN)$
空间复杂度：$O(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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
void merge_sort(int *data, int start, int end, int *temp)
{
	if (start >= end)
		return;
	int mid = start + (end - start) / 2;
	merge_sort(data, start, mid, temp);
	merge_sort(data, mid + 1, end, temp);
	if (end == start + 1 && data[end] < data[start])
		swap(data[end], data[start]);
	else
	{
		int i = start;
		int j = mid + 1;
		int idx = 0;
		for (; i <= mid && j <= end; ++idx)
		{
			if (data[i] < data[j])
			{
				temp[idx] = data[i];
				++i;
			}
			else
			{
				temp[idx] = data[j];
				++j;
			}
		}
		for (; i <= mid; ++i, ++idx)
		{
			temp[idx] = data[i];
		}
		for (; j <= end; ++j, ++idx)
		{
			temp[idx] = data[j];
		}
		memcpy(data + start, temp, sizeof(int)*(end - start + 1));
	}
}
void merge_sort(int *data, int len)
{
	assert(data != NULL && len > 0);
	int *temp = new int[len];
	if (len == 1)
		return;
	merge_sort(data, 0, len - 1, temp);
}

6、希尔排序

思路：将数组分成若干个子序列，对各个子序列进行直接插入排序，缩小子序列的间隔执行上述步骤，最后变成一个子序列。
时间复杂度：$O(NlogN)$
空间复杂度：$O(1)$
不稳定

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
void shell_sort(int *data, int len)
{
	for (int k = len / 2; k > 0; k = k / 2)
	{
		for (int p = 0; p < k; ++p)
		{
			for (int i = p + k; i < len; i += k)
			{
				int pos = i;
				for (int j = p; j < i; j += k)
				{
					if (data[i] < data[j])
					{
						pos = j;
						break;
					}
				}
				if (pos != i)
				{
					int temp = data[i];
					for (int j = i; j>pos; j -= k)
					{
						data[j] = data[j - k];
					}
					data[pos] = temp;
				}
			}
		}
	}
}

7、堆排序

思路：先构建最大堆，每次将根节点与最后一个元素交换，并调整最大堆。
时间复杂度：$O(NlogN)$
空间复杂度：$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
31
32
33
34
35
36
37
38
void heap_adjust(int *data, int i,int len)
{
	int lchild = 2 * i;
	int rchild = 2 * i + 1; 
	int max = i; 
	if (i <= len / 2)
	{
		if (lchild <= len && data[lchild - 1]>data[max - 1])
		{
			max = lchild;
		}
		if (rchild <= len && data[rchild - 1]>data[max - 1])
		{
			max = rchild;
		}
		if (max != i)
		{
			swap(data[i - 1], data[max - 1]);
			heap_adjust(data, max, len);
		}
	}
}
void heap_sort(int *data, int len)
{		
	for (int i = len/2; i >=1; --i)
			heap_adjust(data,i,len);
	for (int k = len-1; k>=1; --k)
	{
	
		swap(data[0], data[k]);
		heap_adjust(data, 1, k);
	}
}

8、基数排序

思路：先按照元素的个位数字进行分组，重新组合，然后是十位，直到最高位。
时间复杂度：$O(d(n+rd))$
空间复杂度：$O(rd+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
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
int radix_maxbit(int *data, int n)
{
	int d = 1;
	for (int i = 0; i<n; i++)
	{
		int c = 1;
		int p = data[i];
		while (p / 10)
		{
			p = p / 10;
			c++;
		}
		if (c>d)
			d = c;
	}
	return d;
}
int radix_getbit(int num, int bit)
{
	int n = 0;
	for (int i = 0; i < bit; ++i)
	{
		if (num == 0)
			return 0;
		n = num % 10;
		num = num / 10;
	}
	return n;
}
void radix_sort(int *data, int n,int bit)
{
	int count[19];
	for (int i = 0; i < 19; ++i)
		count[i] = 0;
	for (int i = 0; i < n; ++i)
	{
		int b = radix_getbit(data[i], bit);
		++count[b+9];
	}
	for (int i = 0; i < 18; ++i)
	{
		count[i + 1] += count[i];
	}
	int * buff = new int[n];
	for (int i = 0; i < n; i++)
	{
		int b = radix_getbit(data[i], bit);
	    --count[b + 9];
		buff[count[b + 9]] = data[i];
	}
	for (int i = 0; i < n; i++)
	{
		data[i] = buff[i];
	}
	delete[] buff;
}
void radix_sort(int *data, int n)
{
	int max = radix_maxbit(data, n);
	for (int i = 1; i <= max;++i)
	    radix_sort(data,n,i);
}
坚持原创技术分享，您的支持将鼓励我继续创作！