概述: 冒泡排序是一种简单直观的排序算法。它重复的走访要排序的数列,一次比较两个元素,按照一定的顺序,如果顺序错误就将他们交换过来。重复进行直到没有再需要交换,也就是该数组已经排序完成。这个算法名字的又来是因为越小的元素会经交换慢慢“浮”到数列的头部。
算法步骤
1.比较相邻的元素。如果第一个比第二个大,就进行交换
2.对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。做完这一步之后,最后一个元素就是最大的数
3.重复1 2 步骤,除了最后一个元素。对越来越少的元素重复上面的步骤,知道没有任何一对数字需要比较
public static void sort(int[] str) {
if (str == null || str.length == 0) {
return;
}
for (int i = 0; i < str.length; i++) {
for (int j = 0; j < str.length - 1 - i; j++) {
if (str[j] > str[j + 1]) {
int temp = str[j];
str[j] = str[j + 1];
str[j + 1] = temp;
}
}
}
}
时间复杂度
O(n^2)
概述: 选择排序也是一种简单直观的排序算法,无论什么数据进去都是O(n^2)的时间复杂度。所以使用选择排序时,数据规模越小越好。唯一的好处可能就是不占用额外的内存空间。
算法步骤
1.在未排序序列中找到最小(大)元素,存放到排序序列的起始位置
2.从剩余未排序元素中寻找最小(大)元素,然后放到已排序序列的末尾
3.重复第二步,直到所有元素均排序完毕
Java代码
public static void sort(int[] str){
if(str==null || str.length==0){
return;
}
for (int i = 0; i < str.length; i++) {
int min = i;
for (int j = i; j < str.length; j++) {
if(str[min]>str[j]){
min = j;
}
}
// 将最小值放在索引为i的位置
if(min!=i){
int temp = str[i];
str[i] = str[min];
str[min] = temp;
}
}
}
时间复杂度
O(n^2)
概述: 插入排序的代码实现起来虽然没有冒泡排序和选择排序那么简单粗暴,但它的原理是最容易理解的,插入排序的原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。
算法步骤
将待排序序列第一个元素看成一个有序序列,将第二个元素到最后一个元素看成未排序的序列。从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置。(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面)
Java代码
public static void sort(int[] str) {
for (int i = 1; i < str.length; i++) {
int temp = str[i];
int j = i - 1;
while (j >= 0) {
if (str[j] > temp) {
str[j + 1] = str[j];
j--;
} else {
break;
}
}
str[j + 1] = temp;
}
}
概述: 希尔排序也称递减增量排序算法,是插入排序的一种更高效的改进版本。但是希尔排序是不是很稳定。
算法步骤
选择一个增量序列t1,t2,…tn 其中tn=1
按照增量序列个数n,对序列进行k趟排序,每趟排序将这些子序列用插入排序进行排序知道当增量因子为1时,整个序列作为一个序列处理
Java代码
public static void sort(int[] str) {
if (str == null || str.length == 0) {
return;
}
for (int temp = str.length / 2; temp >= 1; temp /= 2) {
for (int i = temp; i < str.length; i++) {
int flag = str[i];
int j = i - temp;
while (j >= 0) {
if (str[j] > flag) {
str[j + temp] = str[j];
j -= temp;
} else {
break;
}
}
str[j + temp] = flag;
}
}
}
概述: 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。
算法步骤
1.申请空间,使其大小为两个已经排序的序列之和,该空间用来存放合并后的序列
2.设定两个指针,最初位置分别为两个已经排序序列的起始位置
3.比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
4.重复步骤3知道某一指针到达序列尾
5.将另一序列所剩下的所有元素直接复制到合并序列尾
Java代码
public static int[] sort(int[] str) {
if (str == null || str.length < 2) {
return str;
}
int middle = str.length / 2;
int[] left = Arrays.copyOfRange(str, 0, middle);
int[] right = Arrays.copyOfRange(str, middle, str.length);
return merge(sort(left), sort(right));
}
public static int[] merge(int[] left, int[] right) {
int[] result = new int[left.length + right.length];
int i = 0;
int m = 0;
int n = 0;
while (m < left.length && n < right.length) {
if (left[m] < right[n]) {
result[i++] = left[m++];
} else {
result[i++] = right[n++];
}
}
while (m < left.length) {
result[i++] = left[m++];
}
while (n < right.length) {
result[i++] = right[n++];
}
return result;
}
概述: 快速排序的最坏运行情况是O(n^2),比如说顺序数列的快排,但它的平摊期望时间是O(nlogn), 且O(nlogn)记号中隐含的常数因子很小,比复杂度稳定等于O(nlogn)的归并排序要小很多。所以,对绝大多数顺序性较弱的随机数列而言,快速排序总是优于归并排序。
算法步骤
1.从数列中挑出一个元素,称为“基准”(pivot)
2.重新排列数列,所有比基准值小的摆放在基准前面,所有元素比基准值大的把放在后面,相同的数可以放任一边。在这个分区退出之后,该基准就处于数列的中间位置,这个称为分区(partition)操作
3.递归的(recursive)把小于基准值的元素的子数列和大于基准值元素的子数列排序
Java代码
public static void sort(int[] str, int left, int right) {
// 递归到底的情况
if (left >= right) {
return;
}
// 递归操作
int pivot = str[left];
int i = left;
int j = right;
while (i < j) {
// 从右边开始找第一个小于pivot的元素
while (i < j && str[j] > pivot) {
j--;
}
// 替换
if (i < j) {
str[i] = str[j];
i++;
}
// 从左边开始找到第一个比pivot大的元素、
while (i < j && str[i] < pivot){
i++;
}
// 替换
if(i<j){
str[j] = str[i];
j--;
}
}
str[i] = pivot;
sort(str, left, i-1);
sort(str, i+1, right);
}
数据结构之堆的概念:
概述: 堆排序就是利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或大于)它的父结点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法:
算法步骤
1.构建一个堆(将完全二叉树整理成堆)
2.把堆首(最大值)和堆尾互换(下沉操作)
3.调用shift down方法,使除过堆尾元素的树满足最大堆的性质
4.重复步骤2,直到堆中只有一个元素
Java代码
public static void sort(int str[]) {
if (str == null || str.length == 0) {
return;
}
// 构建堆,将完全二叉树整理成堆
heapify(str);
// 排序
for (int i = 0; i < str.length-1; i++) {
// 将首位元素替换
int temp = str[0];
str[0] = str[i];
str[i] = temp;
// 整理成堆
siftDown(0, str, i);
}
}
public static void heapify(int[] str) {
// 找到最后一个元素的父亲结点
int parentIndex = getParentIndex(str.length - 1);
// 从最后一个元素的父亲结点开始进行下沉操作,直到根结点
for (; parentIndex >= 0; parentIndex--) {
siftDown(parentIndex, str, str.length);
}
}
// 获取堆的根结点,根结点一般都是最中间
public static int getParentIndex(int index) {
if (index < 0) {
throw new IllegalArgumentException("index is invalid!");
}
if (index == 0) {
// 处理根结点
return -1;
}
return (index - 1) / 2;
}
// 根据当前数组所在的索引获取左孩子结点的索引
private static int getLeftChileIndex(int index) {
return index * 2 + 1;
}
// 下沉操作
private static void siftDown(int curIndex, int[] str, int length) {
int leftChildIndex = getLeftChileIndex(curIndex);
int changeIndex = leftChildIndex;
while (leftChildIndex < length) {
int rightChildIndex = leftChildIndex + 1;
if (rightChildIndex < length && str[rightChildIndex] > str[leftChildIndex]) {
changeIndex = rightChildIndex;
}
if(str[changeIndex]>str[curIndex]){
// 交换操作
int temp = str[curIndex];
str[curIndex] = str[changeIndex];
str[changeIndex] = temp;
curIndex = changeIndex;
leftChildIndex = getLeftChileIndex(curIndex);
changeIndex = leftChildIndex;
}else{
break;
}
}
}
时间复杂度
O(nlogn)
概述: 计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数。
特点: 计数排序不是比较排序,排序的速度快于任何比较排序算法。由于用来计数的数组的长度取决于待排序数组中数据的范围(等于待排序数组的最大值与最小值的差加上1),这使得计数排序对于数据范围很大的数组,需要大量时间和内存。
算法步骤
1.找出待排序的数组中最大和最小的元素
2.统计数组中每个值为i的元素出现的次数,存入数组的第i项
3.对所有的计数累加
4.反向填充目标数组
Java代码
// 辅助函数,查找数组最大值
private static int getMaxVal(int[] str) {
int max = str[0];
for (int i = 0; i < str.length; i++) {
max = Math.max(max, str[i]);
}
return max;
}
public static void sort(int[] str) {
if (str == null || str.length == 0) {
return;
}
// 获取数组中最大的值
int maxVal = getMaxVal(str);
// 创建一个数组用来计数
int[] counts = new int[maxVal + 1];
// 计数
for (int i = 0; i < str.length; i++) {
counts[str[i]]++;
}
// 反向填充
int index = 0;
for (int i = 0; i < counts.length; i++) {
while (counts[i] > 0) {
str[index++] = i;
counts[i]--;
}
}
}
时间复杂度
当输入的元素是n个0到k之间的整数时,运行时间为O(n+k)
概述: 桶排序是计数排序的升级版。它利用了函数的映射关系,高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效,我们需要做到这两点:
算法步骤
1.创建容器(桶)
2.初始化桶
3.将数据放入桶内
4.分别对每个桶进行排序
5.将桶中的元素反向填充到数组中
Java代码
public static void sort(int[] str) {
if (str == null || str.length == 0) {
return;
}
// 创建桶
List<Integer>[] buckets = new ArrayList[10];
// 初始化桶
for (int i = 0; i < buckets.length; i++) {
buckets[i] = new ArrayList<>();
}
// 将数据放入桶中
for (int i = 0; i < str.length; i++) {
int index = str[i] / 10;
buckets[index].add(str[i]);
}
// 分别对每个桶进行排序
for (int i = 0; i < buckets.length; i++) {
buckets[i].sort(null);
}
// 将桶中的数据反向填充到str中
int index = 0;
for (int i = 0; i < buckets.length; i++) {
List<Integer> item = buckets[i];
while (!item.isEmpty()) {
str[index++] = item.remove(0);
}
}
}
概述: 基数排序原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。基数排序的方式可以采用LSD或MSD,LSD的排序方式由键值的最右边开始,而MSD则相反,由键值的最左边开始。
算法步骤
1.从数组中选出最大数和最大数的位数
2.根据位数进行循环
3.每次循环获取数组中每个数的最后一位,然后将其数字放入相应的桶中
4.对桶中的元素进行排序
5.然后将桶中的数反向输出到原数组中
Java代码
public static void sort(int[] str) {
if (str == null || str.length == 0) {
return;
}
// 获取最大值
int maxValue = getMaxVal(str);
// 获取最大位数
int maxDigit = getMaxDigit(maxValue);
radixSort(str, maxDigit);
}
private static void radixSort(int[] str, int maxDigit) {
int mod = 1;
// 创建桶
List<Integer>[] buckets = new ArrayList[10];
// 对桶进行初始化
for (int i = 0; i < buckets.length; i++) {
buckets[i] = new ArrayList<>();
}
// 将相应的尾数的数字放入对应的桶中
for (int i = 0; i < str.length; i++) {
int bucketIndex = (str[i] / mod) % 10;
buckets[bucketIndex].add(str[i]);
}
// 对桶进行排序,分别对每个桶进行排序
for (int i = 0; i < buckets.length; i++) {
buckets[i].sort(null);
}
// 将桶中的元素反向填充到str中
int index = 0;
for (int i = 0; i < buckets.length; i++) {
while (!buckets[i].isEmpty()){
str[index++] = buckets[i].remove(0);
}
}
}
private static int getMaxDigit(int maxValue) {
int max = 0;
while (maxValue > 0) {
max++;
maxValue /= 10;
}
return max;
}
private static int getMaxVal(int[] str) {
int max = str[0];
for (int i = 0; i < str.length; i++) {
max = Math.max(max, str[i]);
}
return max;
}
文章浏览阅读2.5w次,点赞6次,收藏50次。官方解释是,docker 容器是机器上的沙盒进程,它与主机上的所有其他进程隔离。所以容器只是操作系统中被隔离开来的一个进程,所谓的容器化,其实也只是对操作系统进行欺骗的一种语法糖。_docker菜鸟教程
文章浏览阅读5.7k次,点赞3次,收藏14次。该如何避免的,今天小编给大家推荐两个下载Windows系统官方软件的资源网站,可以杜绝软件捆绑等行为。该站提供了丰富的Windows官方技术资源,比较重要的有MSDN技术资源文档库、官方工具和资源、应用程序、开发人员工具(Visual Studio 、SQLServer等等)、系统镜像、设计人员工具等。总的来说,这两个都是非常优秀的Windows系统镜像资源站,提供了丰富的Windows系统镜像资源,并且保证了资源的纯净和安全性,有需要的朋友可以去了解一下。这个非常实用的资源网站的创建者是国内的一个网友。_msdn我告诉你
文章浏览阅读1.2k次。vue2封装对话框el-dialog组件_
文章浏览阅读4.7k次,点赞5次,收藏6次。MFC 文本框换行 标签: it mfc 文本框1.将Multiline属性设置为True2.换行是使用"\r\n" (宽字符串为L"\r\n")3.如果需要编辑并且按Enter键换行,还要将 Want Return 设置为 True4.如果需要垂直滚动条的话将Vertical Scroll属性设置为True,需要水平滚动条的话将Horizontal Scroll属性设_c++ mfc同一框内输入二行怎么换行
文章浏览阅读832次。检查Linux是否是否开启所需端口,默认为6379,若未打开,将其开启:以root用户执行iptables -I INPUT -p tcp --dport 6379 -j ACCEPT如果还是未能解决,修改redis.conf,修改主机地址:bind 192.168.85.**;然后使用该配置文件,重新启动Redis服务./redis-server redis.conf..._redis-server doesn't support auth command or ismisconfigured. try
文章浏览阅读4.9k次。济大数电实验报告_数据选择器及其应用
文章浏览阅读236次。1研究内容消费在生产中占据十分重要的地位,是生产的最终目的和动力,是保持省内经济稳定快速发展的核心要素。预测河南省社会消费品零售总额,是进行宏观经济调控和消费体制改变创新的基础,是河南省内人民对美好的全面和谐社会的追求的要求,保持河南省经济稳定和可持续发展具有重要意义。本文建立灰色预测模型,利用MATLAB软件,预测出2019年~2023年河南省社会消费品零售总额预测值分别为21881...._灰色预测模型用什么软件
文章浏览阅读1.2k次。12.4-在Qt中使用Log4Qt输出Log文件,看这一篇就足够了一、为啥要使用第三方Log库,而不用平台自带的Log库二、Log4j系列库的功能介绍与基本概念三、Log4Qt库的基本介绍四、将Log4qt组装成为一个单独模块五、使用配置文件的方式配置Log4Qt六、使用代码的方式配置Log4Qt七、在Qt工程中引入Log4Qt库模块的方法八、获取示例中的源代码一、为啥要使用第三方Log库,而不用平台自带的Log库首先要说明的是,在平时开发和调试中开发平台自带的“打印输出”已经足够了。但_log4qt
文章浏览阅读786次。全局观思维模型,一个教我们由点到线,由线到面,再由面到体,不断的放大格局去思考问题的思维模型。_计算机中对于全局观的
文章浏览阅读330次。一、CountDownLatch介绍CountDownLatch采用减法计算;是一个同步辅助工具类和CyclicBarrier类功能类似,允许一个或多个线程等待,直到在其他线程中执行的一组操作完成。二、CountDownLatch俩种应用场景: 场景一:所有线程在等待开始信号(startSignal.await()),主流程发出开始信号通知,既执行startSignal.countDown()方法后;所有线程才开始执行;每个线程执行完发出做完信号,既执行do..._countdownluach于cyclicbarrier的用法
文章浏览阅读508次。Prometheus 算是一个全能型选手,原生支持容器监控,当然监控传统应用也不是吃干饭的,所以就是容器和非容器他都支持,所有的监控系统都具备这个流程,_-自动化监控系统prometheus&grafana实战
文章浏览阅读4.7k次。输入关键字,可以通过键盘的搜索按钮完成搜索功能。_react search