//放在一起感觉又臭又长,所以每排序我单独放出来了,欢迎大家平均交流指出不足

import java.lang.reflect.Array;

import java.util.*;
public class EightKindOfSort {
/*选择排序    (不稳定算法)
 * 基本思想:两个for循环嵌套,内部for循环用来找到最大(小)的元素,外部循环用来放置找到的元素
 * 复杂度:需要遍历数组才能找到峰值元素,所以复杂度与原始序列是否有序无关,最好最坏和平均情况的时间复杂度都为O(n^2);
 * 需要一个临时变量用来交换数组内数据位置,所以空间复杂度为O(1)
 */
public static void xuanZeSort(int[] a) { for (int i = 0; i < a.length - 1;
i++) { for (int j = i + 1; j < a.length; j++) { if (a[i] > a[j]) { int temp =
a[i]; a[i] = a[j]; a[j] = temp; } } } //j是a遍历出的每个元素,不是下标 for (int j : a) {
System.out.print(j + " "); } }

/*快速排序(不稳定算法)
 * 基本思想:选择数组任一数据作为k,依次从前向后 找到第一个比k大的元素,然后与k交换。
 *   从后向前找到第一个比k小的元素,然后与k交换,直到遍历一次,k恰好放到正确的位置
 *   然后在分别对k左和k右两部分进行快速排序
 *  外层是while循环,条件start<end  为一次遍历
 *  循环体两个while,一个从左到右找到第一个比k大的元素交换,条件是(start<end&&a[start]<=base)
 *  另一个从右到左找到第一个比k小的元素交换
 *  一次遍历之后把数组划分成两部分,然后一次递归;
 *  
 *  复杂度:简单来说,复杂度就是对数据的操作次数
 *  在最好和平均情况下,数据从中间划分成两部分,一个大小为n的数组需要划分Log2n次,即递归log2n次,
 *  一次对n级别个数据进行操作,所以时间复杂度为O(n*log2n)
 * 在最坏的情况下,每次都选到数组中的最大或者最小的元素,每次划分成n-1和1两部分,这样就需要递归n-1次,
 * 一次对n级别个数据进行操作,所以最坏的时间复杂度为O(n*2)
 *  快速排序的空间复杂度可以理解为递归的深度,而递归的实现依靠栈。
 *   已经说明平均需要递归log2n次,所以平均空间复杂度为O(log2n)
 * 
 */
 
