一个无序数组a[n]，找出最大数和最小数，要求比较次数不超过1.5n

Question

如题。谢谢。

Answer 1

//stable 3/2*n
public static <T extends Comparable<? super T>> T[] getMinMax(T[] array)
{
T[] result = (T[]) Array.newInstance(array.getClass().getComponentType(), 2);
int length = array.length;
T min = array[0];
T max = array[0];
for (int i = ((length&0X1)==0?0:1); i < length; i = i+2)
{
T t1 = array[i];
T t2 = array[i+1];
if (t1.compareTo(t2)<0)
{
if(t1.compareTo(min)<0)
{
min=t1;
}
if(t2.compareTo(max)>0)
{
max=t2;
}
}
else
{
if(t1.compareTo(max)>0)
{
max=t1;
}
if(t2.compareTo(min)<0)
{
min=t2;
}
}
}
result[0] = min;
result[1] = max;
return result;
}

Answer 2

public class QuickSort implements SortStrategy 
{    private static final int CUTOFF = 3;             //当元素数大于此值时采用快速排序 
       /** 
       *利用快速排序算法对数组obj进行排序，要求待排序的数组必须实现了Comparable接口        */        public void sort(Comparable[] obj) 
       {   if (obj == null)               {  throw new NullPointerException("The argument can not be null!");               }               quickSort(obj, 0, obj.length - 1); 
       }        private void quickSort(Comparable[] obj, int left, int right)        {    if (left + CUTOFF > right)               {     SortStrategy ss = new ChooseSort();                      ss.sort(obj); 
              }  else               {   //找出枢轴点，并将它放在数组最后面的位置                      pivot(obj, left, right);                      int i = left, j = right - 1;                      Comparable tmp = null;                     while (true)                      {    //将i, j分别移到大于/小于枢纽值的位置                             //因为数组的第一个和倒数第二个元素分别小于和大于枢纽元，所以不会发生数组越界                             while (obj[++i].compareTo(obj[right - 1]) < 0)    {}                             while (obj[--j].compareTo(obj[right - 1]) > 0)      {}                            //交换                             if (i < j)                             {  tmp = obj[i];                                   obj[i] = obj[j];                                    obj[j] = tmp;                            }                            else    break; 
                     }                      //将枢纽值与i指向的值交换                      tmp = obj[i];                      obj[i] = obj[right - 1];                      obj[right - 1] = tmp;                      //对枢纽值左侧和右侧数组继续进行快速排序                      quickSort(obj, left, i - 1);                     quickSort(obj, i + 1, right); }        } 
       private void pivot(Comparable[] obj, int left, int right)        {  int center = (left + right) / 2;              Comparable tmp = null;              if (obj[left].compareTo(obj[center]) > 0)               {  tmp = obj[left];                      obj[left] = obj[center];                     obj[center] = tmp; 
              }               if (obj[left].compareTo(obj[right]) > 0)               {  tmp = obj[left];                      obj[left] = obj[right];                      obj[right] = tmp;               }               if (obj[center].compareTo(obj[right]) > 0)               { tmp = obj[center];                      obj[center] = obj[right];                      obj[center] = tmp; 
              }              //将枢纽元置于数组的倒数第二个                tmp = obj[center];               obj[center] = obj[right - 1];              obj[right - 1] = tmp;        } }时间是N的对数，最大和最小值在数组的第一个和最后一个

Answer 3

调用Arrays里的public static void sort(int[] a)方法
对int型数组进行升序排列  然后取第一个和最后一个

Answer 4

    public static int[] g(int[] iarr) {
        int a = iarr[0];
        int b = iarr[iarr.length - 1];
        if (a > b) {
            a = b;
            b = iarr[0];
        }
        for (int i = 1, il = iarr.length; i < il; i++) {
            if (iarr[i] < a) {
                a = iarr[i];
            } else {
                if (iarr[i] > b) {
                    b = iarr[i];
                }
            }
        }
        return new int[]{a, b};
    }