引言

Java二分查找的实现和递归实现快速排序。

二分查找

题目描述：

输入整数n(n>0&&n<=100)，表示数组的长度

输入n个正整数（递增），作为数组元素

输入1个正整数，作为要查找的元素

输出：利用二分查找输出要查找的元素在数组中的下标位置，若没有这个数则输出no

二分查找：又叫折半查找，要求待查找的序列有序。每次取中间位置的值与待查关键字比较，如果中间位置的值比待查关键字大，则在前半部分循环这个查找的过程，如果中间位置的值比待查关键字小，则在后半部分循环这个查找的过程。直到查找到了为止，否则序列中没有待查的关键字。

import java.util.Scanner;

public class binarySearch {
    public static void main(String[] args) {
        int len;
        int[] array = new int[100];
        int toSearch;
        int curpos;
        boolean flag;
        int low;
        int high;
        Scanner in = new Scanner(System.in);
        while(in.hasNext()) {
            len = in.nextInt();
            for(int i=0; i<len; i++) {
                array[i] = in.nextInt();
            }
            toSearch = in.nextInt();
            flag = false;
            low = 0;
            high = len - 1;
            curpos = (low + high) / 2;
            while(low <= high) {
                if(array[curpos] > toSearch) {
                    high = curpos - 1;
                } else if (array[curpos] < toSearch) {
                    low = curpos + 1;
                } else {
                    flag = true;
                    break;
                }
                curpos = (low + high) / 2;
            }
            if(!flag) {
                System.out.println("no");
                continue;
            }
            System.out.println(curpos);
        }
    }
}

快速排序

题目描述

快速排序是常用排序算法，请参考以下资料实现对一组数组的升序快速排序

思路：

数组中选择一个数作为基准点（可以选第一个元素，也可以任意选择）
将所有大于基准点的放在基准点右侧，所有小于基准点的放在其左侧
针对基准点左侧和右侧的区间，重复步骤1和2，直到各区间只有一个数

参考网址：http://tools.jb51.net/aideddesign/paixu_ys

import java.util.Scanner;

public class quickSort {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNext()) {
            int len = in.nextInt();
            int[] array = new int[len];
            for (int i=0;i<len;i++) {
                array[i] = in.nextInt();
            }
            qSort(array, 0, array.length - 1);
            for (int j=0;j<len;j++) {
                System.out.printf("%d ", array[j]);
            }
            System.out.println();
        }
    }

    public static void qSort(int[] array, int p, int r) {
        int q;
        if (p < r) {
            q = partition(array, p, r);
            qSort(array, p, q - 1);
            qSort(array, q + 1, r);
        }
    }

    public static int partition(int[] array, int p, int r) {
        int x = array[r];
        int i = p - 1; // 指向的是比主元素小的位置
        int temp;
        for (int j=p;j<=r-1;j++) {
            if (array[j] <= x) {
                i++;
                temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
        temp = array[i+1];
        array[i+1] = array[r];
        array[r] = temp;
        return i + 1;
    }
}