《数据结构》直接插入、简单选择、冒泡和快速排序
- 格式：docx
- 大小：55.69 KB
- 文档页数：9
/******************************************************************************* /*
/****************************************************************************** /* 数据类型和常量定义 /******************************************************************************/ #define LQ(a, b) ((a) <= (b))
/****************************************************************************** /* 函数原型声明 /******************************************************************************/ void InsertSort(int x[], int n); //直接插入排序 void BubbleSort(int x[], int n); //冒泡排序 void QuickSort(int x[], int low, int high); //快速排序 void SelectSort(int x[], int n); //简单选择排序
/******************************************************************************* /* /* 函数名 : InsertSort /* 功能 : 直接插入排序 /* 参数 : int x[], 待排序列 /* int n, 序列中元素个数 /* 返回值 : - /* 备注 : - /* 作者 : /* *******************************************************************************/ void InsertSort(int x[], int n) { int sentinel = 0; /* sentinel: 哨兵 */ int i, j, k; for(i = 1; i < n; i++) /* 序列中的第一个元素可以看成一个有序表 */ { if(LQ(x[i], x[i - 1])) { sentinel=x[i]; /* 复制为哨兵 */ for(j = i - 1; j >= 0 && LQ(sentinel, x[j]); --j) x[j + 1] = x[j]; /* 记录后移 */ x[j + 1] = sentinel; /* 插入到正确位置 */ } printf("第 %d 趟排序后的结果: ", i); /*输出每一趟排序的结果*/ for(k = 0; k < n; k++) printf("%d ", x[k]); printf("\n"); } }
/******************************************************************************* /* /* 函数名 : BubbleSort /* 功能 : 冒泡排序 /* 参数 : int x[], 待排序列 /* int n, 序列中元素个数 /* 返回值 : - /* 备注 : 一种交换排序 /* 作者 : /* *******************************************************************************/ void BubbleSort(int x[], int n) { int temp, exchange; int i, j, k; for(i=n-1; i>0; i--) //最多做n-1趟排序 { exchange=0; //本趟排序开始前, 交换标志应为假 for(j=0; j { if(LQ(x[j+1], x[j])) { temp=x[j+1]; x[j+1]=x[j]; x[j]=temp; exchange=1; } } if(!exchange) //本趟排序未发生交换，提前终止算法 break; printf("第 %d 趟排序后的结果: ", n-i); /*输出每一趟排序的结果*/ for(k=0; k printf("%d ", x[k]); printf("\n"); } }
/******************************************************************************* /* /* 函数名 : QuickSort /* 功能 : 快速排序 /* 参数 : - /* 返回值 : - /* 备注 : 一种交换排序 /* 作者 : /* *******************************************************************************/ int Partition(int x[], int low, int high) { int sentinel = x[low]; int pivotkey = x[low]; while(low < high) { while(low x[low] = x[high]; while(low x[high] = x[low]; } x[low]=sentinel; return low; }
void QuickSort(int x[], int low, int high) { int pivotloc, k; if(low < high) { pivotloc=Partition(x, low, high); printf("排序过程: "); /*输出每一趟排序的结果*/ for(k=0; k<8; k++) printf("%d ", x[k]); printf("\n"); QuickSort(x, low, pivotloc-1); QuickSort(x, pivotloc+1, high); } }
/******************************************************************************* /* /* 函数名 : SelectSort /* 功能 : 简单选择排序 /* 参数 : - /* 返回值 : - /* 备注 : 一种选择排序 /* 作者 : /* *******************************************************************************/ int SelectMinKey(int x[], int low, int high) { int temp = x[low], pos=low; while(low <= high) { if(LQ(x[low], temp)) { temp = x[low]; pos = low; } low++; } return pos; }
