排序算法

插入排序

直接插入排序

思路： 将一个记录插入到一个已经排序好的有序表中，找到合适的位置插入。一般将第一个记录当做有序表，从第二个记录还是逐个插入

代码：

public static void insertSort(int[] array) {
    // 将第一个记录看成已经排序好的序列
    for(int i = 1; i < array.length; i++) {
        // 要插入的记录
        int temp = array[i];
        // 找到排序好的第一个记录进行比较
        int j = i - 1;
        // 如果到底了，或者找到了插入的位置
        while(j >= 0 && array[j] > temp) {
            // 后移，空出位置
            array[j + 1] = array[j];
            j--;
        }
        // 插入到j的后面
        if(j != i - 1) {
            array[j + 1] = temp;
        }
    }
}

希尔排序

希尔排序是插入排序的一种改进版本，不需要每个元素挨个比较，而是初期选用大跨步（增量较大）间隔比较，使记录跳跃式接近它的排序位置；然后增量缩小；最后增量为 1 ，这样记录移动次数大大减少，提高了排序效率。

思路

• 先取一个正整数 d1(d1 < n)，把全部记录分成 d1 个组，所有距离为 d1 的倍数的记录看成一组，然后在各组内进行插入排序
• 然后取 d2(d2 < d1)
• 重复上述分组和排序操作；直到取 di = 1(i >= 1) 位置，即所有记录成为一个组，最后对这个组进行插入排序。一般选 d1 约为 n/2，d2 为 d1 /2， d3 为 d2/2 ，…， di = 1

代码实现

public static void shellSort(int[] table) {
    // 增量最开始等于length/2，并逐渐减少
    for (int gap = table.length / 2; gap > 0; gap /= 2) {
        // 从gap个元素，逐个对其所在组进行直接插入排序操作
        for (int i = gap; i < table.length; i++) {
            int j = i;
            int temp = table[j];
            if (table[j] < table[j - gap]) {
                while (j - gap >= 0 && temp < table[j - gap]) {
                    // 移动法
                    table[j] = table[j - gap];
                    j -= gap;
                }
                table[j] = temp;
            }
        }
    }
}

选择排序

简单选择排序

思路

比较length躺，每躺将最大(小)的找出来，赋值给第一个

代码实现

public static void selectSort(int[] table) {
    int temp;
    for (int i = 0; i < table.length; i++) {
        for(int j = i + 1; j < table.length; j++) {
            if(table[j] < table[i]) {
                temp = table[j];
                table[j] = table[i];
                table[i] = temp;
            }
        }

    }
}

堆排序

什么是堆

堆数据结构是一种数组对象，它可以被视为一科完全二叉树结构。它的特点是父节点的值大于（小于）两个子节点的值（分别称为大顶堆和小顶堆）。

堆和数组的互相关系：

堆的基本操作

• A表示堆的数组，下标从1开始，一直到n
• parent(i): 节点i的父节点= floor(i/2)
• left(i): 节点i的左节点 = 2*i
• right(i): 节点i的右节点 = 2*i+1
• heap_size(A): 堆A当前元素的个数

但是在堆排序中一般是基于0开始的，也就是第一个元素是0并不是1(数组的第一个元素是0),所以公式也要做相应的调整：

• Parent(i) = floor((i-1)/2)，i 的父节点下标
• Left(i) = 2i + 1，i 的左子节点下标
• Right(i) = 2(i + 1)，i 的右子节点下标

类似下图:

堆排序的原理

几个操作：

• 最大堆调整（Max-Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点

  public static void maxHeapfiy(int[] array, int index, int heapSize) {
      int iMax = index;
      int iLeft = 2 * index + 1;
      int iRight = 2 * (index + 1);
      if(iLeft < heapSize && array[index] < array[iLeft]) {
          iMax = iLeft;
      }
      if(iRight < heapSize && array[index] < array[iRight]) {
          iMax = iRight;
      }
  
      if(iMax != index) {
          swap(array, iMax, index);
          // 递归调整
          maxHeapfiy(array, iMax, heapSize);
      }
  }

  使得i节点之后的下标都满足最大堆的性质
• 创建最大堆（Build-Max-Heap）：将堆所有数据重新排序，使其成为最大堆

  public static void buildMaxHeadp(int[] array, int heapSize) {
      int i;
      // (heapSize -1)/2以后的节点都是叶子节点，没必要调整
      int iParent = (int)Math.floor((heapSize - 1) / 2);
      for(i = iParent; i >= 0; i--) {
          maxHeapfiy(array, i, heapSize);
      }
  }

• 堆排序（Heap-Sort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算

  public static void heapSort1(int[] array, int heapSize) {
      buildMaxHeadp(array, heapSize);
      for (int i = heapSize - 1; i > 0; i--) {
          swap(array, 0, i);
          maxHeapfiy(array, 0, i);
      }
  }

  交换排序

冒泡排序

思路

