网站开发费用如何入帐,网络营销效果评估的作用有哪些,广告公司简介ppt范本,检测WordPress主题的网站文章目录 前言冒泡排序快速排序归并排序 前言
冒泡 快排 归并#xff0c;这三种排序算法太过经典#xff0c;但又很容易忘了。虽然一开始接触雀氏这些算法雀氏有些头大#xff0c;但时间长了也还好。主要是回忆这些算法干了啥很耗时间。
如果在笔试时要写一个o(nlogn)的… 文章目录 前言冒泡排序快速排序归并排序 前言
冒泡 快排 归并这三种排序算法太过经典但又很容易忘了。虽然一开始接触雀氏这些算法雀氏有些头大但时间长了也还好。主要是回忆这些算法干了啥很耗时间。
如果在笔试时要写一个o(nlogn)的排序算法如果不能立刻写出 快排或者归并未免有些太浪费时间了。
故写这篇文章用于记录 tip: 一下内容均实现升序排序 冒泡排序
所谓冒泡就是每一轮都排出一个最大的元素把他丢在末尾。 如上图所示5个元素的数组我们需要5轮遍历每次遍历可以排出一个当前遍历区域内最大的元素
而确定最大元素的方法起始也很简单。每一次遍历我们都和其前一个元素对比也就是比较arr[j - 1]arr[j]。如果 arr[j - 1] arr[j]则交换否则不变。这样的比较方式让算法趋向于将大的元素向右边送直到将最大的元素送到最右侧
当第一轮排序完成后第二轮排序的范围则被缩小。因为已知最大元素在最右侧那么无需遍历最右侧元素。
第三轮同理无需遍历倒数第二个元素。以此类推
import java.util.*;public class Main {public static void main(String[] args) {// 冒泡int N;Scanner sc new Scanner(System.in);N sc.nextInt();int[] arr new int[N];for (int i 0; i N; i) {arr[i] sc.nextInt();}// sort 核心for (int i 0; i N; i) {for (int j 1; j N - i; j) {if (arr[j - 1] arr[j]) {int tmp arr[j];arr[j] arr[j - 1];arr[j - 1] tmp;}}}// printfor (int i 0; i N; i) {System.out.print(arr[i]);if (i N - 1) System.out.print( );}}
}快速排序
所谓快速排序和俄罗斯套娃很像。我们想要快速排序俄罗斯套娃可以做如下操作
选出一个基准娃遍历所有娃小的放左边大的放右边如果两侧的娃不用排序则终止对基准娃左右两侧的娃娃们做123操作
快排也是类似的 不同的是俄罗斯套娃是将别的元素摆放到基准娃的两侧快排是通过交换左右两侧元素定位到base的位置
import java.util.*;public class Main {public static void main(String[] args) {Scanner sc new Scanner(System.in);int N sc.nextInt();int[] arr new int[N];for (int i 0; i N; i) {arr[i] sc.nextInt();}// quickSortquickSort(arr, 0, N - 1);// printfor (int i 0; i N; i) {System.out.print(arr[i]);if (i N - 1) System.out.print( );}}public static void quickSort(int[] arr, int lef, int rig) {if (lef rig) return;int base arr[lef];int lp lef, rp rig;while (lp rp) {// 右指针寻找到base的数for (; rp lp arr[rp] base; --rp);arr[lp] arr[rp];// 左指针寻找到base的数for (; rp lp arr[lp] base; lp);arr[rp] arr[lp];}arr[lp] base;quickSort(arr, lef, lp - 1);quickSort(arr, lp 1, rig);}
}tip: 快排有一些注意点需要强调 递归终止条件快排起始也是递归是递归就需要终止条件。本题递归的终止条件就是lef rig排序范围左侧端点不在右侧端点左边for (; rp lp arr[rp] base; --rp); 这个for相当于右侧小人寻找 小于 base的数。因为是寻找小于因此循环条件是 base就一直寻找如果base是数组第一个元素那么先走动的必须是右侧小人。因为数组最左侧元素我们用base进行备份先走右侧小人覆盖最左侧元素不会丢失base信息 归并排序
归并排序就有点蛋疼了虽然代码极少相对来说但思维量如果不熟悉分治的情况下还是比较大的。
本文并非专业的介绍文章感兴趣的读者可以详细阅读这篇文章
归并排序大致思路如下
往死里拆分数组具体拆分的方式就是对半拆当拆分到不能再拆局部合并
其中mergeSort干的任务是对lef ~ right范围内的数组归并排序merge属于归并排序中并的部分。
因为递归的原因上层递归栈merge数组以mid为临界区域left ~ midmid 1 ~ right这两段数组内部元素都是局部递增的。这个原因很简单因为递归的特性回溯到上层栈底层栈一定把功能实现好。
这有点类似于甩锅我排序全部数组太累了于是找两个小弟一个归并排序左边一个排序右边。我不许用关心小弟怎么排序我只需要知道等小弟回来回溯我就只需要排序两个有序数组
所以要实现merge的功能起始就是对两段有序数组进行排序
假设两段数组分别是arr1, arr2实际上只有arr为了方便叙述我们说成两段具体的排法是双指针遍历。
对于arr1, arr2。谁的元素大谁就把元素按序存储到tmp中。
import java.util.*;public class Main {private static int[] tmp;public static void main(String[] args) {Scanner sc new Scanner(System.in);int N sc.nextInt();int[] arr new int[N];tmp new int[N];for (int i 0; i N; i) {arr[i] sc.nextInt();}// mergemergeSort(arr, 0, N - 1);// printfor (int i 0; i N; i) {System.out.print(arr[i]);if (i N - 1)System.out.print( );}sc.close();}public 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);}}public static void merge(int[] arr, int left, int right) {int mid (left right) / 2; int lp left, rp mid 1, k left;while (lp mid rp right) {if (arr[lp] arr[rp]) tmp[left] arr[lp];else tmp[left] arr[rp]; }while (lp mid) tmp[left] arr[lp]; // 左区间没迭代完while (rp right) tmp[left] arr[rp]; // 右区间没迭代完for (; k right; k) arr[k] tmp[k]; // copy}
}另外值得一提的是归并是上述三种排序中最快的。冒泡快排都没有AC
