首页 > 代码库 > Collection of algorithm for sorting. 常见排序算法集(一)
Collection of algorithm for sorting. 常见排序算法集(一)
Collection of algorithm for sorting (part one)
选择排序--Selection sort
可能你会觉得奇怪,为什么用结构体传参? 那是一层封装,我在面向对象的思想来写 : )
对已一个数组,不管怎么操作,都不能越界. C语言 不会自动检查数组越界。这个时候程序员就应该负起责任来。
数组的边界成为数组必不可少的信息,此时可以把array当作一个对象来看,即此时的element.
我们排序的对象可能会变,比方说从int类型变到char类型,这时候我们仅仅去改变struct element就可以了
不必要去改动API. 面向对象是一种思想。即使C语言不具备,但是程序员也应该有这种思想.把程序变得更棒.
/*************************************************** code writer : EOF code date : 2014.09.14 code file : selection_sort.c e-mail : jasonleaster@gmail.com ******************************************************/ #include <stdio.h> #define DEBUG #define ARRAY_SIZE 6 struct element { int array[ARRAY_SIZE]; int size; }; int selection_sort(struct element* element) { if(!element) { printf("element is NULL!\n"); return 0; } int tmp_1 = 0; int tmp_2 = 0; int swap = 0; int min_index = 0; for(tmp_1 = 0;tmp_1 < element->size;tmp_1++) { min_index = tmp_1; for(tmp_2 = tmp_1;tmp_2 < element->size;tmp_2++) { if(element->array[min_index] > element->array[tmp_2]) { min_index = tmp_2; } } swap = element->array[min_index]; element->array[min_index] = element->array[tmp_1]; element->array[tmp_1] = swap; } return 0; } #ifdef DEBUG void print_element(struct element* const element) { if(!element) { printf(""); return ; } int tmp = 0; for(tmp = 0;tmp < element->size; tmp++) { printf("%d ",element->array[tmp]); } printf("\n"); } int main() { /* ** Initialize this element. */ struct element test_element = { {1,4,9,6,3,2}, ARRAY_SIZE, }; printf("Before sorting\n"); print_element(&test_element); selection_sort(&test_element); printf("Before sorting\n"); print_element(&test_element); return 0; } #endif
插入排序 insertion sort
这里和上面的不同仅仅是排序算法的不同.
/*************************************************** code writer : EOF code date : 2014.09.14 code file : insertion_sort.c e-mail : jasonleaster@gmail.com ******************************************************/ #include <stdio.h> #define DEBUG #define ARRAY_SIZE 6 struct element { int array[ARRAY_SIZE]; int size; }; int insertion_sort(struct element* element) { if(!element) { printf("element is NULL!\n"); return 0; } int tmp_1 = 0; int tmp_2 = 0; int swap = 0; for(tmp_1 = 0;tmp_1 < element->size; tmp_1++) { for(tmp_2 = tmp_1;tmp_2-1 > 0 && tmp_2 > 0; tmp_2--) { if(element->array[tmp_2] < element->array[tmp_2-1]) { swap = element->array[tmp_2]; element->array[tmp_2] = element->array[tmp_2-1]; element->array[tmp_2-1] = swap; } else { break; } } } return 0; } #ifdef DEBUG void print_element(struct element* const element) { if(!element) { printf("Function:%s line:%d Somebody passed NULL into print_element\n",__FUNCTION__,__LINE__); return ; } int tmp = 0; for(tmp = 0;tmp < element->size; tmp++) { printf("%d ",element->array[tmp]); } printf("\n"); } int main() { /* ** Initialize this element. */ struct element test_element = { {1,4,9,6,3,2}, ARRAY_SIZE, }; printf("Before sorting\n"); print_element(&test_element); insertion_sort(&test_element); printf("Before sorting\n"); print_element(&test_element); return 0; } #endif
希尔排序 shell sort
如果搞定了上面的插入排序,希尔排序不是问题的...
自己写出来就会发现,希尔排序其实就是插入排序的一种改进.它把原来插入排序的一整个数组划分成多个小数组排序.
/*************************************************** code writer : EOF code date : 2014.09.14 code file : shell_sort.c e-mail : jasonleaster@gmail.com ******************************************************/ #include <stdio.h> #define DEBUG #define ARRAY_SIZE 6 struct element { int array[ARRAY_SIZE]; int size; }; int shell_sort(struct element* element) { if(!element) { printf("element is NULL!\n"); return 0; } int increment = 0; int tmp_1 = 0; int tmp_2 = 0; int swap = 0; for(increment = element->size/2; increment > 0;increment /=2 ) { for(tmp_1 = increment;tmp_1 < element->size;tmp_1++) { for(tmp_2 = tmp_1;tmp_2 >= increment;tmp_2 -= increment) { if(element->array[tmp_2] < element->array[tmp_2-increment]) { swap = element->array[tmp_2-increment]; element->array[tmp_2-increment] = element->array[tmp_2]; element->array[tmp_2] = swap; } } } } return 0; } #ifdef DEBUG void print_element(struct element* const element) { if(!element) { printf("Panic! NULL was passed into %s %d :(",__FUNCTION__,__LINE__); return ; } int tmp = 0; for(tmp = 0;tmp < element->size; tmp++) { printf("%d ",element->array[tmp]); } printf("\n"); } int main() { /* ** Initialize this element. */ struct element test_element = { {1,4,9,6,3,2}, ARRAY_SIZE, }; printf("Before sorting\n"); print_element(&test_element); shell_sort(&test_element); printf("Before sorting\n"); print_element(&test_element); return 0; } #endif
西斯廷圣母 拉斐尔
Collection of algorithm for sorting. 常见排序算法集(一)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。