漳州网站建设选博大不错,做旅游网站的目标,网站开发文档总结,国家商标查询官网入口1.快速排序
快速排序是Hoare在1962年提出的一种二叉树结构的交换排序的方法#xff0c;采用了递归的思想
思想#xff1a;任取待排序的元素序列中的某元素作为基准值#xff0c;按照原来的顺序将序列分为两个子序列#xff0c;
左子序列中的所有元素均小于基准直#x…1.快速排序
快速排序是Hoare在1962年提出的一种二叉树结构的交换排序的方法采用了递归的思想
思想任取待排序的元素序列中的某元素作为基准值按照原来的顺序将序列分为两个子序列
左子序列中的所有元素均小于基准直右子树的所有序列中的元素均大于基准直然后左右子序列重复该过程直到所有元素都排在相应的位置上。
先写出大致的框架与二叉树的前序遍历非常之像写递归框架可以照着二叉树前序遍历写出来
后续只要分析如何按照基准直对区间中的数据划分即可
public static void QuickSort(int[] array,int start,int end){//递归结束的条件if(start end){return;}//如果子区间的数据越来越少了直接采用 范围插入排序 更快if(end-start1 10){insertSort(array,start,end);return;}//三数取中原因//如果这个序列是接近有序的1 2 3 4 5 6 7 8 9 11 10//基准值一般选取最左侧的数据 1那么每次递归1的左侧没有子序列只有右侧//所以会大大提高时间复杂度//那么就取最左最有最中三个数据的中位数//将中位数与第一个数交换这样返回的基准直就不是1了而是与1交换的数int index midTreeNum(array,start,end);swap(array,start,index);//寻找基准直位置的下标//该方法有很多种等下面我们一一介绍int par paririon(array,start,end);//按照基准直将其左右两个子区间进行排序QuickSort(array,start,par-1);QuickSort(array,par1,end);}//挖坑法private static int paririon(int[]array,int left,int right){int temp array[left];while (left right){while (left right array[right]temp){right--;}array[left] array[right];while (left right array[left] temp){left;}array[right] array[left];}array[left] temp;return left;}//找到中间值的下标private static int midTreeNum(int[]array,int left,int right){//中间位置下标int mid left(right-left)/2;if(array[left]array[right]){if(array[mid]array[left]){return left;}else if(array[mid]array[right]){return right;}else {return mid;}}else {if(array[mid]array[left]){return left;}else if(array[mid]array[right]){return right;}else {return mid;}}}private static void insertSort(int[]array,int left,int right){for(int ileft1;iright;i){int temp array[i];int j i-1;for(;j0;j--){if(array[j] temp){array[j1] array[j];}else {break;}}array[j1] temp;}}paririon 方法使用用来找到基准直的通过找到的基准直将序列化分为两个子区间再通过递归不断排序缩小子区间直到子区间就一个数字。
int index midTreeNum(array,start,end);
这条语句什么意思 就是取到三个数的中位数
三数取中原因
如果这个序列是接近有序的1 2 3 4 5 6 7 8 9 11 10
基准值一般选取最左侧的数据 1那么每次递归1的左侧没有子序列只有右侧
所以会大大提高时间复杂度
那么就取最左最有最中三个数据的中位数
将中位数与第一个数交换这样返回的基准直就不是1了而是与1交换的数
上面查找基准值的paririon方法是挖坑法
下面例举Hoare法查找基准值
//Hoare法private static int paririon2(int[]array,int left,int right){int i left;int temp array[left];while (left right){while (left right array[right] temp){right--;}while (left right array[left]temp){left;}swap(array,left,right);}swap(array,left,i);return left;}
快速排序总结
1.整体综合性能与使用场景都是比较好的才敢较快排
2.时间复杂度O(N*logN);
3.空间复杂度O(logN);
4.稳定性不稳定 2.归并排序
建立在归并操作上的有效排序算法该算法采用分治法的一个典型的应用。将已有的子序列合并得到完全有序的序列。
使每个子序列有序再使每个子序列之间有序。
归并排序
更多是解决磁盘中的外排序问题。
时间复杂度O(N*logN)
空间复杂度O(N)
稳定性稳定
代码实现
//归并排序public static void mergeSort(int[]array){megeFun(array,0,array.length-1);}public static void megeFun(int[]array,int left,int right){if(left right){return;}//分解int mid left(right-left)/2;megeFun(array,left,mid);megeFun(array,mid1,right);//合并merge(array,left,mid,right);}public static void merge(int[]array,int left,int mid,int right){int[] temp new int[right-left1];int sl left;int el mid;int sr mid1;int er right;int k 0;while (slel srer){if(array[sl] array[sr]){temp[k] array[sl];}else{temp[k] array[sr];}}while (slel){temp[k] array[sl];}while (srer){temp[k] array[sr];}for (int i 0; i k; i) {array[ileft] temp[i];}}3.计数排序
又叫做鸽巢原理是对哈希直接定址法的变形应用
1.统计相同元素的出现的次数
2.根据统计结果将序列收回到原来的序列中
时间复杂度O(max(N,范围))
空间复杂度O(范围)
稳定性稳定
代码
public static void countSort(int[]array){//遍历数组找到最大最小值int mindex array[0];int maxdex array[0];for (int i 0; i array.length; i) {if(maxdexarray[i]){maxdex array[i];}if(mindexarray[i]){mindex array[i];}}//已经找到最大与最小值了定义数组int[]count new int[maxdex-mindex1];for (int i 0; i array.length; i) {int val array[i]-mindex;count[val];}//count数组以数据为下标出现的次数为值int index 0;//array的下标for (int i 0; i count.length ; i) {while (count[i]0){array[index] imindex;index;count[i]--;}}}
