尼古丁有镇定作用:一步一步写算法(之快速排序)
来源:百度文库 编辑:偶看新闻 时间:2024/05/07 11:44:45
一步一步写算法(之快速排序)
分类: 数据结构和算法 2011-10-05 14:47 2062人阅读 评论(6) 收藏 举报【 声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱:feixiaoxing @163.com】
快速排序是编程中经常使用到的一种排序方法。可是很多朋友对快速排序有畏难情绪,认为快速排序使用到了递归,是一种非常复杂的程序,其实未必如此。只要我们使用好了方法,就可以自己实现快速排序。
首先,我们复习一下,快速排序的基本步骤是什么:
1、 判断输入参数的合法性
2、把数组的第一个数据作为比较的原点,比该数据小的数据排列在左边,比该数据大的数据排列在右边
3、按照(2)的方法分别对左边的数组和右边的数据进行和(2)一样的数据排列
那么实际编写代码中,应该怎么做呢?
a)首先,判断数据的合法性?
view plaincopy to clipboardprint?
- void quick_sort(int array[], int length)
- {
- int median = 0;
- if(NULL == array || 0 == length)
- return;
- _quick_sort(array, 0, length -1);
- }
view plaincopy to clipboardprint?
- void _quick_sort(int array[], int start, int end)
- {
- int middle;
- if(start >= end)
- return;
- middle = get_middle(array, start, end);
- _quick_sort(array, start, middle -1);
- _quick_sort(array, middle + 1, end);
- }
- void quick_sort(int array[], int length)
- {
- int median = 0;
- if(NULL == array || 0 == length)
- return;
- _quick_sort(array, 0, length-1);
- }
view plaincopy to clipboardprint?
- int get_middle(int array[], int start, int end)
- {
- int front = 0;
- int tail = end - start;
- int value = array[start];
- int length = end - start + 1;
- int loop = start + 1;
- while(loop <= end){
- if(array[loop] < value){
- gQuickSort[front] = array[loop];
- front ++;
- }else{
- gQuickSort[tail] = array[loop];
- tail --;
- }
- loop ++;
- }
- gQuickSort[front] = value;
- memmove(&array[start], gQuickSort, sizeof(int) * (length));
- return start + front ;
- }
注意:这里gQuickSort是一个全局数组,主要是为了作为排序的临时数组使用,实际环境中大家可以灵活运用各种方法。
d)基本的快速排序就完成了,那我们怎么测试呢?我们可以编写几个简单的测试用例?
view plaincopy to clipboardprint?
- static void test1()
- {
- int array[] = {1};
- quick_sort(array, sizeof(array)/sizeof(int));
- }
- static void test2()
- {
- int array[] = {2, 1};
- quick_sort(array, sizeof(array)/sizeof(int));
- assert(1 == array[0]);
- assert(2 == array[1]);
- }
- static void test3()
- {
- int array[] = {4, 3, 2,1};
- quick_sort(array, sizeof(array)/sizeof(int));
- assert(1 == array[0]);
- assert(2 == array[1]);
- assert(3 == array[2]);
- assert(4 == array[3]);
- }
- static void test4()
- {
- int array[] = {3, 2, 1};
- quick_sort(array, sizeof(array)/sizeof(int));
- assert(1 == array[0]);
- assert(2 == array[1]);
- assert(3 == array[2]);
- }
【预告: 下一篇博客主要介绍合并排序的内容】
快速排序的循环算法
用C语言写一个排序算法。
排序。随机生成若干个数据,程序将数据排序后输出,分别使用快速排序,希尔排序,冒泡排序算法进行排序。
用快速分类算法给出数据(49,38,65,97,76,13,27,49)的第一趟排序过程
java中用快速排序(排序算法应该是正确的),不报错,但执行起来不行。在elipse中执行的。
java中用快速排序(排序算法应该是正确的),不报错,但执行起来不行。在elipse中执行的。
谁会对C++中的排序算法,比如冒泡排序,插入排序,选择排序,快速排序等的MPI并行实现代码?
设计一个用链表表示的简单选择排序的算法,并实现之(试验报告)
结构体排序算法
asp排序算法
什么是起泡排序算法??
急求一排序算法
合并排序算法
vb选择排序算法
内部排序算法比较
内部排序算法比较
整数排序算法的问题?
堆排序的具体算法
求几种排序法的算法
全排序的算法(PASCAL)
快速排序vc
一、题目:三种典型排序算法及其比较(直接法、插入法、shell排序比较)
请教算法高手:还是关于排序!
pascal 排序算法的一道选择题。Help!