建设银行网站打不开怎么办,网站招标书怎么做,设计本网站,网站基本建设1.直接插入排序
1.原理#xff1a;和玩扑克牌一样#xff0c;从左边第二个牌开始#xff0c;选中这个#xff0c;和前面的所有牌比较#xff0c;插在合适的位置 public static void insertsort(int[] arr){//直接插入排序for (int i 1; i arr.length; i) {//此循环…1.直接插入排序
1.原理和玩扑克牌一样从左边第二个牌开始选中这个和前面的所有牌比较插在合适的位置 public static void insertsort(int[] arr){//直接插入排序for (int i 1; i arr.length; i) {//此循环用来从1开始确定牌的位置int j i-1;//得到j前面一个元素int tmp arr[i];//将i处元素取出来用来作比较for (; j 0 ; j--) {//此循环用来和i前面的比较将i放在正确的位置if(arr[j] tmp){arr[j1] arr[j];//若i前面的比i大则将前面的值赋值给后面}else{
// arr[j1] tmp;break;//比前面都要大没有比较的必要}}arr[j1] tmp;//j走完上面循环为-1上面走完一次循环j0时为空}}
直接插入排序特点
1. 元素集合越接近有序直接插入排序算法的时间效率越高 2. 时间复杂度O(N^2) 3. 空间复杂度O(1)它是一种稳定的排序算法 4. 稳定性稳定
2.希尔排序
希尔排序是直接插入排序的Promax版本将直接插入排序分为n份比较完n份排序即成功
思想先选定一个整数把待排序文件中所有记录分成多个组 所有距离为的记录分在同一组内并对每一组内的记录进行排序。然后取重复上述分组和排序的工作。当到达 1时所有记录在统一组内排好序。
public static void shellSort(int[] array){//希尔排序是直接插入排序的优化int gap array.length;while(gap 0){//将每组距离最终干为1即可成功gap / 2;//得到每组的距离shell(array,gap);}}public static void shell(int[] array,int gap){for (int i gap; i array.length; i) {int tmp array[i];int j i - gap;for (; j 0; j--) {if(array[j] tmp){array[jgap] array[j];}else{array[jgap] tmp;break;}}array[jgap] tmp;}}
3.选择排序
基本思想一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元 素排完 。 public static void selsctSort1(int[] array){//选择排序基础版for (int i 0; i array.length; i) {int minIndex i;//每循环一次确定一个从左往右的最小值int j i1;for (; j array.length; j) {if(array[minIndex] array[j]){minIndex j;//将minTndex和j的下标先进行交换,找到最小的和其交换}//从一次次循环中得出在[i,length的最小值}swap(array,minIndex,i);}}public static void selsctSort(int[] array){//选择排序promax版int left 0;int right array.length-1;while (left right){int minIndex left;int maxIndex left;//统一从没排序的起点开始for (int i left1; i array.length; i) {if(array[maxIndex] array[i]){maxIndex i;}if(array[minIndex] array[i]){minIndex i;}}swap(array,left,minIndex);swap(array,right,maxIndex);left;right--;}}public static void swap(int[]array ,int minIndex,int j){int tmp array[j];array[j] array[minIndex];array[minIndex] tmp;}
}
总结 1. 直接选择排序思考非常好理解但是效率不是很好。实际中很少使用 2. 时间复杂度O(N^2) 3. 空间复杂度O(1) 4. 稳定性不稳定
4. 堆排序 降序建大堆升序建小堆
详情思路请看之前写的堆部分
https://mp.csdn.net/mp_blog/creation/editor/139502440 /*** 堆排序* 时间复杂度O(n*logN)* 空间复杂度O(1)* 稳定性不稳定* param array*/public static void heapSort(int[] array) {createHeap(array);int end array.length-1;while (end 0) {swap(array,0,end);siftDown(array,0,end);end--;}}private static void createHeap(int[] array) {for (int parent (array.length-1-1)/2; parent 0; parent--) {siftDown(array,parent,array.length);}}/**** param array* param parent 每棵子树调整的根节点* param length 每棵子树调整的结束节点*/private static void siftDown(int[] array, int parent, int length) {int child 2 * parent 1;while (child length) {if(child 1 length array[child] array[child1]) {child;}if(array[child] array[parent]) {swap(array, parent, child);parent child;child 2*parent1;}else {break;}}}
6.快速排序
思想任取待排序元素序列中的某元 素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有 元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。
翻译过来实现过程就是取第一个数分别在头和尾定义一个指针 头指针找比第一个数大的需求就是把小的放在左边所以需要找大的和右边大的交换尾指针找比第一个小的两个都找到后进行交换确保左边的都是小于或等于第一个数的右边都是大于或等于第一个数的直到两个指针位置相等然后再交换第一个与它们的位置通过递归将它们分为一个个更小的然后即可完成 快速排序Hoare法实现过程 问题为什么先从后面开始
如果先从前面开始则会造成最后汇合点大于key. 递归法
通过left和right的不断变化直到left与right相遇为止当不断分为很多的left和right后
public class Sort {public static void swap(int[]array ,int minIndex,int j){int tmp array[j];array[j] array[minIndex];array[minIndex] tmp;}public static void qsort(int[] array){int left 0,right array.length-1;parttrtions(array,left,right);}private static void parttrtions(int[]array,int left,int right){if(leftright){return;}int start parttrtion(array,left,right);parttrtions(array,left,start-1);parttrtions(array,start1,right);}private static int parttrtion(int[] array,int left,int right){//Hoare版int privt array[left];int end right,start left;while(startend){while(startend array[end] privt) {//从右往左直到找到比array[start](privt)小的放在end--;}while(startendarray[start] privt){//跳出小循环说明找到了比privt大的数start;}swap(array,left,start);}return start;}private static int parttrtion1(int[] array,int left,int right){//挖坑法int privt array[left];int end right,start left;while(startend){while(startend array[end] privt) {//从右往左直到找到比array[start](privt)小的放在end--;}array[start] array[end];//将end下标的值来补充start的空缺while(startendarray[start] privt){//跳出小循环说明找到了比privt大的数start;}array[end] privt;//将start下标的值来补充end的空缺}return start;}
}快排的优化
1.三数取中法如果是单一的数则可能造成单支树的产生最高造成N(O*2),所以可以提前将中间的值给到start,这样能极大减少计算量
private static int getMiddleNum(int[] array,int left,int right) {int mid (leftright)/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;}}} 非递归法 利用栈后进先出不断变化left和right的值
public static void qsort1(int[] array){int left 0,right array.length-1;int par parttrtion(array,left,right);StackInteger stack new Stack();if(parleft1){stack.push(left);stack.push(par-1);}if(par right-1){stack.push(par1);stack.push(right);}while(!stack.empty()){right stack.pop();left stack.pop();par parttrtion(array,left,right);if(parleft1){stack.push(left);stack.push(par-1);}if(par right-1){stack.push(par1);stack.push(right);}}}总结 1. 快速排序整体的综合性能和使用场景都是比较好的所以才敢叫快速排序 2. 时间复杂度O(N*logN)
3. 空间复杂度O(logN) 4. 稳定性不稳定
7.归并排序
思想先将数组分成很多小份然后再进行排序然后把排序完的数组重新整和最终得到一个有序数组。 递归法
1.首先将大数组分为小数组把大问题拆分为小问题1.找到最底层的两个数组2.排序 public void mergeSortTmp(int[]a,int left,int right){//将数组先分开再合并if(leftright){return;}int mid (leftright)/2;mergeSortTmp(a,left,mid);//分成很多份找到最左边mergeSortTmp(a,mid1,right);//上层递归完成找到对应要排序的另一个数组merge(a,mid,left,right);//两个都找到后进行排序操作}
2.然后利用两个数组组合排序的方法定义两个指针取到小的添加到新的数组
private void merge(int[]a,int mid,int left,int right){int [] array new int[right-left1];int set 0;int s1 left;int e1 mid;int s2 mid1;int e2 right;while(s1e1s2e2){if(a[s1] a[s2]){array[set] a[s1];}else {array[set] a[s2];}}while (s1 mid) {array[set] array[s1];}while (s2 right) {array[set] array[s2];}for (int i 0; i array.length; i) {a[ileft] array[i];//分组后每一小组的下标并不是零}}
非递归法
思路我们这个排序的核心就是1.一步步得到最小数组 2.一步步将两个小数组合并起来直到得到 大数组
所以可以在循环里嵌套循环外面决定数组长度里面循环将小数组排序合并外循环设置每个小数组的相隔距离 public void mergrSort1(int[] array){int left 0,right array.length-1;int gap 1;//gap负责将数组分为array.length/2while(gaparray.length){for (int i 0; i array.length; i2*gap) {//得到小一号的数组并且进行排序合并,里面for循环是为了得到最多组数组left i;int mid leftgap-1;right midgap;if(mid array.length) midarray.length-1;if(rightarray.length) right array.length-1;merge(array,mid,left,right);}gap * 2;//世界线收束每次小数组排序好后再将更大数组排序}}}
总结1. 归并的缺点在于需要O(N)的空间复杂度归并排序的思考更多的是解决在磁盘中的外排序问题。 2. 时间复杂度O(N*logN) 3. 空间复杂度O(N) 4. 稳定性稳定
8.计数排序
思路将原数组遍历一遍得到原数组的最大值和最小值将最大值和最小值相减得到它们的取值范围创建一个新数组然后将对应的值给到和其相对相等的下标比如数组的值为1给到开辟数组的1下标然后遍历新数组赋值给原数组
/*** 计数排序* 时间复杂度O(范围 n )* 范围越大 越慢* 空间复杂度O(范围)* 稳定性* param array*/public static void countSort(int[] array) {//1. 找最大值 和 最小值 来确定 计数数组的大小int maxVal array[0];int minVal array[0];for (int i 1; i array.length; i) {if(array[i] minVal) {minVal array[i];}if(array[i] maxVal) {maxVal array[i];}}int len maxVal - minVal 1;int[] count new int[len];//2. 遍历原来的数组array把 每个元素 放到对应的计数数组当中 进行计数for (int i 0; i array.length; i) {int index array[i];count[index-minVal];}//3.依次 遍历计数数组 O(范围)int index 0;for (int i 0; i count.length; i) {while (count[i] ! 0) {array[index] iminVal;index;count[i]--;}}}总结
1. 计数排序在数据范围集中时效率很高但是适用范围及场景有限。 2. 时间复杂度O(MAX(N,范围)) 3. 空间复杂度O(范围) 4. 稳定性稳定
