六大排序实现

插入排序

算法思路

直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一

个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。

就像斗地主，我们需要对拿到的牌去进行一个排列，

动图演示

代码实现

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

希尔排序

算法思路

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个

组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工

作。当到达=1时，所有记录在统一组内排好序。

动图演示

代码实现

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

选择排序

算法思路

在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素

若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换

在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素

动图演示

代码实现

void electsort1()
	{
		int min_idx = 0;
		for (int i = 0; i < _size-1; i++)
		{
			int min = _a[i];
			min_idx = i;
			for (int j = i + 1; j < _size; j++)
			{
				if (_a[j] < min)
				{
					min = _a[j];
					min_idx = j;
				}
			}
			swap(_a[i], _a[min_idx]);
		}
	}
void electsort2()//同时从两边去找最大最小值一次性找出最大和最的值
	{
		int begin = 0;
		int end = _size - 1;
		while (begin < end)
		{
			int max_idx = begin;
			int min_idx = begin;
			for (int i = begin; i <= end; i++)
			{
				if (_a[i] < _a[min_idx])
					min_idx = i;
				if (_a[i] > _a[max_idx])
					max_idx = i;
			}
			swap(_a[begin], _a[min_idx]);
			max_idx = max_idx == begin ? min_idx : max_idx;
			swap(_a[end], _a[max_idx]);
			begin++;
			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
38
39
40

堆排序

算法思路

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是

通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

动图演示

代码实现

//建堆
	void adjustup(int root)//向上调整建堆
	{
		int parent = (root - 1) / 2;
		while (root > 0)
		{
			if (_a[parent] > _a[root])
			{
				swap(_a[parent], _a[root]);
				root = parent;
				parent = (root - 1) / 2;
			}
			else
				break;
		}
	}
	void adjustdown(int n, int child)//向下调整重建堆
	{
		int parent = child;
		child = parent * 2 + 1;
		while (child < n)
		{
			if (_a[child] > _a[child + 1] && child + 1 < n)
			{
				child++;
			}
			if (_a[parent] > _a[child])
			{
				swap(_a[parent], _a[child]);
				parent = child;
				child = parent * 2 + 1;
			}
			else
				break;
		}
	}
	//堆排
	void heapsort()
	{
		for (int i = _size-1 ; i >= 0; i--)
		{
			adjustup(i);
		}
		int end = _size - 1;
		while (end > 0)
		{
			swap(_a[0], _a[end]);
			adjustdown(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
38
39
40
41
42
43
44
45
46
47
48
49
50
51

冒泡排序

算法思路

就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排

序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

动图演示

代码实现

void bubblesort()
	{
		int end = _size;
		while (end)
		{
			int flag = 1;
			for (int i = 1; i < end; i++)
			{
				if (_a[i] < _a[i - 1])
				{
					swap(_a[i], _a[i - 1]);
					flag = 0;
				}
			}
			if (flag)
				break;
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

快速排序

算法思路

任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

动图演示

代码实现

//快排左右指针法
	void qsort(int begin,int end)
	{
		if (begin >= end)
			return;
		int key = _a[begin];
		int key_idx = begin;
		int right = end;
		int left = begin;
		while (begin < end)
		{
			while (_a[end] >= key&& begin < end)
			{
				end--;
			}
			while (_a[begin] <= key&& begin < end)
			{
				begin++;
			}
			swap(_a[begin], _a[end]);
		}
		swap(_a[begin], _a[key_idx]);
		qsort(left, end - 1);
		qsort(end+1,right);	
	}
//挖坑法
//递归版本
	void qsort1(int begin, int end)
	{
		if (begin >= end)
			return;
		int hole = _a[begin];
		int hole_idx = begin;
		int right = end;
		int left = begin;
		while (begin < end)
		{
			while (_a[end] >= hole && begin < end)
			{
				end--;
			}
			swap(_a[begin], _a[end]);
			while (_a[begin] <= hole && begin < end)
			{
				begin++;
			}
			swap(_a[begin], _a[end]);
		}
		swap(_a[end], hole);
		qsort(left, end - 1);
		qsort(end + 1, right);
	}
//非递归版本
int qsortfirst(int begin, int end)
	{
		int key = _a[begin];
		int key_idx = begin;
		int right = end;
		int left = begin;
		while (begin < end)
		{
			while (_a[end] >= key && begin < end)
			{
				end--;
			}
			while (_a[begin] <= key && begin < end)
			{
				begin++;
			}
			swap(_a[begin], _a[end]);
		}
		swap(_a[begin], _a[key_idx]);
		return end;
	}
	void qsortNorl(int begin, int end)
	{
		stack s;
		s.push(end);
		s.push(begin);
		while (!s.empty())
		{
			int left = s.top();
			s.pop();
			int right = s.top();
			s.pop();
			int mid = qsortfirst(left, right);
			if (mid - 1 > left)
			{
				s.push(mid - 1);
				s.push(left);
			}
			if (mid + 1 < right)
			{
				s.push(right);
				s.push(mid + 1);
			}
		}
	}
//前后指针法
	void qsort3(int begin, int end)
	{
		int key = _a[begin];
		int cur = begin + 1;
		int prev = begin;
		while (cur <= end)
		{
			if(_a[cur] < key && prev++ != cur)
			{
				swap(_a[cur], _a[prev]);
			}
			++cur;
		}
		swap(_a[prev], _a[begin]);
		qsort(begin, prev - 1);
		qsort(prev + 1, 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
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

.push(right);
s.push(mid + 1);
}
}
}
//前后指针法
void qsort3(int begin, int end)
{
int key = _a[begin];
int cur = begin + 1;
int prev = begin;
while (cur <= end)
{
if(_a[cur] < key && prev++ != cur)
{
swap(_a[cur], _a[prev]);
}
++cur;
}
swap(_a[prev], _a[begin]);
qsort(begin, prev - 1);
qsort(prev + 1, end);
}

  
1
2