java实现的各种排序算法代码示例

发布时间：2020-05-23 12:52:47 所属栏目：Java 来源：互联网

导读：折半插入排序折半插入排序是对直接插入排序的简单改进。此处介绍的折半插入，其实就是通过不断地折半来快速确定第i个元素的

折半插入排序

折半插入排序是对直接插入排序的简单改进。此处介绍的折半插入，其实就是通过不断地折半来快速确定第i个元素的
插入位置，这实际上是一种查找算法：折半查找。Java的Arrays类里的binarySearch()方法，就是折半查找的实现，用
于从指定数组中查找指定元素，前提是该数组已经处于有序状态。与直接插入排序的效果相同，只是更快了一些，因
为折半插入排序可以更快地确定第i个元素的插入位置

代码：

package interview; 
/** 
 * @author Administrator 
 * 折半插入排序 
 */ 
public class BinaryInsertSort { 
  public static void binaryInsertSort(DataWrap[] data) { 
    System.out.println("开始排序"); 
    int arrayLength = data.length; 
    for (int i = 1; i < arrayLength; i++) { 
      DataWrap temp = data[i]; 
      int low = 0; 
      int high = i - 1; 
      while (low <= high) { 
        int mid = (low + high) / 2; 
        if (temp.compareTo(data[mid]) > 0) { 
          low = mid + 1; 
        } else { 
          high = mid - 1; 
        } 
      } 
      for (int j = i; j > low; j--) { 
        data[j] = data[j - 1]; 
      } 
      data[low] = temp; 
      System.out.println(java.util.Arrays.toString(data)); 
    } 
  } 
  public static void main(String[] args) { 
    DataWrap[] data = { new DataWrap(9,""),new DataWrap(-16,new DataWrap(21,"*"),new DataWrap(23,new DataWrap(-30,new DataWrap(-49,new DataWrap(30,"")}; 
    System.out.println("排序之前：n" + java.util.Arrays.toString(data)); 
    binaryInsertSort(data); 
    System.out.println("排序之后：n" + java.util.Arrays.toString(data)); 
  } 
}

结果：

排序之前：
[9,-16,21*,23,-30,-49,21,30*,30]
开始排序
[-16,9,30]
[-16,30]
[-30,30]
[-49,30,30*]
排序之后：
[-49,30*]

冒泡排序

代码：

package interview; 
/** 
 * @author Administrator 
 * 冒泡排序 
 */ 
public class BubbleSort { 
  public static void bubbleSort(DataWrap[] data) { 
    System.out.println("开始排序"); 
    int arrayLength = data.length; 
    for (int i = 0; i < arrayLength - 1; i++) { 
      boolean flag = false; 
      for (int j = 0; j < arrayLength - 1 - i; j++) { 
        if (data[j].compareTo(data[j + 1]) > 0) { 
          DataWrap temp = data[j + 1]; 
          data[j + 1] = data[j]; 
          data[j] = temp; 
          flag = true; 
        } 
      } 
      System.out.println(java.util.Arrays.toString(data)); 
      if (!flag) 
        break; 
    } 
  } 
  public static void main(String[] args) { 
    DataWrap[] data = { new DataWrap(9,"")}; 
    System.out.println("排序之前：n" + java.util.Arrays.toString(data)); 
    bubbleSort(data); 
    System.out.println("排序之后：n" + java.util.Arrays.toString(data)); 
  } 
}

运行结果：

排序之前：
[9,30]
排序之后：
[-49,30]

桶式排序

算法的时间效率：时间效率极高，只需经过两轮遍历即可算法的空间效率：空间开销较大，需要两个数组来完成，算
法的稳定性：稳定
代码：

package interview; 
import java.util.Arrays; 
/** 
 * @author Administrator 
 * 桶式排序 
 */ 
public class BucketSort { 
  public static void bucketSort(DataWrap[] data,int min,int max) { 
    System.out.println("开始排序"); 
    int arrayLength = data.length; 
    DataWrap[] temp = new DataWrap[arrayLength]; 
    int[] buckets = new int[max - min]; 
    for (int i = 0; i < arrayLength; i++) { 
      buckets[data[i].data - min]++; 
    } 
    System.out.println(Arrays.toString(buckets)); 
    for (int i = 1; i < max - min; i++) { 
      buckets[i] = buckets[i] + buckets[i - 1]; 
    } 
    System.out.println(Arrays.toString(buckets)); 
    System.arraycopy(data,temp,arrayLength); 
    for (int k = arrayLength - 1; k >= 0; k--) { 
      data[--buckets[temp[k].data - min]] = temp[k]; 
    } 
  } 
  public static void main(String[] args) { 
    DataWrap[] data = { new DataWrap(9,new DataWrap(5,new DataWrap(-1,new DataWrap(8,new DataWrap(7,new DataWrap(3,new DataWrap(-3,new DataWrap(1,"*")}; 
    System.out.println("排序之前：n" + java.util.Arrays.toString(data)); 
    bucketSort(data,-3,10); 
    System.out.println("排序之后：n" + java.util.Arrays.toString(data)); 
  } 
}

结果

排序之前：
[9,5,-1,8,5*,7,3,1,3*]
开始排序
[1,2,1]
[1,10]
排序之后：
[-3,3*,9]

堆排序

代码：

package interview; 
/** 
 * @author Administrator 
 * 堆排序 
 */ 
public class HeapSort { 
  public static void heapSort(DataWrap[] data) { 
    System.out.println("开始排序"); 
    int arrayLength = data.length; 
    // 循环建堆 
    for (int i = 0; i < arrayLength - 1; i++) { 
      // 建堆 
      builMaxdHeap(data,arrayLength - 1 - i); 
      // 交换堆顶和最后一个元素 
      swap(data,arrayLength - 1 - i); 
      System.out.println(java.util.Arrays.toString(data)); 
    } 
  } 
  // 对data数组从0到lastIndex建大顶堆 
  private static void builMaxdHeap(DataWrap[] 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; 
        } 
      } 
    } 
  } 
  // 交换data数组中i、j两个索引处的元素 
  private static void swap(DataWrap[] data,int i,int j) { 
    DataWrap temp = data[i]; 
    data[i] = data[j]; 
    data[j] = temp; 
  } 
  public static void main(String[] args) { 
    DataWrap[] data = { new DataWrap(9,"")}; 
    System.out.println("排序之前：n" + java.util.Arrays.toString(data)); 
    heapSort(data); 
    System.out.println("排序之后：n" + java.util.Arrays.toString(data)); 
  } 
}

结果：

排序之前：
[9,30*]
[-16,30*]
[21,30*]
[-49,30*]
[-30,30*]

直接插入排序

package interview;
public class InsertSort {
	public static void insertSort(DataWrap[] data){ 
	  System.out.println("开始排序"); 
	  int arrayLength = data.length; 
	  for(int i = 1;i < arrayLength;i++){ 
	    DataWrap temp = data[i]; 
	    if(data[i].compareTo(data[i-1]) < 0){ 
	      int j = i -1; 
	      for(;j >= 0 && data[j].compareTo(temp) > 0;j--){ 
	        data[j +1] = data[j]; 
	      } 
	      data[j + 1] = temp; 
	    } 
	    System.out.println(java.util.Arrays.toString(data)); 
	  } 
	} 
	public static void main(String[] args) { 
	  DataWrap[] data = { new DataWrap(9,"")}; 
	  System.out.println("排序之前：n" + java.util.Arrays.toString(data)); 
	  insertSort(data); 
	  System.out.println("排序之后：n" + java.util.Arrays.toString(data)); 
	} 
}

结果

排序之前：
[9,30]

归并排序

算法的时间效率：归并算法需要递归地进行分解、合并，每进行一趟归并排序，需要merge()方法一次，每次执行
merge()需要比较n次，较差，需要一个与原始序列同样大小的辅助序列。算法的稳定性：稳定
代码：

package interview; 
/** 
 * @author Administrator 
 * 归并排序 
 */ 
public class MergeSort { 
  public static void mergeSort(DataWrap[] data) { 
    // 归并排序 
    sort(data,data.length - 1); 
  } 
  // 将索引从left到right范围的数组元素进行归并排序 
  private static void sort(DataWrap[] data,int left,int right) { 
    if(left < right){ 
      //找出中间索引 
      int center = (left + right)/2; 
      sort(data,left,center); 
      sort(data,center+1,right); 
      //合并 
      merge(data,center,right); 
    } 
  } 
  // 将两个数组进行归并，归并前两个数组已经有序，归并后依然有序 
  private static void merge(DataWrap[] data,int center,int right) { 
    DataWrap[] tempArr = new DataWrap[data.length]; 
    int mid = center + 1; 
    int third = left; 
    int temp = left; 
    while (left <= center && mid <= right) { 
      if (data[left].compareTo(data[mid]) <= 0) { 
        tempArr[third++] = data[left++]; 
      } else { 
        tempArr[third++] = data[mid++]; 
      } 
    } 
    while (mid <= right) { 
      tempArr[third++] = data[mid++]; 
    } 
    while (left <= center) { 
      tempArr[third++] = data[left++]; 
    } 
    while (temp <= right) { 
      data[temp] = tempArr[temp++]; 
    } 
  } 
  public static void main(String[] args) { 
    DataWrap[] data = { new DataWrap(9,"") }; 
    System.out.println("排序之前：n" + java.util.Arrays.toString(data)); 
    mergeSort(data); 
    System.out.println("排序之后：n" + java.util.Arrays.toString(data)); 
  } 
}

结果：

排序之前：
[9,30]

基数排序

（编辑：安卓应用网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!