<>交换排序

<>冒泡排序

原理:在无序区间,通过相邻数的比较,将最大的数冒泡到无序区间的最后,持续这个过程,直到数组整体有序。

实现:
public static void bubbleSort(int[] array){ for(int i=0;i<array.length-1;i++){
boolean isSorted=true; for(int j=0;j<array.length-i-1;j++){ //相等不交换,确保稳定性 if(
array[i]>array[j+1]){ swap(array,j,j+1); isSorted=fasle; } } if(isSorted){ break
; } } }
性能分析

稳定性: 稳定

<>快速排序(重要)

原理:

* 从待排序区间选择一个数,作为基准值(pivot);
* Partition: 遍历整个待排序区间,将比基准值小的(可以包含相等的)放到基准值的左边,将比基准值大的(可以包含相等的)放到基准值的右边;
* 采用分治思想,对左右两个小区间按照同样的方式处理,直到小区间的长度 == 1,代表已经有序,或者小区间的长度 == 0,代表没有数据。
实现:
public static void quickSort(int[] array) { quickSortInternal(array, 0, array.
length- 1); } //[left,right]为待排序区间 private static void quickSortInternal(int[]
array, int left,int right){ if(left==right) { return; } if(left>right){ return;
} //最简单的选择基准值的方式,选择array【left】作为基准值 //pivoIndex代表基准值最终停留的下标 int pivoIndex=
partition(array,left,right); //[left,pivoIndex-1]都是小于等于基准值的
//[piovIndex+1,right]都是大于等于基准值的 quickSortInternal(array, left,pivoIndex-1);
quickSortInternal(array,pivoIndex+1,right); }
原理-partition

实现:
private static int partition(int[] array,int left,int right){ int i=left; int j
=right; int pivot=array[left]; while(i<j){ while(i<j&&array[j]>=pivot){ j--; }
while(i<j&&array[i]<=pivot){ i++; } swap(array,i,j); } swap(array,i,left);
return 1; }
挖坑法:
基本思路和Hoare法一致,只是不再进行交换,而是进行赋值(填坑+挖坑)

实现:
private static int partition(int[] array,int left,int right){ int i=left; int j
=right; int pivot=array[left]; while(i<j){ while(i<j&&array[j]>=pivot){ j--; }
array[i]=array[j]; while(i<j&&array[i]<=pivot){ i++; } array[j]=array[i]; }
array[i]=pivot; return 1; }
前后遍历法:
private static int partition(int[] array,int left,int right){ int d=left+1; int
pivot=array[left]; for(int i=left+1;i<=right;i++){ if(array[i]<pivot){ swap(
array,i,d); d++; } } swap(array,d-1,left); return d-1; }
性能分析:

存在最优情况:如果每次获取到的基准值都能够将区间划分成左右两部分→图解:二叉树平衡数→O(NlogN)
存在最差情况:每次划分之后,数据都在基准值的一侧(每次拿到的基准值刚好是区间中的极值)→图解:单支树→O(N^2)

稳定性:不稳定

基准值的选择:
1.选择边上(左或者右)
2.随机选择
3.几数取中(例如三数取中):array[left],array[mid],array[right]大小是中间的为基准值

优化总结:
1,选择基准值很重要,通常使用几数取中法
2.partition过程中把和基准值相等的数也选择出来
3.待排序区间小于一个阈值时,使用直接插入排序

<>归并排序

原理:

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

原理-合并两个有序数组
private static int merge(int[] array,int left,int right){ int i=low; int j=mid;
int length=high-low; int[] extra=new int[length]; int k=0; //选择小的放入extra while(i
<mid&&j<high){ //加入等于,保证稳定性 if(array[i]<=array[j]){ extra[k++]=array[i++]; }else
{ extra[k++]=array[j++]; } } //将属于元素放入extra while(i<mid){ extra[k++]=array[i++];
} while(j<high){ extra[k++]=array[j++]; } //从extra搬移回array for(int t=0;t<length;
t++){ //需要搬移回原位置,从low开始 array[low+t]=extra[t]; } }
实现
public static void mergeSort(int[] array) { mergeSortInternal(array, 0, array.
length); } //待排序区间为[low,high) private static void mergeSortInternal(int[] array,
int low,int high){ if(low>=high-1){ return; } int mid=(low+high)/2;
mergeSortInternal(array,low,mid); mergeSortInternal(array,mid,high); merge(array
,low,mid,high); }
性能分析:
归并排序没有所谓最差和最优情况
时间复杂度:O(n*log(n))
空间复杂度:O(n)
稳定性:稳定

找出现次数最多的前K个单词-----TOP-K
输出:按照次数从大到小输出,次数如果相同,按照字母次序进行输出

方式一:
1.统计每个单词出现的次数;
2.对统计的结果<单词,单词出现次数>键值对,进行排序-----必须要提供比较准则----需要自己写比较器
3.取排序结果中的前K个单词

方法二:
1.统计每个单词出现的次数;
2.使用优先级队列按照<单词,单词出现次数>次数进行比较,创建了一个大堆;
3.直接取前K个元素
不太好

TOP—K
前K个最大的元素—小堆
前K个最小的元素—大堆

1.先用前K个元素建堆—前K个最大元素(小堆)
小堆可以保证堆顶元素永远是目前遇到的最小的元素,每次替换,都是将最小的从堆中剔除掉了
2.用后序元素依次与堆顶元素比较,
如果比堆顶元素小—舍弃
如果比堆顶元素大—*直接替换堆顶元素—堆需要向下调整
*:1.删除堆顶元素;2.将该元素插入

技术
©2019-2020 Toolsou All rights reserved,
新手玩海思HI3520D开发板(一,升级)贝叶斯决策Hackbar 使用教程git拉取远程分支并切换到该分支关于Navicat for mysql 的2003错误【Python-数据读取】读取txt文件每一行数据生成列表(精华2020年6月3日更新) TypeScript中接口详解vue vue-element-admin项目踩坑小结mybatis-config.xml设置默认值配置关于Bellman-Ford算法的个人理解