浅谈Java常见的排序算法

package Sort;
//插入排序
public class InsertSort {
    public static void main(String[] args) {
        int [] arr={49,38,65,97,76,13,27,49};
        sort(arr);
       print(arr);
    }

    private static void sort(int [] arr) {

        for (int i = 1; i < arr.length; i++) {
           for(int j=i;j>0;j--){
               if(arr[j]<arr[j-1]){
                  swap(arr,j,j-1);
               }
           }
        }
    }
    private static void swap(int [] arr,int i,int j){
        int temp=0;
        temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }
    private static void print(int [] arr) {
        for (int i = 0; i <arr.length ; i++) {
            System.out.print(arr[i]+" ");
        }
    }
}

package Sort;
//希尔排序是插入排序的改良
public class shellSort {
    public static void main(String[] args) {
        int [] arr={16,25,12,30,47,11,23,36,9,18,31};
        sort(arr);
        print(arr);
    }
    private static void sort(int [] arr) {
        //gap设置优化
        int h=1;
        while(h<arr.length/3){
            h=h*3+1;
        }
       for(int gap=h;gap>0;gap=(gap-1)/3) {//gap:希尔排序的间距
           for (int i = gap; i < arr.length; i++) {
               for (int j = i; j >gap-1; j-=gap) {
                   if (arr[j] < arr[j - gap]) {
                       swap(arr, j, j - gap);
                   }
               }
           }
       }
    }
    private static void swap(int [] arr,int i,int j){
        int temp=0;
        temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }
    private static void print(int [] arr) {
        for (int i = 0; i <arr.length ; i++) {
            System.out.print(arr[i]+" ");
        }
    }
}

package Sort;

import java.util.Arrays;

//快速排序
public class QuickSort {
    public static void main(String[] args) {
        int[] arr={49,38,65,97,76,13,27,49};
        sort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    private static void sort(int [] arr,int start,int end) {
       if(start<end){
           //把数组的第0个数作为标准数
           int stared=arr[start];
           //记录要排序的下标
           int low=start;
           int height=end;
           //循环找出比标准数大和比标准数小的数
           while(low<height){
               //右边数字比标准数大
               while(low<height&&stared<=arr[height]){
                   height--;
               }
               //用右边的数字替换左边的数字
               arr[low]=arr[height];
               //左边数字比标准数小
               while(low<height&&stared>=arr[low]){
                   low++;
               }
               //用左边的数字替换右边的数字
               arr[height]=arr[low];
           }
           arr[low]=stared;
           sort(arr,start,low);
           sort(arr,low+1,height);
       }

    }
    }

  堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。

package Sort;
import java.util.Arrays;



public class HeapSort {
    public static void main(String[] args) {
        int [] arr={4,6,8,5,9};
        heapSort(arr);
    }
    //编写一个堆排序的方法
    public static void heapSort(int[] arr){
        int temp=0;
        for(int i=arr.length/2-1;i>=0;i--){
            adjustHeap(arr,i,arr.length);
        }
        //将堆顶元素与末尾元素进行交换，此时末尾就为最大值，将最大值全放在数组最后
        //重新调整结构，使其满足堆定义，继续交换堆顶元素与当前末尾元素，反复执行调整交换步骤，使整个序列达到有序
        for(int j=arr.length-1;j>0;j--) {
            //交换
            temp = arr[j];
            arr[j] = arr[0];
            arr[0] = temp;
            adjustHeap(arr, 0, j);
        }
        System.out.println("数组"+Arrays.toString(arr));

    }
    //将数组调整为一个大顶堆
    
    public static void adjustHeap(int[]arr,int i,int length){
         int temp=arr[i];//先取出当前元素的值，保存在临时变量中
        //开始调整
        //k=i*2+1;k是i节点的左子节点
        for(int k=i*2+1;k<length;k=k*2+1){
              if(k+1<length&&arr[k]<arr[k+1]){//说明左子节点的值小于右子节点的值
                 k++;//k指向右子节点
              }
              if(arr[k]>temp){//如果子节点大于父节点
                  arr[i]=arr[k];//把较大的值赋给当前节点
                  i=k;//!!!i指向k，继续循环比较
              }else{
                  break;
              }
        }
        //当for循环结束后，已经将以i为父结点的最大值放在了堆顶上（局部）
          arr[i]=temp;//将temp的值放在调整后的位置
    }
}

package Sort;
//归并排序
public class MergeSort {
    public static void main(String[] args) {
        int [] arr={4,5,7,8,1,2,3,6};
        sort(arr);
        print(arr);
    }

    private static void sort(int [] arr) {
        int mid=arr.length/2;
        int[]temp=new int[arr.length];
        int i=0;//标记左边数组
        int j=mid+1;//标记右边数组起始点
        int k=0;
        while(i<=mid&&j<arr.length){
            if(arr[i]<=arr[j]){
               temp[k]=arr[i];
               i++;
               k++;
            }else{
                temp[k]=arr[j];
                j++;
                k++;
            }
        }
        while(i<=mid){temp[k++]=arr[i++];}//将左边剩余的，复制到数组
        while(j<arr.length){temp[k++]=arr[j++];}//将右边剩余的，复制到数组
    }


    private static void print(int [] arr) {
        for (int i = 0; i <arr.length ; i++) {
            System.out.print(arr[i]+" ");
        }
    }
}