常用的八种排序算法Java代码实现

2018年9月5日
Difference Between Volatile and Synchronized Keywords in Java
2018年8月25日

常用的八种排序算法Java代码实现

package algorithm;

import java.util.Arrays;

public class EightAlgorithm {
  /**
   * 
   * 常用的八种排序算法Java代码实现
   * 时间:2018-9-5-下午9:14:30 
   * 邮件:hasp_Jason@163.com
   * @exception 
   * 辅助记忆
   * 时间复杂度记忆- 
   * 冒泡、选择、直接 排序需要两个for循环,每次只关注一个元素,平均时间复杂度为O(n2)(一遍找元素O(n),一遍找位置O(n))
   * 快速、归并、希尔、堆基于二分思想,log以2为底,平均时间复杂度为O(nlogn)(一遍找元素O(n),一遍找位置O(logn))
   * 稳定性记忆-“快选希堆”(非稳定:快牺牲稳定性) 
   * 排序算法的稳定性:排序前后相同元素的相对位置不变,则称排序算法是稳定的;否则排序算法是不稳定的。
   */
  public static void main(String[] args) {
    
    int []array={23,56,8,45,2,95,11,12,17,10,11};
    System.out.println("length: "+array.length);
    insertSort(array);	//1.直接插入
    //sheelSort(array);		//2.希尔排序
    //selectSort(array);	//3.简单选择排序
    //heapSort(array);		//4.堆排序
    //bubbleSort(array);	//5.冒泡排序
    //quickSort(array, 0, array.length-1);//6.快速排序  
    //mergeSort(array);		//7.归并排序
    //sort(array,10);		//8.基数排序
    System.out.println(Arrays.toString(array));
  }
  
  /**
   * 1.直接插入  经常碰到这样一类排序问题:把新的数据插入到已经排好的数据列中。
   * 平均时间复杂度	最坏时间复杂度	空间复杂度		是否稳定
   * 	O(n^2)			O(n^2)		O(1)		是
   * 	将第一个数和第二个数排序,然后构成一个有序序列
   * 	将第三个数插入进去,构成一个新的有序序列。
  	 * 	对第四个数、第五个数……直到最后一个数,重复第二步。
  	 * 
  	 ***如何写成代码:
  	 *	1.首先设定插入次数,即循环次数,for(int i=1;i<length;i++),1个数的那次不用插入。
  	 *	2.设定插入数和得到已经排好序列的最后一个数的位数。insertNum和j=i-1。
  	 *	3.从最后一个数开始向前循环,如果插入数小于当前数,就将当前数向后移动一位。
  	 *	4.将当前数放置到空着的位置,即j+1。
   */
  public static void insertSort(int[] a) {
    int insertNum; // 要插入的数
    for (int i = 1; i < a.length; i++) {
      insertNum = a[i];
      int j = i - 1;
      while (j >= 0 && a[j] > insertNum) {// 将大于insertNum的数向后移动一格
        a[j + 1] = a[j];
        j--;
      }
      a[j + 1] = insertNum;
    }
  }
  
  /**
   * 2.希尔排序   对于直接插入排序问题,数据量巨大时。
   * 平均时间复杂度	最坏时间复杂度	空间复杂度	是否稳定
   * O(nlogn)		O(n^s)		O(1)	不是
   * 	将数的个数设为n,取奇数k=n/2,将下标差值为k的数分为一组,构成有序序列。
   * 	再取k=k/2 ,将下标差值为k的数分为一组,构成有序序列。
   * 	重复第二步,直到k=1执行简单插入排序。
   * 
   ***如何写成代码:
   *	1.首先确定分的组数。
   *	2.然后对组中元素进行插入排序。
   *	3.然后将length/2,重复1,2步,直到length=0为止。
   */
  public static void sheelSort(int[] a) {
    int length = a.length;
    while (length != 0) {
      length = length / 2;
      System.out.println("length变化: " + length);
      for (int x = 0; x < length; x++) { 	// 分组个数
        for (int i = x + length; i < a.length; i += length) {
          int j = i - length; 	// j为有序序列最后一位的位数
          int insertNum = a[i]; 	// 要插入的元素
          for (; j >= 0 && insertNum < a[j]; j -= length) {
            a[j + length] = a[j];	// 向后移动length位
          }
          a[j + length] = insertNum;
        }
      }
    }
  }
  
