无锡自适应网站开发,电子商务的就业方向,西红门做网站,漳州做网站制作排序
1、冒泡排序
两层循环#xff0c;相邻两个进行比较#xff0c;大的推到后面去#xff0c;一共比较“数组长度”轮#xff0c;每一轮都是从第一个元素开始比较#xff0c;每一轮比较都会将一个元素固定到数组最后的一个位置。【其实就是不停的把元素往后堆#…排序
1、冒泡排序
两层循环相邻两个进行比较大的推到后面去一共比较“数组长度”轮每一轮都是从第一个元素开始比较每一轮比较都会将一个元素固定到数组最后的一个位置。【其实就是不停的把元素往后堆数组剩余长度越来越少直到堆到最后一个数组都堆好排好序了】
if (arr null || arr.length 2) return;
for (int e arr.length - 1; e 0; e--) {for (int i 0; i e; i) {if (arr[i] arr[i 1]) {swap(arr, i, i 1); } } }2、选择排序
也是比较**“数组长度-1”轮但是每一轮中是将一个最值元素放在开头**然后从这个更新过元素的位置往后继续开始此轮的选择最值过程【其实就是不停的从选择最小元素然后往前堆和冒泡正好相反然后前面剩余空间越来越少直到前面都堆好了排好序了】
if (arr null || arr.length 2) return;
for(int i0; iarr.length - 1; i){int minIndex i;for(int ji1; jarr.length; j){minIndex arr[j] arr[minIndex] ? j : minIndex;} swap(arr,i,minIndex);
}3、插入排序
重点看当前索引指向的元素大小去对比比当前索引小也就是前面排好序的那一部分元素。找到合适的位置然后插进去。这对比的次数明显变少只用和【索引-1】前面的数进行比较。
if (arr null || arr.length 2) return;
for(int i 1; iarr.length; i)for(int j i-1; arr[j1]arr[j] j 0; j--)swap(arr,j,j1);4、快速排序 本质是找个基准值一般可以选取这段数组中的最后一个元素。然后将小于这个基准值的放在其左侧大于的放在其右侧. 在遍历数组时一般采用三指针法来实现。具体来说我们使用一个左指针指向数组的左边界用一个右指针指向数组的右边界。另外一个指针指向元素用来遍历。 如果当前查找的索引值对应数据 arr [i] 小于基准值那么这个值和左边界【左指针】的下一个进行交换同时左指针右移 如果大于基准值就将其和右边界的前一个元素交换同时左边界指针不动。索引 i 也不动但是右指针左移 如果等于基准值索引 i public static void quickSort(int[] arr){if(arr null || arr.length 2)return;quickSort(arr,0,arr.length-1);
}public static void quickSort(int[] arr, int l, int r){if(l r){int[] p partition(arr,l,r); //作用就是将最后一个元素当作基准值然后将大于基准值得放右边小于的放左边//同时返回一个基准信息,p[0]就是基准值中最左的一个【考虑到可能标志值会重复】p[1]是最右侧quickSort(arr, l, p[0] - 1);quickSort(arr, p[1] 1, r);}
}public static void partiton(int[] arr, int l, int r){ //l是左边界int pivot arr[r];int left l -1;int right r;while(l right){ //arr[l]就用来记录逐步遍历数组中的元素if(arr[l] pivot)swap(arr, left, l); // 将小于等于pivot的元素交换到左边界的右侧else if(arr[l] pivot){swap(arr, --right, l); // 将大小于等于pivot的元素交换到右边界的左侧}elsel;}swap(arr, more, r); //最后将基准值转移到右指针位置return new int[] { less 1, more };
}5、归并排序
将数组按照中间的位置划分成左右两部分然后对这两部分进行扫描归并。准备两个指针分别指向左部分的开头以及有部分的开头。然后比较大小按照比较结果将结果放进一个临时开辟的数组中最后将这个临时数组的元素再塞回去。
public static void mergeSort(int[] arr){if(arr null || arr.length 2)return;mergeSort(arr,0,arr.length-1);
}public static void mergeSort(int[] arr, int l, int r){if(l r){int mid l ((r-l)1;mergeSort(arr, l, mid1);mergeSort(arr, mid1, r); merge(arr,l,mid,r);}
}public static void merge(int[] arr, int l, int mid, int r) {int[] help new int[r - l 1];int i 0;int p1 l;int p2 mid 1;while(p1 mid p2 r){help[i] arr[p1] arr[p2] ? arr[p1] : arr[p2];}while (p1 m) {help[i] arr[p1];}while (p2 r) {help[i] arr[p2];}for (i 0; i help.length; i) {arr[l i] help[i];}
}6、堆排序 主要涉及两步骤 1、构建堆【heapInsert】2、输出堆顶元素然后调整堆结构以便于下一轮继续输出堆顶元素【heapify】 构建堆的过程就是不停的往上也就是和自己的父节点、祖父节点…一直比较下去如果想要大根堆那就是只要大于父节点那就和父节点交换我们对数组的每一个元素都去单独构建一边。
调整堆就是不停的往下。将堆顶元素和数组最后元素交换由于当前数组经过构建堆过程后已经是堆结构了。所以我们的堆顶元素肯定就是一个最值交换过后再重新调整堆即可。就是找到堆顶的孩子节点中最大的值进行比较交换一直比较到树的最后一层
public static void heapSort(int[] arr) { //这个是主函数参数中的arr数组中存放的就是待排元素if (arr null || arr.length 2) {return;}for (int i 0; i arr.length; i) { //这个函数是用于创建大根堆为了之后输出堆顶元素就是最大值heapInsert(arr, i);}int size arr.length; swap(arr, 0, --size); //这一步是为了将堆顶元素和最后一个元素互换位置注意最后要自减 也就是说最后应该数组中元素是从小到大排序的如果一开始是一个大根堆while (size 0) {heapify(arr, 0, size);swap(arr, 0, --size); //同上面道理}
}
public static void heapInsert(int[] arr, int index) { //这个函数比较好理解就是一个循环只要在创建堆结构过程中新加入堆中的子节点比父节点元素大就交换最后形成的是大根堆while (arr[index] arr[(index - 1) / 2]) {swap(arr, index, (index - 1) /2);index (index - 1)/2 ; //这一步别忘记了一直是往下走的index这个表示父节点位置的标记变量也要向下走}
}
public static void heapify(int[] arr, int index, int size) {//这次函数中参数中要借助 堆的大小size对应上面主函数中的每次输出一次堆顶元素后大小减1int left index * 2 1;while (left size) {int largest left 1 size arr[left 1] arr[left] ? left 1 : left;//上面这一步是为了找到左右子节点哪个最大然后记录最大的那个下标largest arr[largest] arr[index] ? largest : index;if (largest index) {break;}swap(arr, largest, index);index largest;left index * 2 1;}
}
public static void swap(int[] arr, int i, int j) { //就是一个交换函数C中直接用swap函数即可int tmp arr[i]; arr[i] arr[j]; arr[j] tmp; }7、优先级队列
默认是小根堆
//小根堆。默认
PriorityQueueInteger heap new PriorityQueue();在左神算法讲解时举了一个例子就是; 堆排序扩展题目:
已知一个几乎有序的数组几乎有序是指如果把数组排好顺序的话每个元素移动的距离可以不超过k并且k相对于数组来说比较小。请选择一个合适的排序算法针对这个数据进行排序。这时候就需要借助 堆结构 一开始先将前k个数存放入此优先级队列也就是堆结构然后将堆顶元素返回也就是用pop返回 这k个元素构成一个堆结构找到这个堆中的小根堆的堆顶元素就是当前最小的 因为每个元素移动的距离不超过k所以可以理解为这前k个数中最小的一个属肯也是整体数据中最小的一个数字把第k1个数放进去再次形成小根堆那返回的堆顶元素就是第二小的元素 然后再重新从数组中取下一个元素添加到堆中自动就排好序形成相应的大根堆或者是小根堆 下面我用左神算法中的java 代码来展示其中关键的地方都加了注释了
public void sortedArrDistanceLessK(int[] arr, int k) {PriorityQueueInteger heap new PriorityQueue(); //java中的优先级队列的定义方式int index 0;for (; index Math.min(arr.length, k); index) {//万一k超出范围了就选取数组长度当作边界值min()的作用就是这个heap.add(arr[index]);}int i 0;for (; index arr.length; i, index) {heap.add(arr[index]); //上面那个for循环实际上没有取到第k个元素所以先取arr[i] heap.poll(); //然后再弹出堆顶元素}while (!heap.isEmpty()) {//数组最后一个元素也都加进堆结构后剩下的就是将堆中的所有元素放依次弹出了arr[i] heap.poll();}
}8、复杂度
冒泡时间复杂度o(n^2) 空间复杂度O(1)原地排序不需要额外空间选择时间复杂度o(n^2) 空间复杂度O(1)原地排序不需要额外空间插入时间复杂度o(n^2) 空间复杂度O(1)原地排序不需要额外空间快速时间复杂度o(nlogN) 空间复杂度平均情况下是O(log n)最坏情况下是O(n)。归并时间复杂度o(nlogN) 空间复杂度O(n)需要额外的空间来合并子数组堆 时间复杂度o(nlogN) 空间复杂度O(1)原地排序
