基础排序

冒泡排序

/**
 * 冒泡排序，时间复杂度O(n²)
 *
 * @param array 需要排序的数组
 */
private static void bubbleSort(Integer[] array) {
    for (int i = 0; i < array.length; i++) {
        for (int j = 0; j < array.length - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                Integer temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
}

快速排序

/**
 * 快速排序，时间复杂度nlogn,最坏的情况下为O(n²)
 *
 * @param array 待排序的数组
 */
private static void quickSort(Integer[] array, int low, int high) {
    if (array.length == 0 || low > high) {
        return;
    }

    int middle = quickSortDivide(array, low, high);
    quickSort(array, low, middle - 1);
    quickSort(array, middle + 1, array.length - 1);
}

/**
* 划分中轴点
*
* @param array 数组
* @param low   低位
* @param high  高位
*/
private static Integer quickSortDivide(Integer[] array, int low, int high) {
  Integer temp = array[low];
  while (low < high) {
    while (low < high && array[high] >= temp) {
      high--;
    }
    array[low] = array[high];

    while (low < high && array[low] <= array[high]) {
      low++;
    }
    array[high] = array[low];
    array[low] = temp;
  }

  return low;
}

插入排序

/**
 * 插入排序，时间复杂度O(n²)
 * 1.将初始位置看做一个有序数组，如{7,6,5,4,3,2,1} 看做{{7},6,5,4,3,2,1}
 * 2.从第二个位置开始循环向有序数组插入数据，从后向前遍历
 *
 * @param array 待排序的数组
 */
private static void insertSort(Integer[] array) {
    for (int i = 1; i < array.length; i++) {
        int j;
        int x = array[i];
        for (j = i; j > 0 && x < array[j - 1]; j--) {
            array[j] = array[j - 1];
        }
        array[j] = x;
    }

}

简单选择排序

/**
 * 简单选择排序，每次确定一个最小的数，循环向前插入，时间复杂度O(n²)
 *
 * @param array 待排序的数组
 */
private static void simpleSelectSort(Integer[] array) {
    for (int i = 0; i < array.length; i++) {
        int low = i;
        for (int j = i; j < array.length; j++) {
            if (array[j] < array[low]) {
                low = j;
            }
        }

        if (low != i) {
            int temp = array[i];
            array[i] = array[low];
            array[low] = temp;
        }
    }
}

堆排序（最大堆）

/**
 * 将父节点和左右节点比较，较大者更新为父节点，递归完成一次建堆，时间复杂度O (nlgn)
 *
 * @param arrays 待排序的数组
 * @param currentRootNode 当前节点
 * @param size 数组的大小
 */
public static void heapify(int[] arrays, int currentRootNode, int size) {

    if (currentRootNode < size) {
        //左子树和右字数的位置
        int left = 2 * currentRootNode + 1;
        int right = 2 * currentRootNode + 2;

        //把当前父节点位置看成是最大的
        int max = currentRootNode;

        if (left < size) {
            //如果比当前根元素要大，记录它的位置
            if (arrays[max] < arrays[left]) {
                max = left;
            }
        }
        if (right < size) {
            //如果比当前根元素要大，记录它的位置
            if (arrays[max] < arrays[right]) {
                max = right;
            }
        }
        //如果最大的不是根元素位置，那么就交换
        if (max != currentRootNode) {
            int temp = arrays[max];
            arrays[max] = arrays[currentRootNode];
            arrays[currentRootNode] = temp;

            //继续比较，直到完成一次建堆
            heapify(arrays, max, size);
        }
    }
}

/**
 * 最大堆构建，将最大值放在第一位
 * 
 * @param arrays 待排序的数组
 * @param size 数组大小
 */
public static void maxHeapify(int[] arrays, int size) {

    // 从数组的尾部开始，直到第一个元素(角标为0)
    for (int i = size - 1; i >= 0; i--) {
        heapify(arrays, i, size);
    }

}

归并算法

/**
 * 堆排序，每次建最大堆之后，将第一位数和数组当前数组最后一位的数字交换
 * 
 * @param arrays 待排序的数组
 */
public static void heapSort(int[] arrays) {
    for (int i = 0; i < arrays.length; i++) {

        //每次建堆就可以排除一个元素了
        maxHeapify(arrays, arrays.length - i);

        //交换
        int temp = arrays[0];
        arrays[0] = arrays[arrays.length - 1 - i];
        arrays[arrays.length - 1 - i] = temp;

    }
}

/**
* 归并算法，将数组拆分为小单元之后，合并，时间复杂度O(logn)
*
* @param arrays
* @param left
* @param right
* @param temp
*/
public static void mergeSort(int[] arrays, int left, int right, int[] temp) {
  if (left < right) {
    int middle = (left + right) / 2;
    mergeSort(arrays, left, middle, temp);
    mergeSort(arrays, middle + 1, right, temp);

    mergeParts(arrays, left, middle ,right, temp);
  }
}

/**
* 合并算法
*
* @param arrays
* @param left
* @param middle
* @param right
* @param temp
*/
public static void mergeParts(int[] arrays, int left, int middle, int right, int[] temp) {
  int i = left;
  int j = middle + 1;
  int t = 0;
  while (i <= middle && j <= right) {
    if (arrays[i] <= arrays[j]) {
      temp[t++] = arrays[i++];
    } else {
      temp[t++] = arrays[j++];
    }
  }

  while (i <= middle) {
    temp[t++] = arrays[i++];
  }

  while (j <= right) {
    temp[t++] = arrays[j++];
  }

  t = 0;
  //将temp中的元素全部拷贝到原数组中
  while(left <= right){
    arrays[left++] = temp[t++];
  }
}

public static void mergeSort(int[] arrays) {
  int[] temp = new int[arrays.length];

  mergeSort(arrays, 0, arrays.length - 1, temp);
}