一道关于排序的java面试题..算法帝进·~

发布网友发布时间：2022-04-26 09:42

共1个回答

热心网友时间：2022-06-26 22:57

1. 采用快速排序，一般可以达到O(Nlog(N)),最糟糕情况是O(N^2)。2. 基本思想：对于排列成递增序列，每次将数组分成两半，确保左边的小于右边的，而后递归调用；递减序列相反。3. 代码：仅供参考（代码摘自 http://www.roseindia.net/java/beginners/arrayexamples/QuickSort.shtml），加了中文注释。public class QuickSort{
public static void main(String a[]){
int i;
int array[] = {12,9,4,99,120,1,3,10,13};
System.out.println("Quick Sort\n\n");
System.out.println("Values Before the sort:\n");
for(i = 0; i<array.length; i++)
System.out.print( array[i]+" ");
System.out.println();
quick_srt(array,0,array.length-1);
System.out.print("Values after the sort:\n");
for(i = 0; i <array.length; i++)
System.out.print(array[i]+" ");
System.out.println();
System.out.println("PAUSE");
}
public static void quick_srt(int array[],int low, int n){
int lo = low;
int hi = n;
if (lo >= n) { // 判断排序是否终止
return;
}
int mid = array[(lo + hi) / 2];// 取数组中值，保证左边的都比它小，右边的都比它大
while (lo < hi) {
while (lo<hi && array[lo] < mid) { // 跳过已经满足的，左边小。
lo++;
}
while (lo<hi && array[hi] > mid) { // 跳过已经满足的，右边大。
hi--;
}
if (lo < hi) {//各自指到左右两端不符合条件的位置，交互
int T = array[lo];
array[lo] = array[hi];
array[hi] = T;
}
}
if (hi < lo) {
int T = hi;
hi = lo;
lo = T;
}
// 分别处理两个字串
quick_srt(array, low, lo); // 左
quick_srt(array, lo == low ? lo+1 : lo, n); // 右
}
}4. BTW，中文参考楼上提供的博文链接。