十大经典排序算法 （一）

//交换数组中两元素位置
    public static void swap(int[] arr,int i,int j) {
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }

swap在下面排序算法中会用到，主要是省事。

冒泡排序

//冒泡排序
    public static void bubble(int[] nums) {
        int length=nums.length;
        boolean flag;
        for(int i=0;i<length;i++) {//排序的次数
            flag=true;
            for(int j=0;j<length-1-i;j++) {//参与排序的数据个数
                if(nums[j]>nums[j+1]){
                    swap(nums,j,j+1);
                    flag=false;
                }
            }
            if(flag){
                break;
            }
        }
    }

flag在一定程度上起到了优化的作用，如果排序一个有序数组【1,2,3,4,5,6】，这里只需要循环一次就退出排序；如果在一次排序中，没有发生值交换，就意味着这时数组已经有序。

选择排序

//选择排序
    public static  void sort(int[] nums) {
        for(int i=0;i<nums.length-1;i++) {
            int minIndex=i;
            for(int j=i+1;j<nums.length;j++) {
                if(nums[j]<nums[minIndex]){
                    minIndex=j;
                }
            }
            swap(nums,i,minIndex);
        }
    }

插入排序

//插入排序
   public static void selectSort(int[] nums){
        for(int i=1;i<nums.length;i++) {
            int temp=nums[i];
            int j=i;
            while(j>0&&temp<nums[j-1]){
                nums[j]=nums[j-1];
                j--;
            }
            if(i!=j){
                nums[j]=temp;
            }
        }
   }

希尔排序

//插入排序的改进版---希尔排序
    public static  void shell(int[] nums) {
        int step=nums.length/2;
        int temp;
        while(step>0) {
            for(int i=step;i<nums.length;i++){
                temp=nums[i];
                int j=i;
                while(j>=step&&nums[j-step]>temp) {
                    nums[j]=nums[j-step];
                    j-=step;
                }
                nums[j]=temp;
            }
            step=step/2;
        }
    }

归并排序

//归并排序，先分后合, mergeSort分 ，merge合并
    public static void mergeSort(int[] nums,int left,int right){
        if(left==right) return ;
        int mid=left+(right-left)/2;
        mergeSort(nums,left,mid);
        mergeSort(nums,mid+1,right);
        merge(nums,left,mid,right);
    }
    private static void merge(int[] nums, int left, int mid, int right) {
        int[] helper=new int[right-left+1];//辅助数组
        int i=0;
        int l=left;
        int r=mid+1;
        while(l<=mid&&r<=right) {
            helper[i++] = nums[l]<nums[r]?nums[l++]:nums[r++];
        }
        while(l<=mid) {
            helper[i++] = nums[l++];
        }
        while(r<=right) {
            helper[i++] = nums[r++];
        }
        for(int j=0;j<helper.length;j++) {
            nums[left+j]=helper[j];
        }
    }

最后，使用归并排序为数组排序，验证：

public static void main(String[] args) {
        int[] nums={5,44,15,16,26,27,3,49,4,19,70,28};
        mergeSort(nums,0,nums.length-1);
        for(int num:nums){
            System.out.print(num+" ");
        }
    }