算法解读-排序

冒泡排序

什么是冒泡排序

• 先通过元素进行比较找出最大数，如果是升序就放在最后，降序就放在首位，
• 每次遍历都确定一个数的位置

算法思路

1. 从后往前比较相邻的元素，如果后一个比前一个小，就互换位置
2. 针对所有的元素重复以上的步骤。

算法模型

  public void sort(int[] nums) {
        for(int i=0;i< nums.length;i++){
            boolean flag = true;
            for(int j= nums.length-1;j>i;j--){
                if(num[j]<nums[j-1]){
                    int temp = nums[j-1];
                    nums[j-1] = nums[j];
                    nums[j] = temp;
                    flag = false;
                }
            }
            if(flag){
                break;
            }
        }
    }

插入排序

什么是插入排序

对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

算法思路

1. 将第一个元素看做一个有序序列，把其他元素当成是未排序序列
2. 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置

算法模型

    public void 插入Sort() {
        int[] num = new int[]{2,3,5,3,2,1,8,9,14,6,8,4};
        int j = 0;
        for(int i=0;i<num.length;i++){
            int temp = num[I];
            // 将小于当前位置的数后移
            for(j=i;j>0&&temp>num[j-1];j--){
                num[j] = num[j-1];
            }
            num[j] = temp;
        }
        System.out.println(Arrays.toString(num));
    }

选择排序

算法思路

1. 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
2. 从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾
3. 重复第二步，直到所有元素均排序完毕。

算法模型

    public void 选择Sort(){
        int[] num = new int[]{2,3,5,3,2,1,8,9,14,6,8,4};
        for(int i=0;i<num.length-1;i++){
            int minIndex = i;
            for(int j=i;j<num.length;j++){
                if(num[j]<num[minIndex]){
                    minIndex = j;
                }
            }
            if(i!=minIndex){
                int temp = num[minIndex];
                num[minIndex] = num[i];
                num[i] = temp;
            }
        }
        System.out.println(Arrays.toString(num));
    }

快速排序

算法思路

1. 选基准
2. 分区
3. 对分区迭代进行1，2步骤

算法模型

    public void 快速Sort(){
        int[] num = new int[]{2,3,5,3,2,1,8,9,14,6,8,4};
        quickSort(num,0,num.length-1);
        System.out.println(Arrays.toString(num));
    }
    private void quickSort(int[] num,int left,int right){
        //递归结束条件左指针大于等于右指针
        if(left<right) {
            //分区
            int partitionIndex = partition(num, left, right);
            //递归左分区
            quickSort(num, left, partitionIndex-1);
            //递归右分区
            quickSort(num, partitionIndex+1, right);
        }

    }
    private int partition(int[] num,int left,int right){
        int pivot = left;
        int index = pivot+1;
        for(int i = index;i<=right;i++){
            if(num[i]<num[pivot]){
                swap(num,i,index);
                index++;
            }
        }
        swap(num,pivot,index-1);
        return index-1;
    }

归并排序

算法思路

1. 递归将数组拆成左右两个数组
2. 递归返回时，将左右两个数组合并成有序数组

算法模版

public void 归并Sort(){
        int[] num = new int[]{2,3,5,3,2,1,8,9,14,6,8,4};
        num = mergeSort(num);
        System.out.println(Arrays.toString(num));
    }

    private int[] mergeSort(int[] num){
        if(num.length<2){
            return num;
        }
        int[] left = Arrays.copyOfRange(num,0,num.length/2);
        int[] right = Arrays.copyOfRange(num,num.length/2,num.length);
        return merge(mergeSort(left),mergeSort(right));
    }

    private int[] merge(int[] left,int[] right){
        int i = 0;
        int j = 0;
        int[] result = new int[left.length+right.length];
        int cur;
        while(i<left.length||j<right.length){
            if(i==left.length){
                cur = right[j++];
            }else if(j==right.length){
                cur = left[i++];
            }else if(left[i]<=right[j]){
                cur = left[i++];
            }else{
                cur = right[j++];
            }
            result[i+j-1] = cur;
        }
        return result;
    }