[数据结构与算法]2021-8-5 复习排序算法

package _01_Sorted;




import org.junit.Test;

import java.util.*;

/**
 * 排序算法：
 * ① 选择排序，不断的选择剩余元素中最小的，和外层循环相应的遍历位置交换。
 *
 * ② 插入排序，当前索引左边都是有序的，当数组的索引达到数组最右端时，排序结束
 *           像打牌的时候一样，把新的牌插入到已经有序的牌中的适当位置
 *
 * ③ 希尔排序，对于大规模的数组，插入排序只能一格一格的从一段移到另一端
 *          希尔排序改变插入排序的增量，让步子迈的大一些。大数组迈大步子进行插入排序、
 *          在不断根据数组越来越有序，减小步子，到 1的时候就剩插入排序
 *
 * ④ 归并排序，先利用二叉树的原理，将数组进行拆分。拆到只剩下一个元素时，进行有序的合并
 *          就是二叉树的框架：
 *          二分
 *          拆左边
 *          拆右边
 *          合并（另外提取出合并的方法）
 *
 * ⑤ 冒泡排序，双重循环，外循环遍历所有元素，内循环操作交换位置，把大元素跑到最后去
 *
 * ⑥ 快速排序，选取一个数,这个数可以选取第一个数，以这个数作为基准值。双指针i j
 *          i 从前往后遍历，j从后往前遍历，分别选取到比基准大、小的值，进行交换。
 *          当i==j 时，说明已经到中间了，这个时候再将基准值与i==j 这个位置的元素进行交换。
 *          此时相当于，将数组分成两部分，左边都比数小 + 基准值 + 右边都比数大
 *          递归。递归的结束的条件是里面只有一个元素。
 *
 *
 * 算法之间的比较
 * ① 选择排序：没有利用输入状态，运行时间和输入无关、数据移 N 最少
 * ② 插入排序：对于输入的情况，能立即感知输入的有序性，所以对于部分有序的数组效率高
 * ③ 希尔排序：插入排序的进阶版，数组越大效率越明显，权衡了数组规模和有效性
 *
 *
 * @author sommer1111
 * @date 2021/5/16 13:54
 */
public class all {
    public void select(int[] arr){
//        1.外层循环遍历所有元素
        for (int i = 0; i < arr.length; i++) {
            //2.固定当前遍历位置为待交换的元素
            int min = arr[i];
            int minIndex = i;
//            3.内层循环遍历找到未排序部分最小的元素
            for (int j = i+1; j <arr.length ; j++) {
                if(min>arr[j]){
                    min = arr[j];
                    minIndex = j;
                }
            }
//            交换位置
            if(minIndex!=i){
                arr[minIndex] = arr[i];
                arr[i] = min;
            }
        }
    }

    public void insert(int[] arr){
//        1.外层循环遍历所有元素
        for (int i = 0; i < arr.length; i++) {
//            2.当前值为待插入的元素，需要把元素插入到已经排序的部分
            int insertVal = arr[i];
            int j;
            for (j = i; j >0 && insertVal<arr[j-1] ; j++) {
                arr[j] = arr[j-1];//全部人往后挪
            }
//            3.找到位置坐下
            arr[j] = insertVal;
        }
    }

    public void shell(int[] arr){
//        1.外层迈开步子
        for (int step = arr.length/2; step >=1 ; step/=2) {
//            2.每组步子遍历所有元素
            for (int i = step; i <arr.length ; i++) {
//                3.遍历的元素待插入
                int insertVal = arr[i];
                int j;
                for (j = i; j >=step && insertVal < arr[j-step] ; j-=step) {
                    arr[j] = arr[j-step];
                }
                arr[j] = insertVal;
            }
        }
    }

    public void bubble(int[] arr){
        boolean flag = false;
        for (int i = 0; i < arr.length-2; i++) {
            for (int j = 0; j < arr.length-i-1; j++) {
                if(arr[j]>arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    flag = true;
                }
            }
            if(!flag){
                break;
            }else{
                flag = false;
            }
        }
    }

    public void quick(int[] arr,int left,int right){
        if(left<right){
            int base = left + (int)(Math.random()*(right-left));
            swap(arr,base,left);
            int i = left,j = right;
            while(i<j){
                while(i<j && arr[j]>arr[left]) j--;
                while(i<j && arr[i]>arr[left]) i++;
                swap(arr,i,j);
            }
            swap(arr,left,j);
            quick(arr,left,j-1);
            quick(arr,j+1,right);
        }

    }
    public void swap(int[]arr, int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    @Test
    public void test(){
        int[] arr = {2,5,1,8,0,3,7};
        quick(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
}