数据结构：交换排序

简介：使用C语言实现交换排序，包括冒泡排序(“冒泡”和“下沉”)及快速排序。相关算法的原理，网上的资料已经讲的很仔细，在此就不一一赘述，相关资料可参阅《大话数据结构》。

排序头文件Sort.h：相关函数声明及数据类型定义

#ifndef SORT_H
#define SORT_H

#define ElemType int
#define BOOL ElemType
#define TRUE  ((ElemType) 1)
#define FALSE ((ElemType) 0)

void BubbleSortUp(ElemType A[], int n);
void BubbleSortDown(ElemType A[], int n);
void QuickSort(ElemType A[], int low, int high);

#endif /* SORT_H */
1
2
3
4
5
6
7
8
9
10
11
12
13

排序算法源文件Sort.c：算法的代码实现

#include "Sort.h"

/*---------------------------------------------------------------------------------
下列为交换排序
---------------------------------------------------------------------------------*/
/**********************************************************************************
* @brief  交换元素数值
* @param  data1：元素1
          data2：元素2
* @retval void
* @note   void
**********************************************************************************/
void Swap(int *data1, int *data2)
{
	int temp = *data1;

	*data1 = *data2;

	*data2 = temp;
}

/**********************************************************************************
* @brief  冒泡排序(“最小元素漂浮水面”)
* @param  A：待排序数据
          n：数据元素个数
* @retval void
* @note   void
**********************************************************************************/
void BubbleSortUp(ElemType A[], int n)
{
	int i, j, flag;

	for (i = 0; i < n-1; i++)
	{
		flag = FALSE; //表示本趟是否交换的的标志

		for (j = n - 1; j > i; j--) //从后往前依次比较并交换
		{
			if (A[j-1] > A[j]) //若为逆序，则交换
			{
				Swap(&A[j-1], &A[j]);

				flag = TRUE;
			}
		}

		if (flag == FALSE) //本趟遍历没有发生交换，该表已经有序
			return;
	}
}

/**********************************************************************************
* @brief  冒泡排序(“最大元素沉入水底”)
* @param  A：待排序数据
          n：数据元素个数
* @retval void
* @note   void
**********************************************************************************/
void BubbleSortDown(ElemType A[], int n)
{
	int i, j, flag;
	                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            
	for (i = 0; i < n-1; i++)
	{
		flag = FALSE; //表示本趟是否交换的的标志

		for (j = 0; j < n - 1 - i; j++) //从前往后依次比较并交换
		{
			if (A[j] > A[j + 1]) //若为逆序，则交换
			{
				Swap(&A[j], &A[j + 1]); 

				flag = TRUE;
			}
		}

		if (flag == FALSE) //本趟遍历没有发生交换，该表已经有序
			return;
	}
}

/**********************************************************************************
* @brief  根据枢轴将原序列一分为二
* @param  A   ：待分裂数据
          low ：最左端位置
		  high：最右端位置
* @retval 分裂位置
* @note   void
**********************************************************************************/
static int Partition(ElemType A[], int low, int high)
{
	ElemType pivot = A[low];

	while (low < high)
	{
		while (low < high && A[high] >= pivot) --high;

		A[low] = A[high];

		while (low < high && A[low] <= pivot) ++low;

		A[high] = A[low];
	}

	A[low] = pivot;

	return low;
}

/**********************************************************************************
* @brief  快速排序
* @param  A：待排序数据
          low ：待排序数据最左端起始位置
		  high：待排序数据最右端起始位置
* @retval void
* @note   low和high为数据所在数组的实际下标
**********************************************************************************/
void QuickSort(ElemType A[], int low, int high)
{
	int pivotpos;

	if (low < high)
	{
		pivotpos = Partition(A, low, high);

		QuickSort(A, low, pivotpos-1);

		QuickSort(A, pivotpos+1, high);
	}
}
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