排序算法 Java实现代码

JAVA下面的 堆排序  冒泡排序法 选择排序法 快速排序法 插入排序法 折半插入排序法 希尔排序法 归并排序法

/**   *   * @param <T>   */  public class Sort<T extends Comparable<T>> {   //交换索引i和索引j的值   private void swap(T[] data,int i,int j){    T tmp;    tmp = data[i];    data[i] = data[j];    data[j] = tmp;   }      //-----堆排序 时间复杂度O(nlogn)-----   public void heapSort(T[] data) {    int arrayLength = data.length;    // 循环建堆    for (int i = 0; i < arrayLength - 1; i++) {     // 建堆     builMaxdHeap(data, arrayLength - 1 - i);     // 交换堆顶和最后一个元素     swap(data, 0, arrayLength - 1 - i);     //System.out.println(java.util.Arrays.toString(data));    }   }     // 对data数组从0到lastIndex建大顶堆   private void builMaxdHeap(T[] data, int lastIndex) {    // 从lastIndex处节点（最后一个节点）的父节点开始    for (int i = (lastIndex - 1) / 2; i >= 0; i--) {     // k保存当前正在判断的节点     int k = i;     // 如果当前k节点的子节点存在     while (k * 2 + 1 <= lastIndex) {      // k节点的左子节点的索引      int biggerIndex = 2 * k + 1;      // 如果biggerIndex小于lastIndex，即biggerIndex + 1      // 代表的k节点的右子节点存在      if (biggerIndex < lastIndex) {       // 如果右子节点的值较大       if (data[biggerIndex].compareTo(data[biggerIndex + 1]) < 0) {        // biggerIndex总是记录较大子节点的索引        biggerIndex++;       }      }      // 如果k节点的值小于其较大子节点的值      if (data[k].compareTo(data[biggerIndex]) < 0) {       // 交换它们       swap(data, k, biggerIndex);       // 将biggerIndex赋给k，开始while循环的下一次循环，       // 重新保证k节点的值大于其左、右子节点的值。       k = biggerIndex;      } else {       break;      }     }    }   }      //-----冒泡排序法 时间复杂度O(n^2)-----   public void bubbleSort(T[] data){       int i,j;    for(i=0;i<data.length-1;i++){     for(j=0;j<data.length-i-1;j++){      //排序之前[9, -16*, 21, 23, -30, -49, 21*, 30, 30]      //排序之后[-49, -30, -16*, 9, 21, 21*, 23, 30, 30]      if(data[j].compareTo(data[j+1]) > 0){       swap(data,j+1,j);      }     }    }   }      //-----选择排序法 时间复杂度O(n^2)-----   public void selectSort(T[] data){    int i,j;         for(i=0;i<data.length-1;i++){     for(j=i+1;j<data.length;j++){      //排序之前[9, -16*, 21, 23, -30, -49, 21*, 30, 30]      //排序之后[-49, -30, -16*, 9, 21, 21*, 23, 30, 30]      if (data[i].compareTo(data[j]) > 0){       swap(data,i,j);      }     }    }   }      //-----快速排序法  时间复杂度为O(log2n)-----   public void quickSort(T[] data){    subQuickSort(data,0,data.length-1);   }      private void subQuickSort(T[] data,int start,int end){    if( start < end ){     //以第一个元素作为分界值     T base = data[start];     //i从左边开始搜索大于分界值元素的索引     int i = start;     //j从右边开始搜索小于分界值元素的索引     int j = end + 1;     //排序之前[9, -16*, 21, 23, -30, -49, 21*, 30, 30]     //排序之后[-30, -16*, -49, 9, 21*, 21, 23, 30, 30]     while(true){      //左边跳过比base小的元素      while(i < end && data[++i].compareTo(base) <= 0);      //右边跳过比base大的元素      while(j > start && data[--j].compareTo(base) >= 0);            if(j > i){       swap(data,i,j);      }else{       break;      }     }     //将分界值还原     swap(data,start,j);          //递归左边序列     subQuickSort(data,start,j-1);     //递归右边序列     subQuickSort(data,j+1,end);     // System.out.println(  Arrays.toString(data) );    }   }      //-----插入排序法 时间复杂度O(n^2)-----   public void insertSort(T[] data){    int arrayLength = data.length;        for(int i=1;i<arrayLength;i++){     //当整体后移时保证data[i]的值不会丢失     T tmp = data[i];     //i索引处的值已经比前面所有值都大,表明已经有序,无需插入     //i-1处索引之前的数值已经有序,i-1处索引处元素的值也是最大值     if(data[i].compareTo(data[i-1]) < 0){      int j = i-1;      //整体后移一个      while(j>=0 && data[j].compareTo(tmp) > 0){       data[j+1] = data[j];       j--;      }     data[j+1] = tmp;     // System.out.println(  Arrays.toString(data) );     }    }   }      //-----折半插入排序法 时间复杂度-----   public void binaryInsertSort(T[] data) {    int arrayLength = data.length;      for (int i = 1; i < arrayLength; i++) {     if (data[i - 1].compareTo(data[i]) > 0) {      // 缓存i处的元素值      T tmp = data[i];        // 记录搜索范围的左边界      int low = 0;      // 记录搜索范围的右边界      int high = i - 1;        while (high >= low) {       // 记录中间位置       int mid = (high + low) / 2;       // 比较中间位置数据和i处数据大小，以缩小搜索范围         if (tmp.compareTo(data[mid]) > 0) {        low = mid + 1;       } else {        high = mid - 1;       }      }      // 将low~i处数据整体向后移动1位      for (int j = i; j > low; j--) {       data[j] = data[j - 1];      }      data[low] = tmp;       }     //System.out.println(  Arrays.toString(data) );    }   }      //-----希尔排序法 时间复杂度O(nlogn)O(n^2)具体看h的值-----   public void shellSort(T[] data){    int arrayLength = data.length;    //h保存可变增量        int h = 1;    while(h<=arrayLength/3){     h = h * 3 + 1;     //System.out.println("h="+h);    }        while(h > 0){     //System.out.println(Arrays.toString( data )+"h="+h);          for(int i=h;i<arrayLength;i++){      //当整体后移时,保证data[i]的值不丢失      T tmp = data[i];      //i索引处的值已经比前面所有的值大      //(i-1索引之前的值已经有序的,i-1索引处元素的值就是最大值)      if(data[i].compareTo(data[i-h]) < 0){       int j = i-h;       //整体后移一格       while(j>=0 && data[j].compareTo(tmp) > 0){        data[j+h] = data[j];        j-=h;       }              //最后将tmp值插入合适的位置       data[j+h] = tmp;      }     }     h = (h-1)/3;    }       }      //-----归并排序法 时间复杂度为O(nlog2n)-----   public void mergeSort(T[] data){    subMergeSort(data,0,data.length-1);   }      private void subMergeSort(T[] data,int left,int right){    if(right > left){     //找出中间索引     //System.out.println(  Arrays.toString(data) );     int center = (left + right)/2;     //对左边数组进行递归     subMergeSort(data,left,center);     //对右边数组进行递归     subMergeSort(data,center+1,right);     //合并     merge(data,left,center,right);    }   }      @SuppressWarnings("unchecked")   private void merge(T[] data, int left, int center, int right) {    Object[] tmpArr = new Object[data.length];    int mid = center + 1;    // third记录中间处索引    int third = left;    int tmp = left;      while (left <= center && mid <= right) {     // 从两个数组中取出最小的放入中间数组     if (data[left].compareTo(data[mid]) <= 0) {      tmpArr[third++] = data[left++];     } else {      tmpArr[third++] = data[mid++];     }    }        // 剩余部分依次放入中间数组    while (mid <= right) {     tmpArr[third++] = data[mid++];    }    while (left <= center) {     tmpArr[third++] = data[left++];    }        // 将中间数组的内容复制拷回原数组    // (原left~right范围内德内容被复制回原数组)    while (tmp <= right) {     data[tmp] = (T) tmpArr[tmp++];    }     }        /*public static void main(String[] args){    DataWarp[] dataWarp = {     new DataWarp(9,""),     new DataWarp(-16,"*"),     new DataWarp(21,""),     new DataWarp(23,""),     new DataWarp(-30,""),     new DataWarp(-49,""),     new DataWarp(21,"*"),     new DataWarp(30,""),     new DataWarp(56,""),     new DataWarp(40,""),     new DataWarp(430,""),     new DataWarp(-67,""),     new DataWarp(56,""),     new DataWarp(-87,""),     new DataWarp(26,""),     new DataWarp(92,""),     new DataWarp(30,"")    };        DataWarp[] dataWarp2 = {      new DataWarp(9,""),      new DataWarp(-16,"*"),      new DataWarp(21,""),      new DataWarp(23,""),      new DataWarp(-30,""),      new DataWarp(-49,""),      new DataWarp(21,"*"),      new DataWarp(30,""),      new DataWarp(56,""),      new DataWarp(40,""),      new DataWarp(430,""),      new DataWarp(-67,""),      new DataWarp(56,""),      new DataWarp(-87,""),      new DataWarp(26,""),      new DataWarp(92,""),      new DataWarp(30,"")     };           System.out.println( "排序之前" + Arrays.toString(dataWarp) );              Sort<DataWarp> sort = new Sort<DataWarp>();       sort.mergeSort(dataWarp);       sort.shellSort(dataWarp2);              System.out.println( "排序之后" + Arrays.toString(dataWarp) );       System.out.println( "排序之后" + Arrays.toString(dataWarp2) );     }*/  }