冒泡排序
/** * 从后往前，不断向前比较，小的向前面浮起来（交换） * 如果发现一趟排序没有交换，那么flag=false，程序就提前退出了 * 时间复杂度O(n^2) */private static int[] bubbleSort(int[] arr) { boolean flag = true; for (int i = 0; i < arr.length && flag; i++) { flag = false; for (int j = arr.length - 1; j > i; j--) { if (arr[j] < arr[j - 1]) { int temp = arr[j]; arr[j] = arr[j - 1]; arr[j - 1] = temp; flag = true; } } } return arr;}复制代码 插入排序
/** * 基本思想：在要排序的一组数中，假设前面n-1个数已经是排好顺序的， * 把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。如此反复循环。 * 时间复杂度O(n^2) */private static int[] insertSort(int[] arr) { for (int i = 1; i < arr.length; i++) { if (arr[i] < arr[i - 1]) { //假设下标i前面的数已经排好序，把当前下标i的元素插入到前面 //具体插入位置：如果前面的元素比下标i的元素小，不断向前覆盖一格 //最后把下标i的元素插入到正确位置 int temp = arr[i]; int j = i - 1; for (; j >= 0 && arr[j] > temp; j--) { arr[j + 1] = arr[j]; } arr[j + 1] = temp; } } return arr;}复制代码 选择排序
/** * 选择排序的思想是，先假设一个为最小，然后用剩下的元素去比较 * 如果发现有比假设值小的，先把下标记录下来，最后再进行交换 * 时间复杂度O(n^2) */private static int[] selectSort(int[] arr) { for (int i = 0; i < arr.length - 1; i++) { int min = i;//先选择一个最小的，然后用其他去跟这个比较，直到找到最小的那个为止 for (int j = i + 1; j < arr.length; j++) { if (arr[j] < arr[min]) { //先记录下来，最后再交换 min = j; } } if (min != i) { int temp = arr[min]; arr[min] = arr[i]; arr[i] = temp; } } return arr;}复制代码 快速排序
/** * 快速排序 * 时间复杂度O(n * log(n)) * 优化方式：1三数取中 2优化不必要的交换 3小数组的方案 4尾递归优化 * * @return 返回排序后的数组 */private static void quickSort(int[] arr, int low, int high) { if (low < high) { //计算基准点 int pivot = partition(arr, low, high); //分别对基准点左右两边进行递归 quickSort(arr, low, pivot - 1); quickSort(arr, pivot + 1, high); }}private static int partition(int[] arr, int low, int high) { int pivotKey = arr[low]; while (low < high) { while (low < high && arr[high] >= pivotKey) { high--; } System.out.println("交换" + low + ":" + high); swap(arr, low, high); System.out.println(Arrays.toString(arr)); while (low < high && arr[low] <= pivotKey) { low++; } swap(arr, low, high); } return low;}复制代码 希尔排序
/** * 希尔排序，元素的分组跳跃式排序 * 直接插入排序的改版 * 时间复杂度O(n * log(n)) */private static int[] shellSort(int[] arr) { int inc = arr.length; do { inc = inc / 3 + 1; for (int i = inc; i < arr.length; i++) { if (arr[i] < arr[i - inc]) { int temp = arr[i]; int j = i - inc; for (; j >= 0 && arr[j] > temp; j = j - inc) { arr[j + inc] = arr[j]; } arr[j + inc] = temp; } } } while (inc > 1); return arr;}复制代码 归并排序
/** * 归并排序 * 时间复杂度O(n * log(n)) */private static void mergeSort(int[] arr, int left, int right) { if (left < right) { //数组拆分 int mid = (left + right) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); //拆到不能再拆的时候，开始合并 merge(arr, left, right); }}private static void merge(int[] arr, int left, int right) { int[] temp = new int[arr.length]; int mid = (left + right) / 2; int i = left; int j = mid; int k = left; //逐一比较大小，把小的存到临时数组里面 while (i < mid && j < right) { if (arr[i] < arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; } } //把剩下的元素写进去 while (i < mid) { temp[k++] = arr[i++]; } while (j < right) { temp[k++] = arr[j++]; } //把临时数组的内容拷贝回去 int l = left; while (l < right) { arr[l] = temp[l]; l++; }}复制代码 堆排序
/** * 堆排序是通过不断构造大顶堆 * 时间复杂度O(n * log(n)) */private static int[] heapSort(int[] arr) { int len = arr.length - 1; //从下往上，从右往左构建大顶堆 for (int i = len / 2; i > 0; i--) { adjust(arr, i, len); } for (int i = len; i > 1; i--) { //交换最后一个元素与大顶堆的根结点 int temp = arr[i]; arr[i] = arr[1]; arr[1] = temp; adjust(arr, 1, i - 1); } return arr;}private static void adjust(int[] arr, int s, int m) { int temp = arr[s]; for (int i = s * 2; i <= m; i = i * 2) { //判断左右子结点哪个大 if (i < m && arr[i] < arr[i + 1]) { i++; } //如果当前的双亲结点是最大的那个，那么不用继续调整 if (temp >= arr[i]) { break; } //把当前左右结点中的最大值赋值给双亲结点 arr[s] = arr[i]; //以当前最大结点为双亲结点，继续下一次循环，直到找到 //temp应该存放的位置为止 s = i; } //找到temp应该存放的位置 arr[s] = temp;}复制代码 如果觉得我的文字对你有所帮助的话，欢迎关注我的公众号：
我的群欢迎大家进来探讨各种技术与非技术的话题，有兴趣的朋友们加我私人微信huannan88，我拉你进群交（♂）流（♀）。