java实现各种排序算法

插入排序

public static void insertSort(int[] arr){
        for(int i = 0 ; i < arr.length ; i ++){
            int tmp = arr[i];
            int j = 0;
            for(j = i - 1; (j > -1) && (tmp < arr[j]) ; j --){
                arr[j + 1] = arr[j];
            }
            arr[j + 1] = tmp;
        }

起泡排序

    public static void bubbleSort(int[] arr){
        int length = arr.length - 1;
        int tmp = 0;
        boolean flag = false;
        while(length != 0){
            flag = false;
            for(int i = 0; i < length ; i ++){
                if(arr[i] > arr[i+1]){
                    tmp = arr[i];
                    arr[i] = arr[i+1];
                    arr[i+1] = tmp;
                    flag = true;
                }
            }
            System.out.println("第"+(arr.length-length)+"趟："+Arrays.toString(arr));
            length--;

            if(flag == false){
                //这个过程中不曾出现数据交换的动作，说明数组已经是有序的了
                break;
            }
        }
    }

选择排序

（1）：将序列分成有序区和无序区，初始时有序区为空，无序区包括全部元素
（2）：每次从无序区中选择最小的元素将其与无序区第一个元素进行交换
（3）：重复（2）,直到无序区没有元素

    public static void selectSort(int[] arr){
        int tmp = 0; 
        int index = 0;
        for(int i = 0 ; i < arr.length ; i ++){
            index = i;
            //查找[i...length]中的最小值
            for(int j = i + 1; j < arr.length; j ++){
                if(arr[index] > arr[j]){
                    index = j;
                }
            }
            //最小元素不是本身
            if(index != i){
                tmp = arr[index];
                arr[index] = arr[i];
                arr[i] = tmp;
            }
        }
    }

##归并排序

    public static void mergeSort(int[] list){
        if(list.length > 1){
            //合并左半部分
            int[] leftHalf = new int[list.length/2];
            System.arraycopy(list,0,leftHalf,0,list.length/2);
            mergeSort(leftHalf);

            //合并右半部分
            int rightHalfLength = list.length - list.length / 2;
            int[] rightHalf = new int[rightHalfLength];
            System.arraycopy(list,list.length / 2,rightHalf,0,rightHalfLength);
            mergeSort(rightHalf);

            int[] temp = merge(leftHalf,rightHalf);
            System.arraycopy(temp,0,list,0,temp.length);
        }
    }
    public static int[] merge(int[] list1,int[] list2){
        int[] temp = new int[list1.length + list2.length];
        int pos1 = 0;//list1游标
        int pos2 = 0;//list2游标
        int pos3 = 0;//temp游标

        while(pos1 < list1.length && pos2 < list2.length){
            if(list1[pos1] < list2[pos2]){
                temp[pos3++] = list1[pos1++];
            }else if(list1[pos1] > list2[pos2]){
                temp[pos3++] = list2[pos2++];
            }else{
                temp[pos3++] = list2[pos2++];
                temp[pos3++] = list1[pos1++];
            }
        }
        while(pos1 < list1.length){
            temp[pos3++] = list1[pos1++];
        }
        while(pos2 < list2.length){
            temp[pos3++] = list2[pos2++];
        }
        return temp;
    }

快速排序

    public static void quickSort(int[] arr,int low,int high){
        if(high > low){
            int part = partition(arr,low,high);
            //System.out.println("part="+part);
            quickSort(arr,low,part - 1);
            quickSort(arr,part+1,high);
        }
    }
    //找寻分界点
    public static int partition(int[] arr,int low , int high){
        int first = low;
        int pivot = arr[low];
        low++;
        while(high > low){
            //从左边找比pivot大的数
            while(low <= high && arr[low] <= pivot ){
                low++;
            }
            //从右边找比pivot小或等于的数
            while(high >= low && arr[high] > pivot ){
                high--;
            }
            //交换
            if(high > low){
                int temp = arr[high];
                arr[high] = arr[low];
                arr[low] = temp;
            }
        }
        //此时high = low - 1;
        //且high之前的元素都小于等于pivot,low之后的元素都大于pivot
        //System.out.println("low="+low+";high="+high+"："+Arrays.toString(arr));
        if(high > first){
            int temp = arr[high];
            arr[high] = arr[first];
            arr[first] = temp;
            //System.out.println("part="+high+"："+Arrays.toString(arr));
            return high;
        }else{
            //System.out.println("part="+high+"："+Arrays.toString(arr));
            return first;
        }
    }

堆排序

堆是一棵具有以下属性的二叉树
    1、一棵完全二叉树
    2、每个节点大于（小于）或等于它的任意一个孩子
    分类：大顶堆，小顶堆

    public static void heapSort(int arr[]){
        //初始化堆
        initHeap(arr);
        //System.out.println("初始化堆：" + Arrays.toString(arr));
        //end表示堆的结束位置
        int end = arr.length - 1;
        while(end > 0){
            //删除堆顶元素
            int temp = arr[0];
            arr[0] = arr[end];
            arr[end] = temp;
            end--;
            if(end > 0){
                //调整堆
                adjustHeap(arr,end);
            }
        }
    }
    public static void initHeap(int[] arr){
        //从0计数，则位置i的节点，左孩子在位置2i+1处，右孩子在位置2i+2处，而父节点在(i-1)/2处
        for(int i = 1 ; i < arr.length ; i ++){
            int current = i;
            while(current > 0){
                int parent = (current - 1) / 2;
                //孩子节点大于父节点，则交换位置
                if(arr[current] > arr[parent]){
                    int temp = arr[current];
                    arr[current] = arr[parent];
                    arr[parent] = temp;
                    //向上调整，跟新current
                    current = parent;
                }else{
                    break;
                }
            }
        }
    }
    public static void adjustHeap(int[] arr,int end){
        //删除堆顶元素后，调整堆顶的位置
        //需要知道的是，由于删除堆顶只是调整了堆顶的元素值，
        //因此除去堆顶之后，左右都是符合堆的树，
        //如此将堆顶元素向下调整的时候，如果检测到堆顶元素符合堆的定义时，
        //而由于它的左右子树始终是符合堆的定义，因此调整过程可以结束
        int current = 0;
        while(current < end){   
            int left = current * 2 + 1;
            int right = current * 2 + 2;
            if(left <= end && right <= end){
                //左右节点都存在
                if(!(arr[current] >= arr[left] && arr[current] >= arr[right])){
                    //需要进行调整堆顶
                    int index = left;
                    if(arr[left] < arr[right]){
                        //左节点小于右节点
                        index = right;
                    }
                    int temp = arr[current];
                    arr[current] = arr[index];
                    arr[index] = temp;
                    current = index;
                }else{
                    //此时已经是堆了，无需继续向下调整
                    break;
                }
            }else if(left <= end && right > end){
                //左节点存在但右节点不存在  
                if(arr[current] < arr[left]){
                    int temp = arr[current];
                    arr[current] = arr[left];
                    arr[left] = temp;
                    current = left;
                }else{
                    //此时已经是堆了，无需继续向下调整
                    break;
                }
            }else{
                //左右节点都不存在,已经调整到底了
                break;
            }
        }
    }