疯狂java


您现在的位置: 疯狂软件 >> 新闻资讯 >> 正文

Java实现归并排序算法、快速排序算法


 

   

  归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

  基本思想

  可以将一组数组分成A,B两组

  依次类推,当分出来的小组只有一个数据时,就可以认为这个小组已经达到了有序

  然后合并相邻的两个小组

  这样先通过递归的分解数组,再合并数组就可以完成 归并排序。

  两个数组的合并算法实现

  public class Merge {

  public static void main(String[] args) {

  int[] arrayA = new int[] { 1, 6, 3, 4, 5 };

  int[] arrayB = new int[] { 2, 7, 8, 9 };

  int[] temp = new int[9];

  mergeArray(arrayA, arrayA.length, arrayB, arrayB.length, temp);

  for (int i : temp) {

  System.out.print(i + " ");

  }

  }

  /**

  * 将数组 arrayA[] 和 arrayB[] 合并到 arrayC[]

  */

  private static void mergeArray(int arrayA[], int lengthA, int arrayB[], int lengthB, int temp[]) {

  int i = 0, j = 0, k = 0;

  while (i < lengthA && j < lengthB) { // 将两个有序的数组合并,排序到辅助数组temp中

  if (arrayA[i] > arrayB[j]) {

  temp[k++] = arrayB[j++];

  }

  else {

  temp[k++] = arrayA[i++];

  }

  }

  while (i < lengthA) { // 如果arrayA[] 中还没有合并完的,则直接将arrayA[]中没有合并的数组复制到辅助数组中

  temp[k++] = arrayA[i++];

  }

  while (j < lengthB) { // 如果arrayB[] 中还没有合并完的,则直接将arrayB[]中没有合并的数组复制到辅助数组中

  temp[k++] = arrayB[j++];

  }

  }

  }

  算法实现

  public class MergeSorter {

  public void sort(int[] array) {

  int[] auxArray = new int[array.length];

  mergeSort(array, auxArray, 0, array.length - 1);

  }

  /**

  * 基于分治思想,执行归并排序

  */

  private void mergeSort(int[] array, int[] auxArray, int low, int high) {

  int dividedIndex = 0;

  if (low < high) {

  dividedIndex = (low + high) / 2;

  mergeSort(array, auxArray, low, dividedIndex); // 左边递归归并排序

  mergeSort(array, auxArray, dividedIndex + 1, high); // 右边递归归并排序

  mergeArray(array, auxArray, low, dividedIndex, high); // 合并分治结果

  }

  }

  private void mergeArray(int[] array, int[] temp, int low, int dividedIndex, int high) {

  int i = low; // 指向左半分区的指针

  int j = dividedIndex + 1; // 指向右半分区的指针

  int k = 0; // 指向辅助数组的指针

  while (i <= dividedIndex && j <= high) {

  if (array[i] > array[j]) {

  temp[k++] = array[j++];

  } else {

  temp[k++] = array[i++];

  }

  }

  while (i <= dividedIndex) {

  temp[k++] = array[i++];

  }

  while (j <= high) {

  temp[k++] = array[j++];

  }

  // 最后把辅助数组的元素复制到原来的数组中去,归并排序结束

  for (i = low, k = 0; i <= high; i++, k++) {

  array[i] = temp[k];

  }

  }

  }

  快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod)。

  基本思想

  先从数组中找出一个数作为基准数

  分区过程,将比这个数小的数全部放到它的左边,大于它的数全部放到右边

  再对左右区间重复第二步,直到各区间都只有一个数

  排序过程

  在一篇博客上看到一个很有趣的讲解方法:叫做 挖坑填数+分治法。

  假如有一个10个数的数组:i=0,j=9,pivot=array[i]=x

  由于已经array[0]中的数保存到pivot中,可以理解成在数组array[0]上挖了个坑,可以将其他数据填充到这里来。

  然后j向前找比当前基准数pivot小的数,当符合条件时(比如是第8个参数),那么将array[8]挖出填充到array[0]这个坑。这时就多出了array[8]这个坑,于是从i开始向后找大于pivot的数,填充array[8]这个坑。

  重复操作。

  最后i==j时会退出循环,这时多出了array[i]这个坑,怎么办呢?将pivot填充到array[i]。这时对左右两个区间继续进行排序就好了。

  算法实现

  /**

  * 快速排序

  */

  public class QuickSort {

  public void sort(int[] array) {

  quickSort(array, 0, array.length - 1);

  }

  /**

  * 通过划分,基于分治思想,递归执行子任务排序最后合并

  * @param low 数组首位索引

  * @param high 数组末尾索引

  */

  private void quickSort(int[] array, int low, int high) {

  int pivotPos;

  if (low < high) {

  pivotPos = partition(array, low, high);

  quickSort(array, low, pivotPos - 1);

  quickSort(array, pivotPos + 1, high);

  }

  }

  /**

  * 简单划分方法

  */

  private int partition(int[] array, int i, int j) {

  int pivot = array[i]; // array[i] 就是 第一个坑

  while (i < j) {

  while (i < j && array[j] >= pivot) {

  j--; // 从右向左找出小于基准数pivot的数来填充array[i]

  }

  if (i < j) {

  array[i] = array[j]; // 将array[j]填充到array[i]中,array[j]就形成了一个新的坑

  i++;

  }

  while (i < j && array[i] <= pivot) {

  i++; // 从左向右找出大于基准数pivot的数来填充array[j]

  }

  if (i < j) {

  array[j] = array[i]; // 将array[i]填充到array[j]中,array[i]就形成了一个新的坑

  j--;

  }

  }

  array[i] = pivot; // 退出时,i等于j。将pivot填到这个坑中。

  return i;

  }

  }