手记

常用算法

二分查找:

public static boolean search(int[] arr,int key){

    insertSort1(arr);  //查找前先要排序

    int left = 0,right = arr.length-1;

    boolean flag = false;

    if(key < arr[left] || key > arr[right])

        flag = false;

    while(left <= right){

        int mid = (left+right)/2;

        if(arr[mid] == key)

            flag = true;

        if(key > arr[mid]){

            left = mid+1;

        }else {

            right = mid-1;

        }

    }

    return flag;

}

快速排序:

public static void quickSort(int[] arr,int leftIndex,int rightIndex){

    int left = leftIndex,right = rightIndex;

    if(leftIndex < rightIndex){    //leftIndex==rightIndex时会不断执行递归造成栈溢出

       int pos = arr[left];     //定义一个标志位,放在if后面因为在右递归时有+1操作防止越界

        while(left < right){

            while(left < right && arr[right] >= pos){ //找到一个比标志位小的数arr[right]

                right--;

            }

            while(left < right && arr[left] <= pos){ //找一个比标志位大的数arr[left]

                left++;

            }

            swap(arr, left, right);//交换arr[right]和arr[right]

        }

        swap(arr,leftIndex,left); //让标志位归位

        System.out.println("标志位:"+pos);

        quickSort(arr, leftIndex, left);

        quickSort(arr, left+1, rightIndex);

    }

例如:对数组int[] arr = {6,3,1,5,2,9,7,8,12,11}排序,输出如下

折半插入排序:

public static void insertSort1(int[] arr){ //折半插入排序

    for(int i = 0;i < arr.length-1;i++){

        int low = 0,high = i;

        int temp = arr[i+1];

        while(low <= high){      //折半查找插入点

            int mid = (low+high)/2;

            if(temp > arr[mid])

                low = mid+1;

            else

                high = mid-1;

        }

    for(int j = i;j > high;j--){  //移动数组,为插入准备

        arr[j+1] = arr[j];

    }

    arr[high+1] = temp;  //插入

    }

}

直接插入排序:

public static void insertSort2(int[] arr){ //直接插入排序

    for(int i = 0;i < arr.length-1;i++){

            for(int j = i;j >= 0;j--){

                if(arr[j+1] < arr[j]){

                swap(arr, j,j+1);

                }

            }

        }

}

交换函数:

public static void swap(int[] arr, int i,int j) {

    int temp;

    temp = arr[i];

    arr[i] = arr[j];

    arr[j]  = temp;

}

生成随机数组:

public static int[] creatArray(int count,int maxNum){

    int [] arr = new int[count];

    for(int i=0;i< count;i++){

        arr[i] = new java.util.Random().nextInt(maxNum); //生成[0~maxNum)的随机数

    }

    return arr;

}

0人推荐
随时随地看视频
慕课网APP