快速排序

2012-12-28 22:30:12   最后更新: 2015-08-06 16:49:04   访问数量:751




快速排序算是最常用的排序算法了,过程有些复杂,不过只要记住这个排序算法的思路是:每次循环结束的时候,基准元素左侧的所有元素值都小于他,右侧的所有元素值都大于他,之后对左右两个子序列分别进行递归,这样就很好理解了

这个算法的最差时间复杂度为O(n*n),平均时间复杂度为O(nlogn),因为只有在完全逆序的情况下才会出现最差的情况,所以这个时间复杂度是完全可以接受的,并且也由此衍生出随机化的改进算法

而快速排序的空间复杂度为O(1),因此,即使在慢速的存储器中运行,性能依然优秀

其具体过程,我在面试中多次被问到,以我的一次交谈内容为例,即可说明:

 

"那你用快速排序排一下3 1 5 2 4  ,可以吧?"

我立即一笑:"好的,没有问题!首先i为0,j为1,基准是3,j位置上的1比基准3小,所以++i,++j,i为1指向1,j为2指向5"

"你这和刚才有什么区别?"

我一看对方不耐烦了,马上说"马上就可以看出区别了,现在j指向5,5比基准3大,于是++j,i不加"

"为什么不加?"

"因为i指向的是比基准小的最后一个元素,而j是寻找右面比基准大的元素,这之后,j指向2,这个时候,发现2比基准3小,于是要把i+1,然后i和j换,因为i是比基准小的最后一个元素,所以i+1以后指向的是第一个比基准大的元素,这个比基准大的元素和j指向的比基准小的元素交换以后i还是指向比基准小的最后一个元素,现在序列变成了3 1 2 5 4,然后j++以后指向4,4比基准3大,i不动,j++,超出范围,过程结束,基准和i换,就变成了1 2 3 5 4,现在,基准3左侧的元素都比他小,右侧的元素都比他大,之后对他左侧的1 2 右侧的 5 4分别进行递归运算,完成上述操作即可"

 

 

 

/* * file: main.c * author: 龙泉居士 * date: 2012-12-28 22:29 */ #include <stdio.h> #include "function/function.h" int quick_sort (int *array, int beg, int end) { if (beg >= end) return 0; int i=beg, j; for (j=i+1; j<=end; ++j) if (array[j] <= array[beg]) { ++i; exch(array, i, j); } exch(array, beg, i); quick_sort (array, beg, i-1); quick_sort (array, i+1, end); return 0; } int main () { int i, n=0; int array[256]; printf ("Please input numbers, end by 9999:\n"); while (1) { scanf ("%d", &array[n]); if (array[n] == 9999) break; ++n; } if (quick_sort(array, 0, n-1)) return -1; for (i=0; i!=n; ++i) printf ("%d ", array[i]); printf ("\n"); return 0; }

 

 

/* * file: function.h * author: 龙泉居士 * date: 2012-12-28 22:30 */ #ifndef FUNCTION_H_20121228 #define FUNCTION_H_20121228 int exch (int *array, int a, int b); #endif /* * file: function.c * author: 龙泉居士 * date: 2012-12-28 22:31 */ #include <stdio.h> #include "function.h" int exch (int *array, int a, int b) { if (array[a]!=array[b]) { if (array == NULL) { printf ("build_heap param error"); return -1; } array[a] = array[a]^array[b]; array[b] = array[a]^array[b]; array[a] = array[a]^array[b]; } return 0; }

 

 






读书笔记      技术帖      算法      算法导论      数据结构      龙潭书斋      排序      快速排序      qsort      quicksort     


京ICP备15018585号