排序算法

  • 冒泡排序
    1. /**
    2.    * 冒泡排序
    3.    * @param num
    4.    */
    5.   public void bubbleSort(int[] num){
    6.       for (int i = 0; i < num.length; i++) {
    7.           for (int j = 0; j < num.length-i-1; j++) {
    8.               if(num[j]>num[j+1]){
    9.                   int temp = num[j];
    10.                   num[j] = num[j+1];
    11.                   num[j+1] = temp;
    12.               }
    13.           }
    14.       }
    15.   }
  • 选择排序
    1. /**
    2.    * 选择排序
    3.    * @param nums
    4.    */
    5.   public void selectSort(int[] nums){
    6.       for (int i = 0; i < nums.length; i++) {
    7.           int minIndex = i;
    8.           for (int j = i; j < nums.length; j++) {
    9.               if(nums[j]<nums[minIndex]){
    10.                   minIndex = j; //更新最小值的下标
    11.               }
    12.           }
    13.           //将当前元素与目前最小值交换
    14.           int temp = nums[minIndex];
    15.           nums[minIndex] = nums[i];
    16.           nums[i] = temp;
    17.       }
    18.   }
  • 插入排序
    1. /**
    2.    * 直接插入排序
    3.    * @param nums
    4.    */
    5.   public void insertSort(int[] nums){
    6.       int n = nums.length;
    7.       for(int i=1;i<n;i++){
    8.           //待排序元素小于有序序列的最后一个元素时，向前插入
    9.           if(nums[i]<nums[i-1]){
    10.               int temp = nums[i]; //待排序元素
    11.               for(int j=i;j>=0;j--){
    12.                   if(j>0&&nums[j-1]>temp){
    13.                       nums[j] = nums[j-1]; //元素后移
    14.                   }else{
    15.                       nums[j] = temp;  //放在合适的位置
    16.                       break;
    17.                   }
    18.               }
    19.           }
    20.       }
    21.   }
  • 希尔排序
    1. /**
    2.    * 希尔排序
    3.    * @param nums
    4.    */
    5.   public void shellSort(int[] nums){
    6.       int len = nums.length;
    7.       int d = len/2; //增量
    8.       while(d>0) {
    9.           //一趟排序
    10.           for (int i = d;i<len;i++) {
    11.               for (int j = i;j>=d;j-=d) {
    12.                   if (nums[j] < nums[j-d]) {
    13.                       int temp = nums[j - d];
    14.                       nums[j - d] = nums[j];
    15.                       nums[j] = temp;
    16.                   }
    17.               }
    18.           }
    19.           d /= 2;//每次增量减半
    20.       }
    21.   }
  • 堆排序 ```java import java.io.; import java.util.; import java.text.; import java.math.; import java.util.regex.*;

public class Main{ public void heapSort(int[] nums){ int len = nums.length; //构建大顶堆 for(int i=len/2-1;i>=0;i—) { adjustHeap(nums,i,len); } System.out.println(Arrays.toString(nums)); for (int j=len-1;j>0;j—) { //交换堆顶和最后一个元素 int temp = nums[0]; nums[0] = nums[j]; nums[j] = temp; //调整堆，注意不能取到最后一个元素 adjustHeap(nums,0,j); } }

  1. //调整堆
  2. public void adjustHeap(int[] nums,int i,int len){
  3.     int temp = nums[i];
  4.     //沿关键字较大的孩子节点向下筛选
  5.     for(int j=i*2+1;j<len;j=j*2+1){
  6.         //选出左右节点中较大的节点
  7.         if (j+1<len && nums[j] < nums[j+1]) {
  8.             j++;
  9.         }
  10.         //再将较大值与根节点相比较
  11.         if (nums[j] > temp) {
  12.             nums[i] = nums[j];
  13.             //更新i
  14.             i = j;
  15.         }else{
  16.             break;
  17.         }
  18.     }
  19.     nums[i] = temp;//将temp放到最终位置
  20. }
  23. public static void main(String[] args) {
  24.     int[] nums = {1,2,3,4,5,6,7};
  25.     Main main = new Main();
  26.     main.heapSort(nums);
  27.     System.out.println(Arrays.toString(nums));
  28. }

}

  3. - 
  4. 归并排序
  5. ```java
  6. public void mergeSort(int[] nums){
  7.     int[] p = Arrays.copyOf(nums,nums.length);
  8.     mergeSort(nums,0,nums.length-1,p);
  9. }
  11. private void mergeSort(int[] nums, int left, int right,int[] p) {
  12.     if(left==right) return; //1个元素时总是有序的
  13.     int mid = left + (right - left) / 2;
  14.     mergeSort(nums, left, mid,p); //使左半部分有序 前闭后开
  15.     mergeSort(nums, mid + 1, right,p); //使右半部分有序
  16.     if(nums[mid]<=nums[mid+1]) return; //若整个数组已经有序，则不需要合并
  17.     merge(nums, left, mid, right,p);//跨越两个区间有序
  18. }
  20. private void merge(int[] nums, int left, int mid, int right,int[] p) {
  21.     //拷贝数组
  22.     for(int i=left;i<=right;i++){
  23.         p[i] = nums[i];
  24.     }
  25.     //左右数组的起点
  26.     int i = left;
  27.     int j = mid+1;
  28.     //插入排序
  29.     for(int k=left;k<=right;k++){
  30.         //只有左边数组
  31.         if(j==right+1){
  32.             nums[k] = p[i++];
  33.         }else if(i==mid+1){
  34.             nums[k] = p[j++];
  35.         }else{
  36.             if(p[i]>p[j]){
  37.                 nums[k] = p[j++];
  38.             }else{
  39.                 nums[k] = p[i++];
  40.             }
  41.         }
  42.     }
  43. }

  • 快速排序

    1. /**
    2.    * 快速排序
    3.    * @param nums
    4.    */
    5.   public void quickSort(int[] nums){
    6.       quickSort(nums,0,nums.length-1);
    7.   }
    9.   private void quickSort(int[] nums, int left, int right) {
    10.       if(left>=right) return;
    11.       int index = selectIndex(nums,left,right);
    12.       quickSort(nums,left,index-1);
    13.       quickSort(nums, index+1, right);
    14.   }
    16.   private int selectIndex(int[] nums, int left, int right) {
    17.       int temp = nums[left];
    18.       while(left<right){
    19.           while(left<right&&nums[right]>=temp){
    20.               right--;
    21.           }
    22.           nums[left] = nums[right];
    23.           while(left<right&&nums[left]<=temp){
    24.               left++;
    25.           }
    26.           nums[right] = nums[left];
    27.       }
    28.       nums[left] = temp;//一定要还原回去，不能破坏原数组的数据
    29.       return left;
    30.   }