全球最大购物网站,山东网站备案注销,线上广告平台,登录浙江省建设信息港冒泡排序 算法步骤 不断的两两比较#xff0c;这样当前最大的元素总是会排在最后面。所以称为冒泡。 图解算法 代码实现 public static int[] bubbleSort(int[] arr) {// i是排好了几个数for (int i 1; i arr.length; i) {// flag标记当前循环是否调整了顺序#xff0c… 冒泡排序 算法步骤 不断的两两比较这样当前最大的元素总是会排在最后面。所以称为冒泡。 图解算法 代码实现
public static int[] bubbleSort(int[] arr) {// i是排好了几个数for (int i 1; i arr.length; i) {// flag标记当前循环是否调整了顺序如果没有调整说明排序完成boolean flag true;// arr.length - i控制数组尾巴for (int j 0; j arr.length - i; j) {if (arr[j] arr[j 1]) {int tmp arr[j];arr[j] arr[j 1];arr[j 1] tmp;flag false;}}if (flag) {break;}}return arr;
}算法分析 稳定性稳定 时间复杂度最佳 O ( n ) O(n) O(n) 最差 O ( n 2 ) O(n^2) O(n2) 平均 O ( n 2 ) O(n^2) O(n2) 空间复杂度 O ( 1 ) O(1) O(1) 排序方式内部排序 选择排序 算法步骤 不断地选择最小/最大的元素和当前未排序序列的头进行交换 图解算法 代码实现 public static int[] selectionSort(int[] arr) {// 找到的元素放到第i个未排序序列头for (int i 0; i arr.length - 1; i) {// minIndex记录当前未排序的最小元素的索引int minIndex i;for (int j i 1; j arr.length; j) {if (arr[j] arr[minIndex]) {minIndex j;}}// 交换if (minIndex ! i) {int tmp arr[i];arr[i] arr[minIndex];arr[minIndex] tmp;}}return arr;
}算法分析 稳定性不稳定 时间复杂度最佳 O ( n 2 ) O(n^2) O(n2) 最差 O ( n 2 ) O(n^2) O(n2) 平均 O ( n 2 ) O(n^2) O(n2) 空间复杂度 O ( 1 ) O(1) O(1) 排序方式内部排序 插入排序 算法步骤 就是扑克牌理牌。从前往后读取未排列序列的元素拿到新元素后从后往前遍历已排序序列找到合适的位置插入。 图解算法 代码实现 public static int[] insertionSort(int[] arr) {for (int i 1; i arr.length; i) {// preindex记录已排序序列的尾int preIndex i - 1;// current是当前要插入的元素int current arr[i];while (preIndex 0 current arr[preIndex]) {// 往后移arr[preIndex 1] arr[preIndex];preIndex - 1;}arr[preIndex 1] current;}return arr;
}算法分析 稳定性稳定 时间复杂度最佳 O ( n ) O(n) O(n) 最差 O ( n 2 ) O(n^2) O(n2) 平均 O ( n 2 ) O(n^2) O(n2) 空间复杂度 O ( 1 ) O(1) O(1) 排序方式内部排序 希尔排序 算法步骤 不断的按照增量来分出子数组的数量子数组内部进行插入排序然后缩小增量减少分子数组的数量然后接着插入排序直到增量为1之后再进行一次插入排序即可。 算法图解 代码实现 public static int[] shellSort(int[] arr) {int n arr.length;int gap n / 2;while (gap 0) {for (int i gap; i n; i) {int current arr[i];int preIndex i - gap;// 插入排序while (preIndex 0 arr[preIndex] current) {arr[preIndex gap] arr[preIndex];preIndex - gap;}arr[preIndex gap] current;}gap / 2;}return arr;
}算法分析 稳定性不稳定 时间复杂度最佳 O ( n l o g n ) O(nlogn) O(nlogn) 最差 O ( n 2 ) O(n^2) O(n2) 平均 O ( n l o g n ) O(nlogn) O(nlogn) 空间复杂度 O ( 1 ) O(1) O(1) 排序方式内部排序 归并排序 算法步骤 将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。 就是让子数列内部有序然后让两个子序列段间有序不断重复直到整个序列有序。 图解算法 代码实现 public static int[] mergeSort(int[] arr) {if (arr.length 1) {return arr;}int middle arr.length / 2;int[] arr_1 Arrays.copyOfRange(arr, 0, middle);int[] arr_2 Arrays.copyOfRange(arr, middle, arr.length);return merge(mergeSort(arr_1), mergeSort(arr_2));
}public static int[] merge(int[] arr_1, int[] arr_2) {int[] sorted_arr new int[arr_1.length arr_2.length];int idx 0, idx_1 0, idx_2 0;while (idx_1 arr_1.length idx_2 arr_2.length) {if (arr_1[idx_1] arr_2[idx_2]) {sorted_arr[idx] arr_1[idx_1];idx_1 1;} else {sorted_arr[idx] arr_2[idx_2];idx_2 1;}idx 1;}if (idx_1 arr_1.length) {while (idx_1 arr_1.length) {sorted_arr[idx] arr_1[idx_1];idx_1 1;idx 1;}} else {while (idx_2 arr_2.length) {sorted_arr[idx] arr_2[idx_2];idx_2 1;idx 1;}}return sorted_arr;
}算法分析 稳定性稳定 时间复杂度最佳 O ( n l o g n ) O(nlogn) O(nlogn) 最差 O ( n l o g n ) O(nlogn) O(nlogn) 平均 O ( n l o g n ) O(nlogn) O(nlogn) 空间复杂度 O ( n ) O(n) O(n) 排序方式外部排序 快速排序 算法步骤 从序列中随机挑出一个元素做为 基准通过一趟排序将待排序列分隔成独立的两部分比基准小的在左边比基准大的在右边则可分别对这两部分子序列继续进行排序以达到整个序列有序。 图解算法 代码实现 public static int partition(int[] array, int low, int high) {int pivot array[high];int pointer low;for (int i low; i high; i) {if (array[i] pivot) {int temp array[i];array[i] array[pointer];array[pointer] temp;pointer;}System.out.println(Arrays.toString(array));}int temp array[pointer];array[pointer] array[high];array[high] temp;return pointer;
}
public static void quickSort(int[] array, int low, int high) {if (low high) {int position partition(array, low, high);quickSort(array, low, position - 1);quickSort(array, position 1, high);}
}算法分析 稳定性不稳定 时间复杂度最佳 O ( n l o g n ) O(nlogn) O(nlogn) 最差 O ( n 2 ) O(n^2) O(n2)平均 O ( n l o g n ) O(nlogn) O(nlogn) 空间复杂度 O ( l o g n ) O(logn) O(logn) 排序方式内部排序 堆排序 算法步骤 堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构并同时满足堆的性质即子结点的值总是小于或者大于它的父节点。 图解算法 算法分析 稳定性不稳定 时间复杂度最佳 O ( n l o g n ) O(nlogn) O(nlogn) 最差 O ( n l o g n ) O(nlogn) O(nlogn) 平均 O ( n l o g n ) O(nlogn) O(nlogn) 空间复杂度 O ( 1 ) O(1) O(1) 排序方式内部排序 计数排序 算法步骤
