排序算法——java实现（上）

作者: SYFHEHE | 来源:发表于2018-09-08 16:10 被阅读0次

0.总结

常用的八种排序算法的时间、空间复杂度和稳定性总结如下：

image.png

算法复杂度分析中的符号

下面我们分别介绍下每种算法的排序思路以及java的实现方法。

1.冒泡排序

1.1 基本思想：

设数组的长度为N：
（1）比较前后相邻的二个数据，如果前面数据大于后面的数据，就将这二个数据交换。
（2）这样对数组的第0个数据到N-1个数据进行一次遍历后，最大的一个数据就“沉”到数组第N-1个位置。
（3）N=N-1，如果N不为0就重复前面二步，否则排序完成。

1.2 代码实现：

我们可以很快想到一种最简便的排序方法：

 public static void bubbleSort1(int[] array, int N) {
    int temp = 0;
    for (int i = 0; i < array.length; i++) {
      for (int j = i; j < array.length; j++) {
        if (array[i] > array[j]) {
          temp = array[i];
          array[i] = array[j];
          array[j] = temp;
        }
      }
    }
  }

但是这种方法不好啊，原因就是最大的一个数据就“沉”到数组第N-1个位置，下一次就不需要再将待排序的数据与之比较，而且，如果一个本身有序的序列，或者序列后面一大部分都是有序的序列，这种冒泡算法还在执行。

那怎么办呢？有两点可以改进：
（1）每次排序，都会排除一个元素，所以每次循环都将队尾元素剔除出排序的序列。
（2）设置一个标志位，如果从第一个到队尾的元素都没有发生交换，则可认为已经排完序。

 public static void bubbleSort2(int[] array, int N) {
    int temp = 0;
    Boolean flag = false;//设置一个标志，如果这一趟发生了交换，则为true，否则为false。明显如果有一趟没有发生交换，说明排序已经完成。
    for (int i =  array.length-1; i > 0; i--) {
      flag = false;
      for (int j = 0; j < i; j++) {
        count++;
        if (array[j] > array[j+1]) {
          temp = array[j];
          array[j] = array[j+1];
          array[j+1] = temp;
          flag = true;
        }
      }
      if(flag == false) {
        break;
      }
    }
  }

利用数组 {1, 1, 2, 0, 9, 3, 12, 7, 8, 3, 4, 65, 22}测试发现，将两种方法一对比，方法一执行了91遍，方法二执行了50遍。

测试结果

2.插入排序

2.1 基本思想：

从数组的第二个元素开始循环，将选中的元素与之前的元素一一比较，如果选中的元素小于之前的元素，则将之前的元素后移，最后再将选中的元素放在合适的位置。在这个算法执行的过程中，总是保持着索引i之前的数组是升序排列的。

2.2 代码实现：

  public static void insertSort(int[] array, int N) {
    int i,j, temp = 0;
    for ( i = 1; i < array.length; i++) {//从数组的第二个元素开始循环
      temp = array[i];//选中的元素
      for ( j = i; j > 0 && array[j - 1] > temp; j--) {//上一个元素是否大于选中的元素,
        array[j] = array[j - 1];       //如果选中的元素大于之前的元素，则将之前的元素后移 
      }
      array[j] = temp;//再将选中的元素放在合适的位置
    }
  }

冒泡排序和插入排序的排序方法他的平均时间复杂度都是Ω（n2）（Ω表示算法下届），为什么呢，主要是它们都是只交换相邻元素，而且每次只消除一个逆序对，那怎么才能提高效率呢？两个办法
（1）每次不止消除一个逆序对
（2）每次交换可以相隔更远

3.希尔排序

3.1 基本思想

在直接插入排序的基础上进行的优化，每次交换可以相隔更远。其步骤大概分为两步：
（1）先选取一个小于n的整数d（步长），然后按照步长d将待排序序列分为d组，从第一个记录开始间隔为d的为一个组；
（2）然后对各组内进行直接插入排序，一趟过后，间隔为d的序列有序，随着有序性的改善，减少步长d重复进行，直到d=1。

3.2 代码实现：

  public static void shellSort(int[] array, int N) {
    int i, j, D, temp = 0;
    for (D = N / 2; D >= 1; D /= 2) {//步长
      for (i = 1; i < array.length; i++) {// 从数组的第二个元素开始循环
        temp = array[i];// 选中的元素
        for (j = i; j >= D && array[j - D] > temp; j-= D) {// 上一个元素是否大于选中的元素,
          array[j] = array[j - D]; // 如果选中的元素大于之前的元素，则将之前的元素后移
        }
        array[j] = temp;// 再将选中的元素放在合适的位置
      }
    }
  }

4.选择排序

4.1 基本思想

在直接插入排序的基础上进行的优化，每次不止消除一个逆序对，其步骤人如下：
（1）对于给定的一组记录，经过第一轮比较后得到最小的记录，然后将该记录的位置与第一个记录的位置交换；
（2）接着对不包括第一个记录以外的其他记录进行第二次比较，得到最小记录并与第二个位置记录交换；重复该过程，知道进行比较的记录只剩下一个为止。