  /**
   * 3.简单选择排序    常用于取序列中最大最小的几个数时。
   * 平均时间复杂度	最坏时间复杂度	空间复杂度	是否稳定
   * O(n^2) 		O(n^2)		O(1)	不是
   * 	(如果每次比较都交换,那么就是交换排序;如果每次比较完一个循环再交换,就是简单选择排序。)
   * 	遍历整个序列,将最小的数放在最前面。
   * 	遍历剩下的序列,将最小的数放在最前面。
   * 	重复第二步,直到只剩下一个数。
   * 
   ***如何写成代码:
   *	1.首先确定循环次数,并且记住当前数字和当前位置。
   *	2.将当前位置后面所有的数与当前数字进行对比,小数赋值给key,并记住小数的位置。
   *	3.比对完成后,将最小的值与第一个数的值交换。
   *	4.重复2、3步。
   */
  public static void selectSort(int[] a) {
    int length = a.length;
    for (int i = 0; i < length; i++) {			// 循环次数
      int key = a[i];
      int position = i;
      for (int j = i + 1; j < length; j++) {	// 选出最小值和位置
        if (a[j] < key) {
          key = a[j];
          position = j;
        }
      }
      a[position] = a[i];			// 交换位置
      a[i] = key;
    }
  }
  
  /**
   * 4.堆排序   对简单选择排序的优化。
   * 平均时间复杂度	最坏时间复杂度	空间复杂度	是否稳定
   * O(nlogn)		O(nlogn)	O(1)	不是
   *	将序列构建成大顶堆。
   *	将根节点与最后一个节点交换,然后断开最后一个节点。
   *	重复第一、二步,直到所有节点断开。
   */
  public static void heapSort(int[] a) {
    System.out.println("开始排序");
    int arrayLength = a.length;
    // 循环建堆
    for (int i = 0; i < arrayLength - 1; i++) {
      // 建堆
      buildMaxHeap(a, arrayLength - 1 - i);
      // 交换堆顶和最后一个元素
      swap(a, 0, arrayLength - 1 - i);
      System.out.println(Arrays.toString(a));
    }
  }

  private static void swap(int[] data, int i, int j) {
    int tmp = data[i];
    data[i] = data[j];
    data[j] = tmp;
  }

