排序算法(一）

冒泡排序

冒泡排序是一种十分稳定的排序，其思想是通过两两比较，改变位置，从而每次让一个数出现在其该出现的位置该很稳定，同时，不论数据是否有序，时间复杂度都是O(N^2)

void BubbleSort(int* arr, int n)
{
		for (size_t 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

选择排序

选择排序是通过两两比较，遍历数组，找到最大值下标和最小值下标，将这两个下标的值交换到最合适的位置，选择排序时间复杂度O(N^2)，是一种不稳定的算法。

void SelectSort(int* arr, int n)
{
	int begin = 0, end = n - 1;
	while(begin < end)
	{
		int mini = begin, maxi = begin;
		for (int i = begin+1; i <= end; i++)
		{
			if (arr[i] < arr[mini])
			{
				mini = i;
			}
			if (arr[i] > arr[maxi])
			{
				maxi = i;
			}
		}
		Swap(&begin, arr[mini]);
		// - 防止交换后，maxi所指向的是最小值
		if (begin == maxi)
			maxi = mini;
		Swap(&end, arr[maxi]);

		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

插入排序

插入排序是一种稳定的排序算法，其算法思想是通过元素之间的比较，将该元素插入到合适的位置，插入排序的时间复杂度是一般是O(N^2)，如果数据基本有序，则时间复杂度将为O(N)。

void InsertSort(int* arr, int n)
{
	for (int i = 0; i < n-1; i++)
	{
		int end = i;
		int tmp = arr[end + 1];
		while (end >= 0)
		{
			if (tmp < arr[end])
			{
				arr[end + 1] = arr[end];
			}
			else
			{
				break;
			}
			end--;

		}
		arr[end + 1] = tmp;
	}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

希尔排序

希尔排序，又叫增量缩小排序，其排序思想是插入排序，不过在直接插入排序前，先通过多次预排序，让数据更加的有序，让最后一次排序的时间复杂度减小，希尔排序的时间复杂度是O(N^1.3-1.6)，希尔排序不是一种稳定的排序算法，数据越有序，时间复杂度越小。

void ShellSort(int* arr, 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 = arr[end + gap];
			while (end >= 0)
			{
				if (tmp < arr[end])
				{
					arr[end + gap] = arr[end];
				}
				else
				{
					break;
				}
				end -= gap;
			}
			arr[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
25
26

当gap = 1时，希尔排序就是插入排序。

堆排序

堆排序需要先建堆，排升序建大堆，降序建小堆，向下调整建堆的时间复杂度是O(N)，向上调整建堆的时间复杂度是O(NlogN)，每次交换堆顶和堆低的元素，并且把最后一个元素弹出堆中，不断重复，其不是一种稳定的排序。

void AdjustDown(DataType* arr, int n, int parent)
{
	assert(arr);
	int minChild = parent * 2 + 1;
	while (minChild < n)
	{
		if (minChild + 1 < n - 1 && arr[minChild] > arr[minChild + 1])
		{
			minChild++;
		}
		if (arr[minChild] < arr[parent])
		{
			Swap(&arr[minChild], &arr[parent]);
			parent = minChild;
			minChild = parent * 2 + 1;
		}
		else
		{
			// - 子树是堆，当判断部分满足堆时，其他部分一定是堆
			break;
		}
	}
	return;


}
void HeapSort(DataType* arr, int n)
{
	// - 升序建大堆，降序建小堆
	// - 向下调整建堆
	for (int i = (n-1-1)/2; i >= 0; i--)
	{
		AdjustDown(arr, n, i);
	}

	while (n--)
	{
		Swap(&arr[0], &arr[n]);
		AdjustDown(arr, n, 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