java 排序总结

排序算法的比较

## 排序准备

 /**
    * 数字交换
    *
    * @param nums
    * @param i
    * @param j
    */
   public  void swapNums(T\[\] nums,int i,int j){
        T temp = nums\[i\];
        nums\[i\]=nums\[j\];
        nums\[j\] = temp;
   }

   /**
    * 大小比较
    *
    */
   public  boolean lessNums(T a ,T b){
       return a.compareTo(b)<0;
   }

   /**
    * 大小比较
    */
   public boolean lessOrEqualNums(T a, T b) {
       return a.compareTo(b) <= 0;
   }

选择排序

选择出数组中的最小元素，将它与数组的第一个元素交换位置。再从剩下的元素中选择出最小的元素，将它与数组的第二个元素交换位置,不断执行这样的操作

 public void selectSort(T[] nums) {
        int n = nums.length;
        for (int i=0;i<n;i++){
             int min = i;
             for(int j=i+1;j<n;j++){
                 if(lessNums(nums[j] , nums[min])){
                    min = j;
                 }
             }
             swapNums(nums,i,min);
        }
    }

冒泡排序

从左到右不断交换相邻逆序的元素，在一轮的循环之后，可以让未排序的最大元素上浮到右侧。 在一轮循环中，如果没有发生交换，就说明数组已经是有序的，此时可以直接退出。

public void ebullitionSort(T[] nums) {
       int n = nums.length;
       boolean isFinish = false;
       for(int i = n-1;i>0 && !isFinish;i--){
           isFinish = true;

           for(int j=0;j<i;j++){
               if(less(nums[j+1],nums[j])){
                   swapNums(nums,j+1,j);
                   isFinish = false;
               }
           }

       }

   }

插入排序

每次都将当前元素插入到左侧已经排序的数组中，使得插入之后左侧数组依然有序

public void insertSort(T[] nums) {
        int n = nums.length;
        for(int i=1;i<n;i++){
            for(int j=i;j<n;j++){
                if(lessNums(nums[j],nums[j-1])){
                   swapNums(nums,j,j-1);
                }
            }
        }

    }

快速排序

快速排序通过一个切分元素将数组分为两个子数组，左子数组小于等于切分元素，右子数组大于等于切分元素，将这两个子数组排序也就将整个数组排序了

public void qucikSort(T[] nums, int start, int end) {
       int i = start;
       int j = end;
       if(i>j){
           return ;
       }

       T temp =  nums[start];

       while (i<j){
           while(lessOrEqualNums(temp,nums[j]) && i<j){
               j--;
           }

           while(lessOrEqualNums(nums[i],temp) && i<j){
               i++;
           }

           if(i<j){
               swapNums(nums,i,j);
           }
       }
       swapNums(nums,start,j);

       qucikSort(nums,start,j-1);
       qucikSort(nums,j+1,end);
   }