C语言达成快速排序
发布时间:2021-11-19 11:28:53 所属栏目:PHP教程 来源:互联网
导读:我觉得冒泡排序是比较简单的;所以今天我们实现一个叫做快速排序的; Problem 你想要将(4,3,5,1,2)排序成(1,2,3,4,5) 你决定使用最简单的快速排序; Solution 首先,打开你的terminal,我写得C代码通常都是用vi编辑,gcc编译; vim quickSortSam
我觉得冒泡排序是比较简单的;所以今天我们实现一个叫做快速排序的; Problem 你想要将(4,3,5,1,2)排序成(1,2,3,4,5) 你决定使用最简单的快速排序; Solution 首先,打开你的terminal,我写得C代码通常都是用vi编辑,gcc编译; vim quickSortSample.c 因为,快速排序需要对数据进行分割然后处理,再分割再处理; 显然需要一个递归的过程; 所以,我们先把递归结束条件写好; #include <stdio.h> void quick_sort( int *a, int n) { int i, j, p, tmp; if (n < 2) return; } 也就是说,当输入只有一个数字就没有必要排序啦!直接返回; void quick_sort( int *a, int n) { int i, j, p, tmp; if (n < 2) return; p = a[n / 2]; // Get the middle element as pivot .. for ( i = 0, j = n -1;; i++, j--) { //TODO ... } } 注意: p = a[n / 2];的目地是获取数组中得中间位置的数据; 我们都知道,数组下标是整数,因此,如果n=3那么n/2应该是1,此时正好平分数组; 若是,n=4那么n/2应该是2,而此时它们就不完全是平分数组啦; for循环的作用是为了从前后两个方向分别遍历; void quick_sort( int *a, int n) { int i, j, p, tmp; if (n < 2) return; p = a[n / 2]; // Get the middle element as pivot .. for ( i = 0, j = n -1;; i++, j--) { while (a[i] < p) i++; while (p < a[j]) j--; } } 注意:我们在for循环中又进行啦while循环; 它的作用是对元素进行遍历,假设左边的数据没有p中保存的元素大,那么继续寻找,并且把i自增; 当找到比p大的或者相等得则停止第一个while循环; 例如:如果数组(2,5,3,1,4)那么p显然是3,当while循环发现5大于3时停止循环,此时i=1; 同理,第二个while循环中,p依然是3,当while循环第一次发现4大于3则继续循环此时j=4; 当while循环到j=3时,得到的元素是1,1不大于3所以停止循环,此时得到的j=3; 好啦!那么我们知道在for循环中没有明确指定循环停止条件; 它该什么时候停止呢? void quick_sort( int *a, int n) { int i, j, p, tmp; if (n < 2) return; p = a[n / 2]; // Get the middle element as pivot .. for ( i = 0, j = n -1;; i++, j--) { while (a[i] < p) i++; while (p < a[j]) j--; if ( i >= j) break; } } 注意:当i>=j意味着此时数据已经全部遍历完了; 因为i与j分布在数组左右两部分,当它们重合,当然也就表明它们遍历完啦; 刚才,我们的两个while循环分别找到啦一个左边比p大得元素,和一个右边比p小的数字; 显然这两个元素应该交换位置的; 那么怎么实现呢; void quick_sort( int *a, int n) { int i, j, p, tmp; if (n < 2) return; p = a[n / 2]; // Get the middle element as pivot .. for ( i = 0, j = n -1;; i++, j--) { while (a[i] < p) i++; while (p < a[j]) j--; if ( i >= j) break; tmp = a[i]; a[i] = a[j]; a[j] = tmp; //swap both .. } } 我们看到了,在冒泡排序中也用到得交换语句; 此时我们完全遍历了一遍数组; 我们在main函数中测试一下; #include <stdio.h> void quick_sort( int *a, int n) { int i, j, p, tmp; if (n < 2) return; p = a[n / 2]; // Get the middle element as pivot .. for ( i = 0, j = n -1;; i++, j--) { while (a[i] < p) i++; while (p < a[j]) j--; if ( i >= j) break; tmp = a[i]; a[i] = a[j]; a[j] = tmp; //swap both .. } } int main(void) { int a[] = { 2, 5, 3, 1, 4}; int n = sizeof a /sizeof a[0]; int i; for (i = 0; i < n; i++) printf("%d%s", a[i], i == n -1 ? "n" : " "); quick_sort(a, n); for (i = 0; i < n; i++) printf("%d%s", a[i], i == n -1 ? "n" : " "); return 0; } main函数的语句都非常容易懂,就不解释啦; 看看编译运行的结果: 显然,运行的结果是我们预期的; 3左边的都比3小啦!那若果数据多一些呢; 比如{ 2, 5, 7, 3, -1, 1, 4}我们会发现左边有两个元素都比3大,理论上要进行两次交换; 显然当它交换完[1]与[5]元素后,它又是怎么继续的我们关心这个问题; 显然交换完数据后,又进入for循环; for循环没有结束条件,因此,i++,j--完成后,此时i=2,j=4; 接下来执行两个while发现,第一个while发现a[2]是7 不小于p此时不执行i++; 同样在第二个while中也发现a[4]是-1不大于p此时不执行j--; 然后到if语句不成立,因此继续进行数据交换; 测试如下数据; #include <stdio.h> void quick_sort( int *a, int n) { int i, j, p, tmp; if (n < 2) return; p = a[n / 2]; // Get the middle element as pivot .. for ( i = 0, j = n -1;; i++, j--) { while (a[i] < p) i++; while (p < a[j]) j--; if ( i >= j) break; tmp = a[i]; a[i] = a[j]; a[j] = tmp; //swap both .. } } int main(void) { int a[] = { 2, 5, 7, 3, -1, 1, 4}; int n = sizeof a /sizeof a[0]; int i; for (i = 0; i < n; i++) printf("%d%s", a[i], i == n -1 ? "n" : " "); quick_sort(a, n); for (i = 0; i < n; i++) printf("%d%s", a[i], i == n -1 ? "n" : " "); return 0; } 我们会得到如下结果: 显然,我们已经得到啦p左边都是小于p的; 右边则是大于p的; 符合我们的设想; 为了把整个数组正确排序,我们需要分别又对两部分重复一遍刚才的操作; 好,我们递归的调用函数,并且把数组的两部分元素传递到函数中; void quick_sort( int *a, int n) { int i, j, p, tmp; if (n < 2) return; p = a[n / 2]; // Get the middle element as pivot .. for ( i = 0, j = n -1;; i++, j--) { while (a[i] < p) i++; while (p < a[j]) j--; if ( i >= j) break; tmp = a[i]; a[i] = a[j]; a[j] = tmp; //swap both .. } quick_sort( a, i); quick_sort( a + i, n - i); } 注意: 第一个递归调用处理数组的前部分,a对应的是数组的首地址,i是指对应的元素个数; 第二个递归调用处理数组后部分,a + i指的当然是首地址加偏移地址,如果你对偏移地址有问题的话,应该看看计算机寻址方式的资料啦; 接下来看运行结果: 最后,我们把所有代码附上: #include <stdio.h> void quick_sort( int *a, int n) { int i, j, p, tmp; if (n < 2) return; p = a[n / 2]; // Get the middle element as pivot .. for ( i = 0, j = n -1;; i++, j--) { while (a[i] < p) i++; while (p < a[j]) j--; if ( i >= j) break; tmp = a[i]; a[i] = a[j]; a[j] = tmp; //swap both .. } quick_sort( a, i); quick_sort( a + i, n - i); } int main(void) { int a[] = { 2, 5, 7, 3, -1, 1, 4}; int n = sizeof a /sizeof a[0]; int i; for (i = 0; i < n; i++) printf("%d%s", a[i], i == n -1 ? "n" : " "); quick_sort(a, n); for (i = 0; i < n; i++) printf("%d%s", a[i], i == n -1 ? "n" : " "); return 0; } (编辑:云计算网_泰州站长网) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |