济宁市松岳建设机械有限公司网站,销售易,长春一大网站,wordpress创建页面路由访问www.tomcoding.com网站#xff0c;学习Oracle内部数据结构#xff0c;详细文档说明#xff0c;下载Oracle的exp/imp#xff0c;DUL#xff0c;logminer#xff0c;ASM工具的源代码#xff0c;学习高技术含量的内容。
冒泡排序
这个算法可以说是排序算法中最著名的…访问www.tomcoding.com网站学习Oracle内部数据结构详细文档说明下载Oracle的exp/impDULlogminerASM工具的源代码学习高技术含量的内容。
冒泡排序
这个算法可以说是排序算法中最著名的一个了名字独特也好理解在一个数组中有n个元素扫描整个数组中没有排序的元素从第一个元素开始每个元素与它后面的元素比较数值小的放在前面数值大的放在后面那么经过第一轮扫描最大的数值就放在了数组最后的位置就像每个元素是一个气泡最大的气泡最先浮到数组顶端。第二轮扫描由于最大的元素已经找到需要找第二大的元素这时扫描的元素个数少了一个变为n-1经过第二轮扫描第二大的元素放到了数组倒数第二的位置。依次类推第三次扫描元素个数变为n-2第三大的元素排到了倒数第三的位置。这样每次扫描的元素越来越少最后扫描到未排序的元素只有一个时排序就结束了这时数组中的数值按照升序排列好了。
第0轮扫描n-1个元素从0开始到n-2每个元素j与后一个元素j1比较小的在前大的在后如果不一致时要把这两个元素交换位置。
第1轮扫描n-2个元素从0开始到n-3每个元素j与后一个元素j1比较。
第2轮扫描n-3个元素从0开始到n-4每个元素j与后一个元素j1比较。
第3轮扫描n-4个元素从0开始到n-5每个元素j与后一个元素j1比较。
……
第n-2轮扫描1个元素第0个和第1个元素比较。
第n-1轮扫描0个元素结束。其实在上一轮比较完就可以结束了。
用C语言编写一个函数实现冒泡排序算法i表示扫描的轮的序号j表示每一轮中扫描的元素序号数组下标。
/* ai是要排序的整数数组指针 * n是数组中元素的个数 */
void bubble_sort(int *ai, int n)
{ int i, j, k; /* 循环n-1轮 */ for (i 0; i (n-1); i) { /* 每一轮扫描n-1-i个元素 */ for (j 0; j (n-1-i); j) { if (ai[j] ai[j1]) { /* 前一个元素比后一个大交换位置否则不用交换 */ k ai[j]; ai[j] ai[j1]; ai[j1] k; } } }
}
选择排序
这个也是经常用到的排序算法甚至是最容易想到的算法虽然不好确定它的名字。工作原理如下把要排序的数组分成两部分第一部分是排过序的元素集合第二部分是没有排过序的元素集合开始时第一部分的元素个数为0第二部分为全部元素算法要进行多轮选择每一轮选择都是从第二部分元素中找到最小的元素把这个元素放到第一部分的末尾这样经过多轮选择后第一部分越来越大第二部分越来越小当第二部分元素数为0时排序就结束了。
实现算法时也有两个关键点要确定第一个是循环的轮数假设数组中元素的个数是n每一轮要找到一个最小数据所以原则上应该找n轮其实找到n-1轮时最后一轮就剩下一个元素了没有比较的必要了所以循环的轮数为n-1。第二个是每轮查找元素的个数看下表。
第0轮扫描n-0个元素从0到n-1
第1轮扫描n-1个元素从1到n-1
第2轮扫描n-2个元素从2到n-1
第3轮扫描n-3个元素从3到n-1
……
第n-2轮扫描2个元素从n-2到n-1
第n-1轮扫描1个元素从n-1到n-1 用C语言写一个函数实现这个算法。
/* ai 是要排序的整数数组 * n 是数组中元素的个数 * * 函数中ij是计数变量 * min_index是第二部分数组中最小值的元素下标 * min变量暂存第二部分中最小值 * tail是第一部分的尾部位置 * start是第二部分开始扫描的起始位置 */
static void selection_sort(int *ai, int n)
{ int i, j, k, min_index; int min; int tail; int start; /* 开始时第一部分没有元素尾部在第0个元素 */ tail 0; for (i 0; i (n-1); i) { start tail; min ai[start]; min_index -1; for (j start; j n; j) { if (ai[j] min) { min_index j; min ai[j]; } } if (min_index ! -1) { /* 找到了最小值交换元素 */ k ai[tail]; ai[tail] ai[min_index]; ai[min_index] k; } tail; }
}
这个函数看起来有些复杂我们来简化一下。从上面看tail其实就是i的位置start是i的下一个位置min值是扫描第二部分的第一个元素把这些简化后得到下面的函数。
void selection_sort(int *ai, int n)
{ int i, j, k; int min_index; for (i 0; i (n-1); i) { min_index i; for (j i1; j n; j) { if (ai[j] ai[min_index]) min_index j; } if (min_index ! i) { /* 交换元素 */ k ai[i]; ai[i] ai[min_index]; ai[min_index] k; } }
} 检查排序结果
写一个函数来检查一下排序后的元素顺序有没有错误方法很简单在数组中遍历一次看看前一个元素是否比后一个元素大如果大就说明排序出错了。
void check_result(int *ai, int n)
{ int i; for (i0; in-1; i) { if (ai[i] ai[i1]) { fprintf(stderr, error, element[%d]%d, element[%d]%d\n\n, i, ai[i], i1, ai[i1]); return; } } fprintf(stdout, element is sorted.\n\n);
} 写一个程序测试一下排序结果。
int main(int argc, char *argv[])
{ static int chaos[16] {23, 6, 235, 89, 4, 12, 76, 35, 129, 30, 77, 15, 61, 44, 49, 88}; int array[16]; fprintf(stdout, test for bubble_sort function.\n\n); memcpy(array, chaos, 16*sizeof(int)); bubble_sort(array, 16); check_result(array, 16); fprintf(stdout, test for selection_sort function.\n\n); memcpy(array, chaos, 16*sizeof(int)); selection_sort(array, 16); check_result(array, 16); return (0);
}