4.2 代码实现：

  public static void selectSort(int[] array, int N) {
    int i, j = 0;
    for (i = 0; i < array.length; i++) {
      int k = i;
      //找到最小值的下标
      for (j = k + 1; j < array.length; j++) {
        if (array[j] < array[k]) {
          k = j;
        }
      }
      //如果最小值不是array[i],将最小值和与array[i]交换。
      if (k != i) {
        int temp = array[i];
        array[i] = array[k];
        array[k] = temp;
      }
    }
  }

简单选择排序是从n个记录中找出一个最小的记录，需要比较n-1次。但是这样的操作并没有把每一趟的比较结果保存下来，在后一趟的比较中，有许多比较在前一趟已经做过了，但由于前一趟排序时未保存这些比较结果，所以后一趟排序时又重复执行了这些比较操作，因而记录的比较次数较多。

5.堆排序

5.1 基本思想

堆排序是选择排序的一种升级，它的方法步骤如下：
（1）将待排序的序列构造成一个大顶堆。（整个序列的最大值就是堆顶的根节点）
（2）将它移走(其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值)
（3）将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次最大值。如此反复执行，就能得到一个有序序列了。

什么是堆？

堆是具有下列性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆。

5.2 java代码

  private static void heapSort(int[] arr) {
    int len = arr.length - 1;
    // 步骤1：堆构造 只要从非叶子节点开始
    for (int i = len / 2 - 1; i >= 0; i--) {
      heapAdjust(arr, i, len);
    }
    while (len >= 0) {
      // 步骤2：将堆顶元素与尾节点交换后，长度减1，尾元素最大
      swap(arr, 0, len--);
      // 步骤3：再次对堆进行调整
      heapAdjust(arr, 0, len);
    }
  }

  /*
   * 参数1：数组 参数2：当前元素 父节点编号 参数3：数组长度
   * 
   */
  public static void heapAdjust(int[] arr, int i, int len) {
    int left, right, j;
    while ((left = 2 * i + 1) <= len) {// 判断当前父节点有无左节点（即有无孩子节点，left为左节点）
      right = left + 1; // 右节点
      j = left; // j指向左节点
      if (j < len && arr[left] < arr[right]) // 右节点大于左节点
        j++; // 当前把"指针"指向右节点
      if (arr[i] < arr[j]) // 将父节点与孩子节点交换
        swap(arr, i, j);
      else // 说明比孩子节点都大，直接跳出循环语句
        break;
      i = j;// 当前元素指向j，指向左子节点，子节点如果还有叶子节点的话 还要向下比较，不然就不是真正的最大堆
    }
  }

  public static void swap(int[] arr, int i, int len) {
    int temp = arr[i];
    arr[i] = arr[len];
    arr[len] = temp;
  }

6.归并排序

6.1基本思想

将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列之间有序。将两个有序数组合并成一个有序数组，称为二路归并(binary merge)。
简而言之，就是如下图所示的过程：

Merge Sort

6.2 java代码

1.对于两个有序的数组，要将其合并为一个有序数组，我们可以很容易地写出如下代码：

 /**
   * 将两个数组进行归并，归并前面2个数组已有序，归并后依然有序
   * 
   * @param data 数组对象
   * @param left 左数组的第一个元素的索引
   * @param right 右数组最后一个元素的索引
   * @param rightEnd 左数组的最后一个元素的索引，center+1是右数组第一个元素的索引
   */
  public static void merge(int[] data, int left, int right, int rightEnd) {
    // 临时数组
    int[] tmpArr = new int[data.length];
    // 左边终点位置
    int leftEnd = right - 1;
    // 缓存左数组第一个元素的索引
    int tmp = left;
    int elementsNum = rightEnd - left + 1;
    while (left <= leftEnd && right <= rightEnd) {
      // 从两个数组中取出最小的放入临时数组
      if (data[left] <= data[right]) {
        tmpArr[tmp++] = data[left++];
      } else {
        tmpArr[tmp++] = data[right++];
      }
    }
    // 剩余部分依次放入临时数组（实际上两个while只会执行其中一个）
    while (left <= leftEnd) {
      tmpArr[tmp++] = data[left++];
    }
    while (right <= rightEnd) {
      tmpArr[tmp++] = data[right++];
    }
    for (int i = 0; i < elementsNum; i++, rightEnd--) {
      data[rightEnd] = tmpArr[rightEnd];
    }
  }

2.如果A,B无序，怎么办呢？可以把它们再分成更小的数组。如此一直划分到最小，每个子数组都只有一个元素，则可以视为有序数组。
3.从这些最小的数组开始，逆着上面的步骤合并回去，整个数组就排好了。

总而言之，归并排序就是使用递归，先分解数组为子数组，再合并数组。

 /**
   * 递归实现归并排序
   * 
   * @param data 数组对象
   * @param left 左数组的第一个元素的索引
   * @param rightEnd 左数组的最后一个元素的索引，center+1是右数组第一个元素的索引
   */
  public static void sort(int[] data, int left, int rightEnd) {
    if (left < rightEnd) {
      // 找出中间索引
      int center = (left + rightEnd) / 2;
      // 对左边数组进行递归
      sort(data, left, center);
      // 对右边数组进行递归
      sort(data, center + 1, rightEnd);
      // 合并
      merge(data, left, center + 1, rightEnd);
      print(data);
    }
  }

递归实现的归并排序算法稳定，但是需要额外的存储空间才能实现，如果使用的是数组需要O(n)的额外空间，链表需要O(log(n))的额外空间。