排序算法 第一篇

1 归并排序

采用递归思想
将数组采用递归思想分为两部分,两部分再细分

    public static void merge(int[] arr,int low,int high){
        int middle =(high+low)/2;
        if(low<high){
//            处理左边
            merge(arr,low,middle);
//            处理右边
            merge(arr,middle+1,high);
//            归并
            mergeSort(arr,low,middle,high);
        }

    }

    private static void mergeSort(int[] arr,int low,int middle,int high) {

        //用于存储归并后的临时数组
        int[] temp=new int[high-low+1];
//        记录第一个数组中需要遍历的下标
        int i=low;
//        记录第二个数组中需要遍历的下标
        int j=middle+1;
//        用于记录在临时数组中存放的下标
        int index=0;
//        遍历两个数组,取出小的数字,放入临时数组中
        while (i<=middle&&j<=high){
            if(arr[i]<=arr[j]){
//                把小的数据放入临时数组中
                temp[index]=arr[i];
//                让下标向后移一位
                i++;
            }else {
                temp[index]=arr[j];
                j++;
            }
            index++;
        }
        while (j<=high){
            temp[index]=arr[j];
            j++;
            index++;
        }
        while (i<=middle){
            temp[index]=arr[i];
            i++;
            index++;
        }
//        临时数组中数据重新存入原数组
        for (int k = 0; k < temp.length; k++) {
            arr[k+low]=temp[low];
        }
    }

2 选择排序

每次遍历取出最小的,然后排好的最小的前一组去和后面进行比较拿出最小的

//    选择排序
    private static void selectSort(int[] arr) {
//        遍历所有的数
        for(int i=0;i<arr.length;i++){
            int minIndex=i;
//            把当前遍历的数和后面所有的数进行比较,记录最小数的下表
            for (int j = i; j < arr.length; j++) {
                if (arr[minIndex] > arr[j]) {
//                    记录下最小数的下标
                    minIndex=j;
                }
            }
//            如果最小数和当前遍历数下标不一致,说明找到了更小的数
            if(i!=minIndex){
                int temp=arr[i];
                arr[i]=arr[minIndex];
                arr[minIndex]=temp;
            }
        }
    }