总结顺序表的算法

顺序表的优缺点

1.优点： 尾插效率高，支持随机访问。

2.缺点： 中间插入或者删除效率低。

3.应用： 数组 ArrayList

插入：从插入的位置开始，后面的数据要一直往后挪
删除：从删除的位置开始，后面的数据要一直往前挪

所以性能会比较低

/**
 * 插入
 */
public void insert(int[] array, int x, int index){
    for (int i = array.length; i > index; i--) {
        array[i] = array[i-1];
    }
    array[index] = x;
}

/**
 * 删除
 */
public void delete(int[] array, int index){
    for (int i = index; i < array.length - 1; i++) {
        array[i] = array[i + 1];
    }
    array[array.length - 1] = 0;  //用0来填充， C语言：\0 填充
}

1、交换a、b，性能分析

//做 a b 算法
int a = 5;
int b = 6;
//1. 可读性做好
int t = a; a = b; b = t;
System.out.println("1.a = " + a + ", b = " + b);

//2. 加减法
a = a + b; //11
b = a - b; //11-6=5
a = a - b; //11-5=6
System.out.println("2.a = " + a + ", b = " + b);

//3. 性能最优（没有可读性）  应用场景：无人机、跑步机
a = a ^ b;
b = a ^ b;
a = a ^ b;
System.out.println("3.a = " + a + ", b = " + b);

2、蛮力法：冒泡排序

从前面2个进行大小比较，进行交换。然后依次比较。

/**
 * 蛮力法，冒泡排序
 * 例子：3 1 5 8 2 9 4 6 7 
 * 时间复杂度：n*(n-1)/2  -> 趋近于n
 * @param array
 */
public static void bubbleSort(int[] array){
    for(int i=array.length-1;i>0;i--) {
        boolean flag=true;
        for (int j = 0; j < i; j++) {
            if (array[j] > array[j + 1]) {
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
                flag=false;
            }
        }
        if(flag){//说明后面都是排好序的，不用排序了
            break;
        }
    }
}

3、选择排序

定位最前的一个值，然后在进行后面所有的值比较大小，找到最小的就和定位的那个值进行交换，然后依次进行。

/**
 * 选择排序法
 * 例子：{1,2,5,8,3,9,4,6,7}
 * @param array
 */
public static void selectSort(int[] array){
    for(int i=0;i<array.length-1;i++) {
        int index = i;
        for (int j = i+1; j < array.length; j++) {
            if (array[j] < array[index]) {
                index = j;
            }
        }
        if(index!=i) {//如果已经是最小的，就不需要交换
            int temp = array[index];
            array[index] = array[i];
            array[i] = temp;
        }
    }
}

4、二分查找

/**
 * 二分查找，从中间一直一次往数据的两边中间查找
 */
public static int binarySearch(int[] array,int fromIndex,int toIndex,int key){
    int low=fromIndex;
    int high=toIndex-1;
    while(low<=high){
        int mid=(low+high)/2;//取中间
        int midVal=array[mid];
        if(key>midVal){//去右边找
            low=mid+1;
        }else if(key<midVal){//去左边找
            high=mid-1;
        }else{
            return mid;
        }
    }
    return -(low+1);//low+1表示找不到时停在了第low+1个元素的位置
}

5、快速排序（前序排序）

/**
 * 快速排序  31  21  59  68  12  40
 *         x=31
 * @param array
 * @param begin
 * @param end
 */
//
public static void quickSort(int[] array,int begin,int end){
    if(end-begin<=0) return;
    int x=array[begin];
    int low=begin;//0
    int high=end;//5
    //由于会从两头取数据，需要一个方向
    boolean direction=true;
    L1:
    while(low<high){
        if(direction){//从右往左找
            for(int i=high;i>low;i--){
                if(array[i]<=x){
                    array[low++]=array[i];
                    high=i;
                    direction=!direction;
                    continue L1;
                }
            }
            high=low;//如果上面的if从未进入，让两个指针重合
        }else{
            for(int i=low;i<high;i++){
                if(array[i]>=x){
                    array[high--]=array[i];
                    low=i;
                    direction=!direction;
                    continue L1;
                }
            }
            low=high;
        }
    }
    //把最后找到的值 放入中间位置
    array[low]=x;
    //开始完成左右两边的操作
    quickSort(array,begin,low-1);
    quickSort(array,low+1,end);
}

6、分治法：归并排序（后序排序）

/**
 * 归并排序
 * @param array
 * @param left
 * @param right
 */
public static void mergeSort(int array[],int left,int right){
    if(left==right){
        return;
    }else{
        int mid=(left+right)/2;
        mergeSort(array,left,mid);
        mergeSort(array,mid+1,right);
        merge(array,left,mid+1,right);
    }
}

/**
 * 归并排序
 *
 * 0    4   7
 * 1  2  5  9 === 3  4  10  11
 *
 * @param array
 * @param left
 * @param mid
 * @param right
 */
public static void merge(int[] array,int left,int mid,int right){
    int leftSize=mid-left;
    int rightSize=right-mid+1;
    //生成数组
    int[] leftArray=new int[leftSize];
    int[] rightArray=new int[rightSize];
    //填充数据
    for(int i=left;i<mid;i++){
        leftArray[i-left]=array[i];
    }
    for(int i=mid;i<=right;i++){
        rightArray[i-mid]=array[i];
    }
    //合并
    int i=0;
    int j=0;
    int k=left;
    while(i<leftSize && j<rightSize){
        if(leftArray[i]<rightArray[j]){
            array[k]=leftArray[i];
            k++;i++;
        }else{
            array[k]=rightArray[j];
            k++;j++;
        }
    }
    while(i<leftSize){
        array[k]=leftArray[i];
        k++;i++;
    }
    while(j<rightSize){
        array[k]=rightArray[j];
        k++;j++;
    }
}