首页 > 代码库 > 快速排序
快速排序
快速排序和归并排序都是分治法的典型应用，主要区别在于，快速排序重在分，而归并排序重在治。
快速排序基于以下假设：已知x，序列中一半的数据大于x，另一半小于等于x，且小于等于x的数据在数组前一半，大于x的在后一半。这种分割不需要额外的存储空间，对两侧数据分别递归进行，最终数组排序即可完成。
实际上，x未知时算法依然有效。对于任意支点pivot，和指向左右两端的指针L，R，指针相向而行。对任意i，i < L，有pivot>=x[i]; 任意j，j>R, 有pivot< x[j];
1) L < R, 如果X[L] <= pivot 或者 X[R] > pivot，继续右移L或左移R。否则，X[L] > pivot 并且 X[R] <= pivot，只需交换X[L]，X[R]，然后继续移动指针，直至相遇。
2) L = R时，除X[L]外，序列分割完毕。
剩下的问题就是选取支点pivot。以上分析可以看出，支点可以任意选取，为简单选取最左端。快速排序代码如下：
1 int qsort(int A[], int l, int r) 2 { 3 int pivot; 4 if (l < r) 5 { 6 pivot = partition(A, l, r); 7 qsort(A, l, pivot - 1); 8 qsort(A, pivot + 1, r); 9 } 10 }11 12 int partition(int A[], int l, int r)13 {14 int pivot = l;15 int L = l, R = r;16 while (L <= R)17 { 18 while ((L <= r) && (A[L] <= A[pivot]))19 L++;20 while ((R >= l) && (A[R] > A[pivot]))21 R--;22 if (L < R)23 exchange(A[L], A[R]);24 } 25 exchange(A[pivot], A[R]);26 pivot = R;27 28 return pivot;29 }
一次辅助算法partition的时间为O(n), qsort时间复杂度为O(nlbn).
快速排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。