最近为公司面试，老大要求每个候选人都要写几段简单代码，本着考察写代码基本功的目的并没出复杂的题目，出现最多的就是数组排序，以往候选人都是热衷于冒泡实现，昨天来的两个候选人突然都主动要求快排实现，一时心血来潮自己撸了一下快速排序的实现，代码如下：
public static void quickSort(int[]data) {
if(data == null || data.length
return;
}
quickSort(data,0,data.length -1);
}
public static void quickSort(int[]data,int left,int right) {
if(left > right) {
return;
}
int low = left,high = right;
int temp = data[right];
while(low
while(data[low]
low++;
}
while(data[high] >= temp && low
high--;
}
if(low
int t = data[low];
data[low] = data[high];
data[high] = t;
}
}
data[right] = data[low];
data[low] = temp;
quickSort(data,left,low - 1);
quickSort(data,low + 1,right);
}
测试OK，但有个严重的问题，在数据已经排好序的情况下有可能退化到O(n^2)的复杂度，用100w的样本测试下：
public static void main(String[] args) {
int []array = new int[1000000];
for(int i=0;i
array[i] = i;
}
quickSort(array);
}
额，直接栈溢出了因为用到了递归，在极端情况栈的深度和数组的长度是一样的
那改造一下，下面是用栈的一个实现：
public static void quickSortStack(int[]array) {
if(array == null || array.length
return;
}
Stack
Stack
topStack.add(0);
tailStack.add(array.length - 1);
while(!topStack.isEmpty()) {
if(topStack.size() % 1000 == 0) {
System.out.println(topStack.size());
}
int top = topStack.pop();
int tail = tailStack.pop();
if(top >= tail) {
continue;
}
int i = top,j=tail;
int flag = array[top];
while(i
while(flag
j--;
}
while(flag >= array[i] && i
i++;
}
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
array[top] = array[i];
array[i] = flag;
topStack.add(top);
topStack.add(i + 1);
tailStack.add(i - 1);
tailStack.add(tail);
}
}
运行一下，对是对了，但是时间有点太长了吧:
sort start at 1578140130237
sort end at 1578140453250
花费了323s，5分半钟才完成，原因就是待排数组是生序，那继续改造下，随机选取一个值，如下：
public static void quickSortStackRandom(int[]array) {
if(array == null || array.length
return;
}
Stack
Stack
topStack.add(0);
tailStack.add(array.length - 1);
Random rand = new Random();
while(!topStack.isEmpty()) {
int top = topStack.pop();
int tail = tailStack.pop();
if(top >= tail) {
continue;
}
int i = top,j=tail;
int index = rand.nextInt(tail - top + 1) + top;
int flag = array[index];
array[index] = array[top];
while(i
while(flag
j--;
}
while(flag >= array[i] && i
i++;
}
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
array[top] = array[i];
array[i] = flag;
topStack.add(top);
topStack.add(i + 1);
tailStack.add(i - 1);
tailStack.add(tail);
}
}
运行下：
sort start at 1578140718702
sort end at 1578140718943
好了，大概240ms，但是等等，如果待排数组大部分数据相等会有问题吗，考虑极端情况，每个数据都相等会发生什么？写个case测试下：
public static void main(String[] args) {
int []array = new int[1000000];
for(int i=0;i
array[i] = 10;
}
quickSort(array);
}
这里我把数组的数据都改成10，运行下：
sort start at 1578141345135
sort end at 1578142101369
时间大概在760s左右
虽然使用了随机快排，但是由于每个数据都一样，还会导致左右严重不平衡，还需要改造下，改成随机+双路快排，代码如下：
public static void quickSortStackRandomDouble(int[]array) {
if(array == null || array.length
return;
}
Stack
Stack
topStack.add(0);
tailStack.add(array.length - 1);
Random rand = new Random();
while(!topStack.isEmpty()) {
int top = topStack.pop();
int tail = tailStack.pop();
if(top >= tail) {
continue;
}
int i = top + 1,j=tail;
int index = rand.nextInt(tail - top + 1) + top;
int flag = array[index];
array[index] = array[top];
while(true) {
while(j >= top && flag
j--;
}
while(i array[i]) {
i++;
}
if(i > j) {
break;
}
int temp = array[i];
array[i] = array[j];
array[j] = temp;
i++;
j--;
}
array[top] = array[j];
array[j] = flag;
topStack.add(top);
topStack.add(j + 1);
tailStack.add(j - 1);
tailStack.add(tail);
}
}
运行下：
sort start at 1578142286529
sort end at 1578142286790
耗时241ms
使用排好序的样本数据试下：
sort start at 1578142326891
sort end at 1578142327143
耗时252ms
使用随机数据实验下：
sort start at 1578142381125
sort end at 1578142381446
耗时321ms
更优的还有三路快排，暂时先不说了，细细想了下一个快排还有N多种玩法，如果不注意，一个普通的实现碰到极端情况是可以把机器累死的哈哈！！
本文来自投稿，不代表本人立场，如若转载，请注明出处：http://www.sosokankan.com/article/2026323.html