Loading... ###**选择排序:每次循环选择一位最小的数值,与本次循环的头位交换,时间复杂度:**O(n^{2})**** ``` public static void selectSort(int[] array) { int length = array.length; for (int i = 0; i < length - 1; i++) { int minIndex = i; for (int j = i; j < length; j++) { //记录替换最小值 if (array[j] < array[minIndex]) { minIndex = j; } } //将最小值与头位替换,swap if (minIndex != i) { swap(array, i, minIndex); } } } ``` ###**插入排序:每次循环取当前数,与前面数依次比较,如果逆序。则交换位置。循环嵌套逆循环,时间复杂度:**O(n^{2})**** ``` public static void insertSort(int[] array) { int length = array.length; for (int i = 0; i < length; i++) { for (int j = i; j > 0; j--) { if (array[j] < array[j - 1]) { swap(array, j, j - 1); continue; } //如果没有进行交换,就证明前序数组已经有序,当前值也与前序数组有序. break; } } } ``` ###**冒泡排序:每次循环比较后一位和当前位大小,如果逆序则互换。两层循环,每层循环从0开始时间复杂度:**O(n^{2})**。** ``` public static void bubbleSort(int[] array) { int length = array.length; for (int i = 0; i < length; i++) { for (int j = 0; j < length - 1; j++) { if (array[j + 1] < array[j]) { swap(array, j, j + 1); } } } } ``` ###**快速排序:选择一个数作为基准数,将小于该数的放置左边,大于该数的放右边,对左右两边的数组再进行递归排序。时间复杂度:**O(nlogn)**** ``` /** * 交换排序:快速排序 * 1.选择end作为base,begin作为next_pivot * 2.遍历数组,如果当前值比base小,则交换next_pivot元素和当前的值.next_pivot++ * 3.遍历完成后,next_pivot位置以及右边的元素是>=base的,左边的元素都是是比base小的.那么只要交换next_pivot和base. * 就能达到next_pivot左边都是小的,右边都是大的. * 4.返回next_pivot作为下一次迭代的基准.分别将基准左侧和右侧的数组进行递归排序. * 也就是0,next_pivot-1和next_pivot+1,end 因为next_pivot是基准不需要再排序了. * * @param array 待排数组 * @param begin 起始位 * @param end 结束位 */ public static void quickSort(int[] array, int begin, int end) { if (end <= begin) { return; } int pivot = partition(array, begin, end); quickSort(array, begin, pivot - 1); quickSort(array, pivot + 1, end); } private static int partition(int[] array, int begin, int end) { int pivot = end, base = array[pivot]; int next_pivot = begin; for (int i = begin; i < end; i++) { //排序过程: //1 2 5 0 3 next_pivot: 2, i: 3 //1 2 0 5 3 next_pivot: 3, i: 4 //1 2 0 3 5 //1 2 0 3 next_pivot: 3, i: 3 //1 2 0 next_pivot: 0, i: 2 //0 2 1 //2 1 //1 2 //0 1 2 3 5 //如果i < pivot,那么就替换i和next_pivot的值 if (array[i] < base) { if (next_pivot != i) { int temp = array[next_pivot]; array[next_pivot] = array[i]; array[i] = temp; } next_pivot++; } } //替换pivot和next_pivot的值 array[pivot] = array[next_pivot]; array[next_pivot] = base; return next_pivot; } ``` ###**归并排序:分治思想,递归。将数组拆分两份,分别对这两份进行排序。再合并这两份排序的结果。时间复杂度:**O(nlogn)**** ``` /** * 交换算法:归并排序 * 分治思想: 递归.将数组拆分两分,分别对这两份进行排序.再合并这两份排序的结果. * @param array 待排序数组 * @param left 起始索引 * @param right 结束索引 */ public static void mergeSort(int[] array, int left, int right) { //right > left if(right <= left){ return; } //mid = (left + right) / 2 int mid = (left + right) >> 1; //对左边数组进行排序 mergeSort(array, left, mid); //对右边数组进行排序 mergeSort(array, mid + 1, right); //合并两个数组 merge(array, left, mid, right); } /** * 对两个有序的子数组进行合并 * @param array 待排序数组 * @param left 子数组1的起始索引 * @param mid 中间索引 * @param right 子数组2的结束索引 */ private static void merge(int[] array, int left, int mid, int right) { int[] temp = new int[right - left + 1]; int i = left, j = mid + 1, k = 0; //12356 & 23456 //比较array[i] 和 array[j]的值。谁小放谁,并自增. while (i <= mid && j <= right) { temp[k++] = array[i] <= array[j] ? array[i++] : array[j++]; } //temp已经是有序,但可能i没跑完或者j没跑完 while (i <= mid) { temp[k++] = array[i++]; } while (j <= right) { temp[k++] = array[j++]; } //temp是个完整的排序好的数组,需要拷贝回array数组 for (int p = 0; p < temp.length; p++) { array[left + p] = temp[p]; } } ``` ###**堆排序:数组元素依次建立小顶堆,将堆顶元素交换堆尾元素并取出。重新建立小顶堆。小顶堆堆顶永远是最小的,大顶堆堆顶永远是最大的。时间复杂度:**O(nlogn)**** ``` /** * 创建堆, * @param arr 待排序列 */ private static void heapSort(int[] arr) { //创建堆 for (int i = (arr.length - 1) / 2; i >= 0; i--) { //从第一个非叶子结点从下至上,从右至左调整结构 adjustHeap(arr, i, arr.length); } //调整堆结构+交换堆顶元素与末尾元素 for (int i = arr.length - 1; i > 0; i--) { //将堆顶元素与末尾元素进行交换 int temp = arr[i]; arr[i] = arr[0]; arr[0] = temp; //重新对堆进行调整 adjustHeap(arr, 0, i); } } /** * 调整堆 * @param arr 待排序列 * @param parent 父节点 * @param length 待排序列尾元素索引 */ private static void adjustHeap(int[] arr, int parent, int length) { //将temp作为父节点 int temp = arr[parent]; //左孩子 int lChild = 2 * parent + 1; while (lChild < length) { //右孩子 int rChild = lChild + 1; // 如果有右孩子结点,并且右孩子结点的值大于左孩子结点,则选取右孩子结点 if (rChild < length && arr[lChild] < arr[rChild]) { lChild++; } // 如果父结点的值已经大于孩子结点的值,则直接结束 if (temp >= arr[lChild]) { break; } // 把孩子结点的值赋给父结点 arr[parent] = arr[lChild]; //选取孩子结点的左孩子结点,继续向下筛选 parent = lChild; lChild = 2 * lChild + 1; } arr[parent] = temp; } ``` © Allow specification reprint Support Appreciate the author AliPayWeChat Like 0 If you think my article is useful to you, please feel free to appreciate