滴滴笔试

快排+二分，写完通过率0，怒之！Arrays.sort提交

最好快排思想，然后Arrays.sort

冒泡。。也太低级了吧。

第二题不是经典堆排序么？

第二题直接用sort通过率只有80%，无奈之下用了最小堆；结果写完之后stl中有接口可以直接用

维护一个最小堆啊

冒泡，排序k次，通过了啊，为毛说太低级

不超过10行的python就能搞定。。。

STL里面的nth_element和partial_sort均可以高效解决此问题，最高效的是nth_element，基本思想是快速排序。具体可以参考本人博客：http://blog.csdn.net/bxw1992/article/details/76695461 void nth_element(vector<int> &vec, int num) 将最小（或最大）的num个数放在数组的开始处。注意num个数是无序的。 主要是利用快速排序的切分操作，源码针对枢轴的选取了优化措施（取待处理区间首、中间、尾3个值中的中间值作为枢轴，防止切分操作退化），这里为了简化，没有对枢轴的选取进行优化。 根据切分函数的返回值，判断是否达到了找出了num个满足要求的数，如果不满足，判断下一处理区间。 #include<iostream> #include<vector> using namespace std; void swap(int &a, int &b) { int temp; temp = a; a = b; b = temp; } int partition(vector<int> &vec,int low,int hi) { int mid = (hi - low) / 2 + low; int pivot = vec[low]; int i = low + 1; int j = hi; while (true) { while (i < hi && vec[i] < pivot) i++; while (j>low && vec[j]>pivot) j--; if (i >= j) break; swap(vec[i], vec[j]); i++; j--; } swap(vec[low],vec[j]); return j; } void nth_element(vector<int> &vec, int num) { int len = vec.size(); int low = 0; int hi = len - 1; while (low<hi) { int j = partition(vec,low,hi); if (j == num - 1) return; else if (j < num - 1) low = j+1; else hi = j - 1; } } void myprint(const vector<int> a) { for (int i = 0; i < a.size(); i++) { cout << a[i] << " "; } cout << endl; } int main() { vector<int> data = { 11,5, 4, 7, 6, 8, 1,10 }; myprint(data); nth_element(data,2); myprint(data); system("pause"); return 0; }

改进的快排可以做到O(n),冒泡怎么都是平方级

搜索bfprt算法

有归并排序做法吗？

直接一个Arrays.Sort搞定