JAVA排序

快排

• 归并排序将数组分为两个子数组分别排序，并将有序的子数组归并使得整个数组排序；
• 快速排序通过一个切分元素将数组分为两个子数组，左子数组小于等于切分元素，右子数组大于等于切分元素，
• 将这两个子数组排序也就将整个数组排序了

https://www.bilibili.com/video/BV117411x72U?p=2

package com.kuang.offer;
public class quickSort {
    public static int[] arr = new int[]{3, 2, 6, 8, 9 , 10, 1,11,5,97,888};
    public static void main(String[] args) {
        quick(arr, 0, arr.length - 1);
        for(int i: arr){
            System.out.println(i);
        }
    }
    public static void quick(int[] arr, int left, int right){
        if(arr == null || arr.length == 0) return;
        if(left > right) return;
        int key = arr[left];
        int l = left;
        int r = right;
        while(l != r){
            while(arr[r] >= key && l < r) r--;
            while(arr[l] <= key && l < r) l++;
            if(l < r){
                int temp = arr[l];
                arr[l] = arr[r];
                arr[r] = temp;
            }
        }
        arr[left] = arr[l];
        arr[l] = key;
        quick(arr, left, l - 1);
        quick(arr, l+ 1, right);
    }
}

arr[left] = arr[l] arr[l] = key 基点和中间值交换

冒泡

1.冒泡排序 a、冒泡排序，是通过每一次遍历获取最大/最小值 b、将最大值/最小值放在尾部/头部

c、然后除开最大值/最小值，剩下的数据在进行遍历获取最大/最小值

d、代码实现