  // 对data数组从0到lastIndex建大顶堆
  private static void buildMaxHeap(int[] 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] < data[biggerIndex + 1]) {
            // biggerIndex总是记录较大子节点的索引
            biggerIndex++;
          }
        }
        // 如果k节点的值小于其较大的子节点的值
        if (data[k] < data[biggerIndex]) {
          // 交换他们
          swap(data, k, biggerIndex);
          // 将biggerIndex赋予k,开始while循环的下一次循环,重新保证k节点的值大于其左右子节点的值
          k = biggerIndex;
        } else {
          break;
        }
      }
    }
  }
  
    
    /**
     * 5.冒泡排序    一般不用。
     * 平均时间复杂度	最坏时间复杂度	空间复杂度	是否稳定
     * O(n^2) 		O(n^2)		O(1)	是
   *	将序列中所有元素两两比较,将最大的放在最后面。
   *	将剩余序列中所有元素两两比较,将最大的放在最后面。
   *	重复第二步,直到只剩下一个数。
   *	
   ***如何写成代码:
   *	1.设置循环次数。
   *	2.设置开始比较的位数,和结束的位数。
   *	3.两两比较,将最小的放到前面去。
   *	4.重复2、3步,直到循环次数完毕。
   *
     */
  public static void bubbleSort(int[] a) {
    int length = a.length;
    int temp;
    for (int i = 0; i < length; i++) {
      for (int j = 0; j < length - i - 1; j++) {
        if (a[j] > a[j + 1]) {
          temp = a[j];
          a[j] = a[j + 1];
          a[j + 1] = temp;
        }
      }
    }
  }

  /**
   * 6.快速排序		要求时间最快时。
   * 平均时间复杂度	最坏时间复杂度	空间复杂度		是否稳定
   * O(nlogn) 	O(n^2)		O(logn)	不是
   *	选择第一个数为p,小于p的数放在左边,大于p的数放在右边。
   *	递归的将p左边和右边的数都按照第一步进行,直到不能递归。
   */
  public static void quickSort(int[] numbers, int start, int end) {
    if (start < end) {
      int base = numbers[start];// 选定的基准值
      int temp;
      int i = start, j = end;
      do {
        while ((numbers[i] < base) && (i < end))
          i++;
        while ((numbers[j] > base) && (j > start))
          j--;
        if (i <= j) {
          temp = numbers[i];
          numbers[i] = numbers[j];
          numbers[j] = temp;
          i++;
          j--;
        }
      } while (i <= j);
      if (start < j)
        quickSort(numbers, start, j);
      if (end > i)
        quickSort(numbers, i, end);
    }
  }

  /**
   * 7.归并排序		速度仅次于快排,内存少的时候使用,可以进行并行计算的时候使用。
   * 平均时间复杂度	最坏时间复杂度	空间复杂度	是否稳定
   * O(nlogn) 	O(nlogn)	O(n)	是
   *	选择相邻两个数组成一个有序序列。
   *	选择相邻的两个有序序列组成一个有序序列。
   *	重复第二步,直到全部组成一个有序序列。
   */
  public static void mergeSort(int[] arr) {
    int[] temp = new int[arr.length];// 在排序前,先建好一个长度等于原数组长度的临时数组,避免递归中频繁开辟空间
    mergeSort(arr, 0, arr.length - 1, temp);
  }

  private static void mergeSort(int[] arr, int left, int right, int[] temp) {
    if (left < right) {
      int mid = (left + right) / 2;
      mergeSort(arr, left, mid, temp);// 左边归并排序,使得左子序列有序
      mergeSort(arr, mid + 1, right, temp);// 右边归并排序,使得右子序列有序
      merge(arr, left, mid, right, temp);// 将两个有序子数组合并操作
    }
  }

  private static void merge(int[] arr, int left, int mid, int right,
      int[] temp) {
    int i = left;// 左序列指针
    int j = mid + 1;// 右序列指针
    int t = 0;// 临时数组指针
    while (i <= mid && j <= right) {
      if (arr[i] <= arr[j]) {
        temp[t++] = arr[i++];
      } else {
        temp[t++] = arr[j++];
      }
    }
    while (i <= mid) {// 将左边剩余元素填充进temp中
      temp[t++] = arr[i++];
    }
    while (j <= right) {// 将右序列剩余元素填充进temp中
      temp[t++] = arr[j++];
    }
    t = 0;
    // 将temp中的元素全部拷贝到原数组中
    while (left <= right) {
      arr[left++] = temp[t++];
    }
  }
  
  
  /**
   * 8.基数排序		用于大量数,很长的数进行排序时。
   * 平均时间复杂度	最坏时间复杂度	空间复杂度	是否稳定
   * O(N∗M)		O(N∗M)		O(M)	是
   * 将所有的数的个位数取出,按照个位数进行排序,构成一个序列。
   * 将新构成的所有的数的十位数取出,按照十位数进行排序,构成一个序列。
   */
  public static void sort(int[] number, int d) {
    int k = 0;
    int n = 1;
    int m = 1;
    int[][] temp = new int[number.length][number.length];
    int[] order = new int[number.length];
    while (m <= d) {
      for (int i = 0; i < number.length; i++) {
        int lsd = ((number[i] / n) % 10);
        temp[lsd][order[lsd]] = number[i];
        order[lsd]++;
      }
      for (int i = 0; i < d; i++) {
        if (order[i] != 0)
          for (int j = 0; j < order[i]; j++) {
            number[k] = temp[i][j];
            k++;
          }
        order[i] = 0;
      }
      n *= 10;
      k = 0;
      m++;
    }
  } 
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注