Qz学算法-数据结构篇(排序算法--快速、归并)

public class QuickSort {
    public static void main(String[] args) {
        int arr[] = {-9,78,0,23,-567,70};
        quickSort(arr,0, arr.length-1);
        System.out.println(Arrays.toString(arr));

    }
    public static void quickSort(int[]arr,int left,int right){
        int l = left; //左下标
        int r = right; //右下标
        int pivot = arr[(left+right)/2];
        int temp = 0; //临时变量
        //while循环的目的是让比pivot值小放到左边
        //比pivot值小放到右边
        while(l<r){
            //在pivot的左边一直找，找到大于等于pivot值，才退出
            while(arr[l]<pivot){
                l+=1;
            }
            //在pivot的左边一直找，找到小于等于pivot值，才退出
            while (arr[r]>pivot){
                r-=1;
            }
            //如果1>=r说明pivot的左右两的值，已经按照左边全部是
            //小于等于pivot值，右边全部是大于等于pivot值
            if (l>=r){
                break;
            }

            //交换
            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;

            //如果交换完后,发现arr[l] == pivot 值相等 ,r--前移
            if(arr[l]==pivot){
                r-=1;
            }
            //如果交换完后，发现这个arr[r]=pivot值相等l+,后移
            if (arr[r]==pivot){
                l+=1;
            }
        }

        //如果 l == r ,必须1++，下--，否则为出现栈溢出
        if (l==r){
            l+=1;
            r-=1;
        }
        //向左递归
        if (left<r){
            quickSort(arr, left, r);
        }
        //向右递归
        if (right>l){
            quickSort(arr,l,right);
        }
    }
}

public class MergetSort {
    public static void main(String[] args) {
        int arr[] = {8, 4, 5, 7, 1, 3, 6, 2};
        int temp[] = new int[arr.length]; //归并排序需要一个额外空间
        mergeSort(arr, 0, arr.length - 1, temp);

        System.out.println("归并排序后:" + Arrays.toString((arr)));
    }


    //分+合方法
    public static void mergeSort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = (left + right) / 2;//中间索引
            //像左递归进行分解
            mergeSort(arr, left, mid, temp);
            //向右递归进行分解
            mergeSort(arr, mid + 1, right, temp);
            //到合并
            merge(arr,left,mid,right,temp);
        }
    }


    /**
     * 合并的方法
     *
     * @param arr   排序的原始数组
     * @param left  左边有序序列的初始索引
     * @param mid   中间索引
     * @param right 右边索引
     * @param temp  做中转的数组
     */
    public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left; //初始化1，左边有序序列的初始素引
        int j = mid + 1;//初始化j,右边有序序列的初始索引
        int t = 0; //指向temp数组的当前索引

        //(1)
        //先把左右两边（有序）的数据按照规则填充到temp数组
        //直到左右两边的有序序列，有一边处理完毕为止
        while (i <= mid && j <= right) {
            //如果左边得有序序列得当前元素,小于等于右边有序序列得当前元素
            //即将左边的当前元素，拷贝到temp数组
            //然后t++,i++
            if (arr[i] <= arr[j]) {
                temp[t] = arr[i];
                t += 1;
                i += 1;
            } else {//反之,将右边有序序列得当前元素,填充到temp数组
                temp[t] = arr[j];
                t += 1;
                j += 1;
            }
        }
        //(2)
        //把有剩余数据的一边的数据依次全部填充到temp
        while (i <= mid) {//左边的有序序列还有剩余的元素，就全部填充到tmp
            temp[t] = arr[i];
            t += 1;
            i += 1;
        }
        while (j <= right) {//右边的有序序列还有剩余的元素，就全部填充到temp
            temp[t] = arr[j];
            t += 1;
            j += 1;
        }
        //(3)
        //将temp数组的元素拷贝到arr
        //注意并不是每次都拷贝所有
        t = 0;
        int tempLeft = left;
        while (tempLeft <= right) {
            arr[tempLeft] = temp[t];
            t += 1;
            tempLeft += 1;
        }
    }
}