每天分享职场生活、职场攻略、领导同事相处技巧和创业资源
文|洪生鹏
在软件开发过程中，经常要使用到排序算法，快速排序由于排序效率在同为平均时间复杂度O(N*logN)的几种排序方法中效率较高，被采用概率较多。
在最坏的情况下，可能相邻的两个数进行交换，最差时间复杂度和冒泡排序是一致的，都是O(N2)。
快速排序算法思想其实是分治法。很多软件公司的笔试面试，包括BAT等知名IT公司都喜欢用这个考验求职者。掌握好快速排序算法很有必要。总的说来，要手写出快速排序算法还是有一定难度的。下面我们一起来看看：
快速排序算法大意是：先选一个“标尺”， 用它把整个队列过一遍筛子， 以保证：其左边的元素都不大于它，其右边的元素都不小于它。这样，排序问题就被分割为两个子区间。
然后再分别对子区间排序。
/**
* 快速排序算法
* @param arr
* @param left
* @param right
*/
public void quickSort(int arr[], int left, int right) {
if (left > right) {
return;
}
int i = left;
int j = right;
//将最左端元素作为基准值
int temp = arr[left];
while (i != j) {
//往左移位，直到大于temp
while (i < j && arr[j] >= temp) {
j--;
}
//往右移位，直到小于temp
while (i < j && arr[i] <= temp) {
i++;
}
if (i < j) {
//数据交换处理
int tt = arr[i];
arr[i] = arr[j];
arr[j] = tt;
}
}
//交换基位数据
int k = arr[i];
arr[i] = temp;
arr[left] = k;
quickSort(arr, left, i - 1);
quickSort(arr, j + 1, right);
}
使用
int[] arr = {50, 38, 99, 97, 76, 13, 27};
quickSort(arr, 0, arr.length-1);
for (int i = 0; i < arr.length; i++) {
LogUtil.e(TAG, arr[i] + "");
}
由于笔者水平有限,文中错漏之处在所难免，欢迎交流。
閱讀更多 洪生鵬 的文章