package com.kuang.offer;
public class bubble {
    public static void main(String[] args) {
        int[] nums = {8, 5, 3, 2, 4};
        for (int num : nums) {
            System.out.println(num);
        }
    }
    public static void bubble_(int[] arr){
        for(int i = 0; i< arr.length - 1; i++){
            for(int j = 0; j < arr.length - i - 1; i++){
                if(arr[j] > arr[j + 1]){
                    int temp = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }
}

选择排序

a、将第一个值看成最小值 b、然后和后续的比较找出最小值和下标 c、交换本次遍历的起始值和最小值 d、说明：每次遍历的时候，将前面找出的最小值，看成一个有序的列表，后面的看成无序的列 表，然后每次遍历无序列表找出最小值。

package com.kuang.offer;
public class select {
    public static void main(String[] args) {
        int[] arr = {6, 5, 4, 3, 8};
        for(int i = 0; i < arr.length; i++){
            //默认第一个是最小的
            int min = arr[i];
            //记录最小的下标
            int index = i;
            //通过与后面的数据进行比较得出，最小值下标
            for(int j = i + 1; j < arr.length; j++){
                if(min > arr[j]){
                    min = arr[j];
                    index = j;
                }
            }
            //然后将最小值与本次循环的，开始值交换
            int temp = arr[i];
            arr[i] = min;
            arr[index] = temp;     //将i前面的数据看成一个排好的队列，i后面的看成是一个无序队列，
                                   // 每次只需要找到无序的最小值，做替换
        }
        for (int i: arr) {
            System.out.println(i);
        }
    }
}

插入排序

a、默认从第二个数据开始比较。 b、如果第二个数据比第一个小，则交换。然后在用第三个数据比较，如果比前面小，则插入（狡 猾）。否则，退出循环 c、说明：默认将第一数据看成有序列表，后面无序的列表循环每一个数据，如果比前面的数据小 则插入（交换）。否则退出。

package com.kuang.offer;
public class insert {
    public static void main(String[] args) {
        int[] arr = {7, 5, 3, 2, 4};
        //外层循环，从第二个开始比较
        for(int i = 1; i < arr.length; i++){
            //内层循环，与前面拍好序的数据比较，如果后面的数据小于前面的则交换
            for(int j = i; j > 0; j--){
               if(arr[j] < arr[j - 1]){
                   int temp = arr[j - 1];
                   arr[j - 1] = arr[j];
                   arr[j] = temp;
               }else{
                   //如果不小于，说明插入完毕，退出内层循环
                   break;
               }
            }
        }
        for(int i: arr){
            System.out.println(i);
        }
    }
}

希尔排序（插入排序变种版）

a、基本上和插入排序一样的道理 b、不一样的地方在于，每次循环的步长，通过减半的方式来实现 c、说明：基本原理和插入排序类似，不一样的地方在于。通过间隔多个数据来进行插入排序。

package com.kuang.offer;
public class xshell {
    public static void main(String[] args) {
        int[] arr = {7, 5, 3, 2, 1};
        //i层循环控制步长
        for(int i = arr.length / 2; i > 0; i /= 2){
            //j控制无序端的起始位置
            for(int j = i; j < arr.length; j++){
                for(int k = j; k > 0 && k - i >= 0; k -= i){
                    if(arr[k] < arr[k - i]){
                        int temp = arr[k - i];
                        arr[k - i] = arr[k];
                        arr[k] = temp;
                    }else{
                        break;
                    }
                }
            }
        } //j, k为插入排序，不过步长为i
        for(int i : arr){
            System.out.println(i);
        }
    }
}

归并排序

package com.kuang.offer;
import java.util.Arrays;
public class MergeSort {
    public static void main(String[] args) {
        int arr[] = {7, 5, 3, 2, 4, 1, 6};
        //归并排序
        int start = 0;
        int end = arr.length - 1;
        mergeSort(arr, start, end);
        for (int i : arr){
            System.out.println(i);
        }
    }
    public static void mergeSort(int[] arr, int start, int end) {
        //判断拆分的不为最小单位
        if (end - start > 0) {
            //再一次拆分，知道拆成一个一个的数据
            mergeSort(arr, start, (start + end) / 2);
            mergeSort(arr, (start + end) / 2 + 1, end);
            //记录开始/结束位置
            int left = start;
            int right = (start + end) / 2 + 1;
            //记录每个小单位的排序结果
            int index = 0;
            int[] result = new int[end - start + 1];
            //如果查分后的两块数据，都还存在
            while (left <= (start + end) / 2 && right <= end) {
            //比较两块数据的大小，然后赋值，并且移动下标
                if (arr[left] <= arr[right]) {
                    result[index] = arr[left];
                    left++;
                } else {
                    result[index] = arr[right];
                    right++;
                }
            //移动单位记录的下标
                index++;
            }
            //当某一块数据不存在了时
            while (left <= (start + end) / 2 || right <= end) {
            //直接赋值到记录下标
                if (left <= (start + end) / 2) {
                    result[index] = arr[left];
                    left++;
                } else {
                    result[index] = arr[right];
                    right++;
                }
                index++;
            }
            //最后将新的数据赋值给原来的列表，并且是对应分块后的下标。
            for (int i = start; i <= end; i++) {
                arr[i] = result[i - start];
            }
        }
    }
}

归并排序（精简版）

package sortdemo;
import java.util.Arrays;
public class MergeSort {
    public static void main(String []args){
        int []arr = {9,8,7,6,5,4,3,2,1};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void sort(int []arr){
        int []temp = new int[arr.length];//在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
        sort(arr,0,arr.length-1,temp);
    }
    private static void sort(int[] arr,int left,int right,int []temp){
        if(left<right){
            int mid = (left+right)/2;
            sort(arr,left,mid,temp);//左边归并排序，使得左子序列有序
            sort(arr,mid+1,right,temp);//右边归并排序，使得右子序列有序
            merge(arr,left,mid,right,temp);//将两个有序子数组合并操作
        }
    }
    private static void merge(int[] arr,int left,int mid,int right,int[] temp){
        int i = left;//左序列指针
        int j = mid+1;//右序列指针
        int t = 0;//临时数组指针
        while (i<=mid && j<=right){
            if(arr[i]<=arr[j]){
                temp[t++] = arr[i++];
            }else {
                temp[t++] = arr[j++];
            }
        }
        while(i<=mid){//将左边剩余元素填充进temp中
            temp[t++] = arr[i++];
        }
        while(j<=right){//将右序列剩余元素填充进temp中
            temp[t++] = arr[j++];
        }
        t = 0;
        //将temp中的元素全部拷贝到原数组中
        while(left <= right){
            arr[left++] = temp[t++];
        }
    }
}