数据结构排序算法---八大排序复杂度及代码实现

---

稳定性：相同的数据排序后，相对位置是否发生改变

一、冒泡排序

时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：稳定

代码实现

void Swap(int* a, int* b)
{
	int tmp;
	tmp = *a;
	*a = *b;
	*b = tmp;
}
void BubbleSort(int* a, int n)
{
	for (int j = 0; j < n; j++)
	{
		int exchange = 0;
		for (size_t i = 1; i < n-j; i++)
			if (a[i - 1] > a[i])
			{
				Swap(&a[i - 1], &a[i]);
				exchange = 1;
			}
		if (exchange == 0)
		{
			break;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

---

二、直接插入排序

时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：稳定

代码实现

void InsertSort(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end>=0)
		{
			if (tmp < a[end])
				a[end + 1] = a[end];
			else
				break;
			--end;
		}
		a[end + 1] = tmp;
	} 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

---

三、希尔排序

时间复杂度：O(N^1.3)
空间复杂度：O(1)
稳定性：不稳定

代码实现

void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
					break;
			}
			a[end + gap] = tmp;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

---

四、选择排序

时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：不稳定

代码实现

void SelectSort(int* a, int n)
{
	int begin = 0;
	int end = n - 1;
	while (begin < end)
	{
		int max = begin, min = begin;
		for (int i = begin+1; i <= end; i++)
		{
			if (a[i] > a[max])
				max = i;
			if (a[i] < a[min])
				min = i;
		}
		Swap(&a[begin], &a[min]);
		if (max == begin)
			max = min;
		Swap(&a[end], &a[max]);
		--end;
		++begin;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

---

五、堆排序

时间复杂度：O(N*logN)
空间复杂度：O(1)
稳定性：不稳定

代码实现

void AdjustDown(int* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child + 1] > a[child])
		{
			++child;
		}

		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapSort(int* a, int n)
{
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}
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

---

六、快速排序

时间复杂度：O(N*logN)
空间复杂度：O(logN)
稳定性：不稳定

代码实现

//三数取中
int GetMidi(int* a, int left, int right)
{
	int midi = (left + right) / 2;
	if (a[left] < a[midi])
	{
		if (a[midi] < a[right])
			return midi;
		else if (a[right] < a[left])
			return left;
		else
			return right;
	}
	else
	{
		if (a[left] < a[right])
			return left;
		else if (a[right] < a[midi])
			return midi;
		else
			return right;
	}
}
//hoare
int PartSort1(int* a, int left,int right)
{
	int keyP = left;//GetMidi(a,left,right);
	while (left < right)
	{
		while (a[right] >= a[keyP] && left < right)
			--right;
		while (a[left] <= a[keyP] && left < right)
			++left;
		Swap(&a[left], &a[right]);
	}
	Swap(&a[keyP], &a[left]);
	return left;
}
//挖坑法
int PartSort2(int* a, int left, int right)
{
	int midi = GetMidi(a, left, right);
	Swap(&a[left], &a[midi]);
	int keyP = a[left];
	//int keyP = left;
	int hole = left;
	while (left < right)
	{
		while (a[right] >= keyP && left < right)
			--right;
		a[hole] = a[right];
		hole = right;
		while (a[left] <= keyP && left < right)
			++left;
		a[hole] = a[left];
		hole = left;
	}
	a[hole] = keyP;
	return hole;
}
//前后指针
int PartSort3(int* a, int left, int right)
{
	int prev = left;
	int cur = prev + 1;
	int keyP = left;
	while (cur <= right)
	{
		if (a[cur] < a[keyP] && ++prev != cur)
		{
			Swap(&a[prev], &a[cur]);
		}
		cur++;
	}
	Swap(&a[prev], &a[keyP]);
	return prev;
}

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;
	int key = PartSort1(a, begin, end);
	QuickSort(a, begin, key - 1);
	QuickSort(a, key + 1, end);
}

void QuickSort1(int* a, int begin, int end)
{
	if (begin >= end)
		return;
	//小区间优化,小区间不在递归分割排序，降低递归次数
	if ((end - begin + 1) > 10)
	{
		int key = PartSort1(a, begin, end);
		QuickSort1(a, begin, key - 1);
		QuickSort1(a, key + 1, end);
	}
	else
	{
		InsertSort(a + begin, end - begin + 1);
	}
}

void QuickSortNonR(int* a, int begin, int end)//非递归
{
	Stack st;
	StackInit(&st);
	StackPush(&st, end);
	StackPush(&st, begin);
	while (!StackEmpty(&st))
	{
		int left = StackTop(&st);
		StackPop(&st);
		int right = StackTop(&st);
		StackPop(&st);
		int key = PartSort3(a, left, right);
		if (key + 1 < right)
		{
			StackPush(&st, right);
			StackPush(&st, key + 1);
		}
		if (begin < key - 1)
		{
			StackPush(&st, key - 1);
			StackPush(&st, begin);
		}
	}
	StackDestory(&st);
}
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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130

其中包含了，三数取中（基准值），快排的三种实现方法（hoare，挖坑法，前后指针）及非递归方法

---

七、归并排序

时间复杂度：O(N*logN)
空间复杂度：O(N)
稳定性：稳定

代码实现

void PartMergeSort(int* a, int* tmp, int begin, int end)
{
	if (end <= begin)
		return;
	int mid = (begin + end) / 2;
	PartMergeSort(a, tmp, begin, mid);
	PartMergeSort(a, tmp, mid + 1, end);
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int count = begin;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
			tmp[count++] = a[begin1++];
		else
			tmp[count++] = a[begin2++];
	}
	while (begin1 <= end1)
	{
		tmp[count++] = a[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[count++] = a[begin2++];
	}
	memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}

void MergeSort(int* a, int n)
{
	int* tmp = malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	PartMergeSort(a, tmp, 0, n - 1);
	free(tmp);
}

void MergeSortNonR(int* a, int n)
{
	int* tmp = malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	int gap = 1;
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2 * gap)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
			int count = i;
			if (begin2 >= n)
				break;
			if (end2 >= n)
				end2 = n - 1;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
					tmp[count++] = a[begin1++];
				else
					tmp[count++] = a[begin2++];
			}
			while (begin1 <= end1)
			{
				tmp[count++] = a[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[count++] = a[begin2++];
			}
			memcpy(a + i, tmp + i, (end2-i+1) * sizeof(int));
		}	
		gap *= 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
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

其中包含了递归及非递归实现方法

---

八、计数排序

时间复杂度：O(N+range)
空间复杂度：O(range)

代码实现

void CountSort(int* a, int n)
{
	int min = a[0], max = a[0];
	for (size_t i = 0; i < n; i++)
	{
		if (a[i] < min)
			min = a[i];

		if (a[i] > max)
			max = a[i];
	}

	int range = max - min + 1;
	int* count = (int*)malloc(sizeof(int) * range);
	printf("\nrange:%d\n", range);
	if (count == NULL)
	{
		perror("malloc fail");
		return;
	}
	memset(count, 0, sizeof(int) * range);

	// 统计数据出现次数
	for (int i = 0; i < n; i++)
	{
		count[a[i] - min]++;
	}

	// 排序
	int j = 0;
	for (int i = 0; i < range; i++)
	{
		while (count[i]--)
		{
			a[j++] = i + min;
		}
	}
}
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