数据结构：交换排序

简介：使用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.c：算法的代码实现

#include "Sort.h"



void Swap(int *data1, int *data2)
{
	int temp = *data1;

	*data1 = *data2;

	*data2 = temp;
}


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;
	}
}


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;
	}
}


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;
}


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);
	}
}