简介:使用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); } }