基础的排序算法
2021-08-02 04:56
标签：频繁 最大的 array -- 简单 序列 两个指针 算法 元素 简单梳理一下以前学过的排序算法 冒泡排序 平均时间复杂度：O(n2)；稳定 比较相邻元素，如果前面的比后面大，就交换两个元素 每一对相邻元素做同样的比较，从开始第一对元素一直比到结尾，一轮结束最后的元素是最大的。 除了每轮比较出来的最大元素，对其他元素重复以上操作。 public void bubbleSort(int[] array) { for (int i = 0; i = 0 && current 0) { for (int i = gap; i = 0 && array[preIndex] > temp) { array[preIndex + gap] = array[preIndex]; preIndex -= gap; } array[preIndex + gap] = temp; } gap /= 2; } } 归并排序 分治法的典型应用。始终都是 O(nlogn) 的时间复杂度，代价是需要额外的内存空间。 平均时间复杂度：O(nlogn)；稳定 将长度为 n 的序列分成两个长度为 n/2 的子序列； 分别对子序列采用归并排序； 将两个排序好的子序列合并成一个有序序列； public void sort(int[] array) { //在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间 int[] temp = new int[array.length]; sort(array, 0, array.length - 1, temp); } public void sort(int[] array, int left, int right, int[] temp) { if (left