public static void quickSort(int []a,int start ,int end) { if(start>=end)
return; else { int mid=quick(a,start,end); quickSort(a,start,mid-1);
quickSort(a,mid+1,end); } } public static int quick(int []a,int start ,int end)
{ int base =a[end]; while(start<end) { while(start<end&&a[start]<=base)
start++; if(start<end) { int temp=a[start]; a[start]=a[end]; a[end]=temp;
//end--; } while(start<end&&a[end]>=base) end--; if(start<end) { int
temp=a[start]; a[start]=a[end]; a[end]=temp; //start++; } } return end;

/*
* 冒泡排序:(稳定算法)
* 基本思想:冒泡排序属于比较简单的排序,以非递减为例,依次遍历数组,发现a[i]>a[i+1}的情况,swap(a[i],a[i+1])
* 直到没有逆序的数据,完成排序
* 可以用两个for循环嵌套实现,外层控制遍历次数,内层用来实现交换

* 也可以用一个boolean类型变量来控制是否有交换发生,如果没有交换,表明已经正序,可以直接输出

* 复杂度 分析:
* 很明显,冒泡排序最好情况是数组已经有序的情况,此时只需要遍历一次数据,没有交换发生,结束排序,时间复杂度为O(n)
* 那最坏情况下的冒泡就是逆序,此时你需要遍历n-1次数据,(数据为 3  2   1,一次遍历为2 1 3 ,二次遍历 1 2 3 结束  ),
* 此时的时间复杂度为O(n^2) 
* 平均情况下也为O(n^2) 需要注意的是平均情况并不是与最坏情况下的时间复杂度相等,
* 平均的时间复杂度=sum(Pi*f(n));Pi为每种情况出现的概率,计算起来有些困难,在这里直接用前辈的结果
* 空间复杂度:只需要一个temp临时变量来交换数据,所以O(1)


* Ps:冒泡排序在数组基本有序,只有零星逆序的情况下效率极高
*/
public static void bubbleSort1(int[] a){ for (int k = 1; k < a.length ; k++) {
for (int i = 0; i < a.length - k; ++i) { if (a[i] > a[i + 1]) { int temp =
a[i]; a[i] = a[i + 1]; a[i + 1] = temp; } } } } public static void
bubbleSort2(int[] a) { boolean bol = true; while (bol) { bol = false; for (int
i = 0; i < a.length - 1; ++i) { if (a[i] > a[i + 1]) { int temp = a[i]; a[i] =
a[i + 1]; a[i + 1] = temp; bol = true; } } } }

/*
* 直接插入排序(稳定算法)
* 基本思想:从第一个数开始,认定数组的前i个数有序,依次遍历数组,
* 把后面的数据插入到合适的位置,使数组继续保持有序
* 用两个for循环实现,外层i用来控制数组的数据量,内层用来找到a[i]需要插入的位置
* 如果temp大于a[j]则把a[j]向后移动
* 复杂度分析:
* 时间复杂度:最好情况是数组有序,依次把数据放到前一个数的后面   O(n)
* 最坏情况是数组逆序,遍历n次数组,每次都需要把n个数据向后移动  O(n^2)
* 平均情况      O(n)
* 空间复杂度:需要一个临时变量temp来存储即将插入的数 据   所以   O(1)

*/
public static void insertSort(int[] a) { for (int i = 1; i < a.length; ++i) {
int temp = a[i]; int j = i - 1; for (j = i - 1; j >= 0; --j) { if (temp < a[j])
{ a[j + 1] = a[j]; } else { break; } } a[j + 1] = temp; } }

/*
* shell排序(希尔排序)
* 基本思想:希尔排序选取一个增量h,也就是把整个数组分成h份,对每一份进行排序。
* 然后减少增量h,重复上述过程。
* 一般我们选取的递增序列为:3*h+1   即1,4,13,40,.....
* 实现:用一个while语句求出对应数组我们所需要的最大h
* 然后在用一个外层while循环控制h,每循环一次h=h/3;直至h自减至1;
* 内层是直接插入排序算法,两个for循环嵌套,外层for循环用来控制i  - a.length的自增
* 内层for循环用来找到i需要插入的位置。
* 复杂度分析:
* 时间复杂度:希尔排序最好情况是数组正序,此时外层for循环执行一次+最外层while循环<n次;内层for循环不执行,  O(n)
* 最坏情况是数组逆序,外层for循环+while<n次,内层for每次都需要把n个数据向后移动一位;   O(n^2)
* 平均情况:  O(n^1.3)  站在巨人的肩膀上看问题
* 空间复杂度:
* 需要一个temp用来临时交换数据,一个h来保存增量           O(1)


*/
public static void shellSort(int[] a) { int len = a.length; int h = 1; while
(h < len / 3) h = h * 3 + 1; while (h > 0) { for (int i = h; i < len; ++i) {
for (int j = i; j >= h; j = j - h) { if (a[j] < a[j - h]) { int temp = a[j];
a[j] = a[j - h]; a[j - h] = temp; } } } h = h / 3; } }

/*
* (二分)归并排序(稳定算法)
* 基本思想:将数组递归分成越来越小的数集,直到每个数集只有一个数
* 然后将数据递归排序,使其合并成与原来数据一样的有序序列
* 时间复杂度分析:递归分解数据,需要递归logN次,每次都需要对n个数据扫描一次,最好最坏平均都一样,所以O(nlogn)
* 空间复杂度分析:归并排序需要一个临时temp[]来储存归并的结果,所以   O(n) 

* 基本实现:需要两个函数,一个用来递归划分数组,比较简单,依次二分即可
* 一个用来把划分好的数组递归排序并合并:两个数组从第一个元素开始比较,小的数据入,直到一个数组中数据为空,
* 然后把另一个数组中的剩余数据写入,最后用temp数组替代初始的数组
*/
 
public static void merge ( int a[], int start, int mid, int end){ int[] temp
= new int[end - start + 1]; int i = start; int j = mid + 1; int k = 0; while (i
<= mid && j <= end) { if (a[i] < a[j]) { temp[k++] = a[i++]; } else { temp[k++]
= a[j++]; } while (i <= mid) { temp[k++] = a[i++]; } while (j <= end) {
temp[k++] = a[j++]; } for (int m = 0; m < temp.length; ++m) { a[start + m] =
temp[m]; } } } /** * @param a * @param start  数组索引 * @param end 数组索引,<.length
*/ public static void mergeSort ( int a[], int start, int end){ int mid = (end
+ start) / 2; // int mid=start+(end-start)/2; // System.out.println(mid); if
(start < end) { mergeSort(a, start, mid); mergeSort(a, mid + 1, end); merge(a,
start, mid, end); } }
 

技术
©2019-2020 Toolsou All rights reserved,
明明是post请求为什么会在地址栏显示参数?java中的编译时异常和运行时异常科幻成真!“三体”被发现了(精华2020年6月2日更新) TypeScript函数详解element-ui的el-date-picker组件获取值shiro-oauth 启用第三方认证登录PostgreSQL: 九. 索引PowerShell中使用WebClient 下载文件并获取下载进度airflow 定时任务+时间设定+cron表达式mysql 递归查找父类的所有子节点