本文主要是介绍百度、腾讯、 阿里等大公司喜欢用这个考验求职者,40%求职者容易忽略,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
在软件开发过程中,经常要使用到排序算法,快速排序由于排序效率在同为平均时间复杂度O(N*logN)的几种排序方法中效率较高,被采用概率较多。
在最坏的情况下,可能相邻的两个数进行交换,最差时间复杂度和冒泡排序是一致的,都是O(N2)。
快速排序算法思想其实是分治法。很多软件公司的笔试面试,包括BAT等知名IT公司都喜欢用这个考验求职者。掌握好快速排序算法很有必要。总的说来,要手写出快速排序算法还是有一定难度的。下面我们一起来看看:
快速排序算法大意是:先选一个“标尺”, 用它把整个队列过一遍筛子, 以保证:其左边的元素都不大于它,其右边的元素都不小于它。这样,排序问题就被分割为两个子区间。
然后再分别对子区间排序。
1/**
2 * 快速排序算法
3 * @param arr
4 * @param left
5 * @param right
6 */
7public void quickSort(int arr[], int left, int right) {
8 if (left > right) {
9 return;
10 }
11 int i = left;
12 int j = right;
13 //将最左端元素作为基准值
14 int temp = arr[left];
15 while (i != j) {
16 //往左移位,直到大于temp
17 while (i < j && arr[j] >= temp) {
18 j--;
19 }
20 //往右移位,直到小于temp
21 while (i < j && arr[i] <= temp) {
22 i++;
23 }
24 if (i < j) {
25 //数据交换处理
26 int tt = arr[i];
27 arr[i] = arr[j];
28 arr[j] = tt;
29 }
30 }
31 //交换基位数据
32 int k = arr[i];
33 arr[i] = temp;
34 arr[left] = k;
35
36 quickSort(arr, left, i - 1);
37 quickSort(arr, j + 1, right);
38}
使用
1int[] arr = {50, 38, 99, 97, 76, 13, 27};
2quickSort(arr, 0, arr.length-1);
3 for (int i = 0; i < arr.length; i++) {
4 LogUtil.e(TAG, arr[i] + "");
5}
由于笔者水平有限,文中错漏之处在所难免,欢迎交流。
【END】
觉得此文对你有帮助
请随手转发到朋友圈
感谢有你
往期精选推荐
程序员32岁前跳槽大多数看薪资,那里福利好去那里,32岁后请慎重
一位国企女程序员的烦恼
分享职场攻略、技术心得和创业资源
更多精彩内容,请长按识别关注
这篇关于百度、腾讯、 阿里等大公司喜欢用这个考验求职者,40%求职者容易忽略的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!