首页 > 代码库 > 快速排序之单项扫描法
快速排序之单项扫描法
快速排序是排序算法中最受青睐的算法之一，相对于堆排序和归并排序而言，即便具有相同的复杂度O(NlogN)。面对大数据而言，快排的效率也更高。一般而言，数据结构中的排序算法都是采取的双向指针法。在之前写的一篇博文《排序算法（初级版）之快排、归并、堆排序》中已经有过总结。这里就不再啰嗦了。
本篇博文主要讲一下，快拍的单项扫描实现，可以实现对链表的快拍。同时，本算法可以高效的解决《剑指offer》中的“寻找最小k个数”
以下内容主要摘自《算法导论》：
本算法将待排序数组array分成四部分：比pivot小的，比pivot大的，尚未扫描的，pivot：
算法过程如下：
具体实现：
public void qSort(int[] a,int begin,int end){ if(begin >= end) return; int mid = partition(a, begin, end); qSort(a, begin, mid - 1); qSort(a, mid + 1, end); } public int partition(int[] a,int p ,int r){ int x = a[r]; int i = p - 1; int j = p; for(j = p; j < r; j++){ if(a[j] < x){ i++; swap(a, i, j); } } swap(a, i + 1, j); return i + 1; } 如此看来单向扫描法具体的实现起来并不比双向扫描复杂，同时适应性更广；
下面再利用partition实现一下，O(n)复杂度找到“前k小/大的元素”
1 public int findKSmallEle(int[] a,int k){ 2 if(k >= a.length || k < 0) return -1; 3 qSelect(a, k, 0, a.length - 1); 4 return a[k]; 5 } 6 7 private void qSelect(int[] a,int k ,int q,int r){ 8 if(q < r){ 9 int index = partition(a, q, r);10 if(index > k){11 qSelect(a, k, q, index - 1);12 }else if(index < k){13 qSelect(a, k, index + 1, r);14 }else15 return;16 }17 }
快速排序之单项扫描法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。