临近的数字两两进行比较,按照从小到大或者从大到小的顺序进行交换,

这样一趟过去后,最大或最小的数字被交换到了最后一位,

然后再从头开始进行两两比较交换,直到倒数第二位时结束,

代码实现

public static void bubbleSort(int table[]) {
    for (int i = 0; i < table.length; i++) {
        for(int j = 0; j < table.length-i-1; j++) {
            // 如果i位置比j位置大，则i往前移一个位置
            if(table[j] > table[j+1]) {
                int temp = table[j];
                table[j] = table[j+1];
                table[j+1] = temp;
            }
        }
    }
}

快速排序

这里使用分治实现快速排序

分治法

将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解

思路

1. 数据集中间选一个元素作为基准(pivot)
2. 所有小于基准的元素移到基准的左边，所有大于基准的元素移到基准的右边，这个操作称为分区(partition)
3. 对基准左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止

代码实现

// 分区
public static int partition(int[] array, int left, int right) {
    int pivot = array[( left + right) / 2];
    int temp;
    while (left < right) {
        // 找到左边第一个比基准小的
        while (array[left] < pivot)
            left++;
        // 找到右边第一个比基准大的
        while (array[right] > pivot)
            right--;

        // 如果符合条件，则交换两边位置
        if(left < right) {
            temp= array[left];
            array[left] = array[right];
            array[right] = temp;
        }
    }
    // 返回基准点左边的
    return left;
}

// 快速排序
public static void quickSort(int[] array, int left, int right) {
    int index = partition(array, left, right);
    // 递归排序左边
    if(left < index -1) {
        quickSort(array, left, index -1);
    }
    // 递归排序右边
    if (index + 1 < right) {
        quickSort(array, index, right);
    }
}

归并排序

归并排序也是用分治法，将两个已经排序的序列合并成一个序列的操作。

算法思路

1. 把 n 个记录看成 n 个长度为 l 的有序子表
2. 进行两两归并使记录关键字有序，得到 n/2 个长度为2的有序子表
3. 重复第 2 步直到所有记录归并成一个长度为 n 的有序表为止

分割归并：

代码实现

public static void mergeSort(int[] array, int low, int high) {
        if(low < high) {
            int middle = (low + high) / 2;
            mergeSort(array, low, middle);
            mergeSort(array, middle + 1, high);

            merge(array, low, middle, high);
        }
    }

/**
 * 归并数组
 *
 * 将目标数组的所有元素拷贝到临时数组helper中，记下左右位置
 * 迭代访问helper，将左右两半中较小的元素复制到目标数组
 * 最后将余下所有的元素复制回目标数组
 */
public static void merge(int[] array, int low, int middle, int high){
    // 填充辅助数组
    int[] helper = new int[array.length];
    for (int i = 0; i <= high; i++) {
        helper[i] = array[i];
    }

    int helperLeft = low;
    int helperRight = middle + 1;
    int current = low;

    /**
     * 迭代访问helper数组，比较左右两半元素
     * 并将较小的元素复制到原先的数组中
     */
    while(helperLeft <= middle && helperRight <= high){
        if(helper[helperLeft] <= helper[helperRight]){
            array[current] = helper[helperLeft];
            helperLeft++;
        } else{
            array[current] = helper[helperRight];
            helperRight++;
        }
        current++;
    }

    /**
     * 将数组左半剩余元素复制到原先的数组中
     */
    int remaining = middle - helperLeft;
    for(int i = 0; i <= remaining; i++){
        array[current + i] = helper[helperLeft + i];
    }
}

桶排序(基数排序)

思路

桶排序的思想近乎彻底的分治思想。假设现在需要对一亿个数进行排序。我们可以将其等长地分到10000个虚拟的“桶”里面，这样，平均每个桶只有10000个数。如果每个桶都有序了，则只需要依次输出为有序序列即可。

1. 将待排数据按一个映射函数f(x)分为连续的若干段。理论上最佳的分段方法应该使数据平均分布；实际上，通常采用的方法都做不到这一点。显然，对于一个已知输入范围在【0，10000】的数组，最简单的分段方法莫过于x/m这种方法，例如，f(x)=x/100。
   “连续的”这个条件非常重要，它是后面数据按顺序输出的理论保证
2. 分配足够的桶，按照f(x)从数组起始处向后扫描，并把数据放到合适的桶中。对于上面的例子，如果数据有10000个，则我们需要分配101个桶（因为要考虑边界条件：f(x)=x/100会产生【0，100】共101种情况），理想情况下，每个桶有大约100个数据
3. 对每个桶进行内部排序，例如，使用快速排序。注意，如果数据足够大，这里可以继续递归使用桶排序，直到数据大小降到合适的范围
4. 按顺序从每个桶输出数据。例如，1号桶【112，123，145，189】，2号桶【234，235，250，250】，3号桶【361】，则输出序列为【112，123，145，189，234，235，250，250，361】