江苏省建设厅网站建筑电工证,如何做中国古城的网站,图片编辑在线使用,wordpress 全部函数排序的概念及其引用#xff1a;
排序的概念#xff1a; 排序#xff1a;所谓排序#xff0c;就是使一串记录#xff0c;按照其中的某个或某些关键字的大小#xff0c;递增或递减的排列起来的操作。 稳定性#xff1a;假定在待排序的记录序列中#xff0c;存在多个具有…排序的概念及其引用
排序的概念 排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。 稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持不变即在原序列中r[i]r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前则称这种排序算法是稳定的否则称为不稳定的 画图说明 排序前A在B前面排序后说明该排序稳定如果排序后B在A前面则说明不稳定。 内部排序数据元素全部放在内存中的排序。 外部排序数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序。 八大排序我们一般将其分为五类分别为 一 插入排序 1. 直接插入排序 2. 希尔排序 二 选择排序 1.直接选择排序 2.堆排序 三 交换排序 1. 冒泡排序 2. 快速排序 四 归并排序 五基数排序 插入排序
直接插入排序
基本思路 思路从第二个数开始假设此数为 tmp 逐个往前进行比对如果前数大于 tmp 就将前数值赋值到 tmp 处然后继续往前比对直到找到小于或等于 tmp 的数或者比对至数据首就停止最后将 tmp 的值赋值到此处就行了 动图演示 代码 public void insertSort(int[] array) {if (array.length 0) {return;}for (int i 1; i array.length; i) {int temp array[i];int j i - 1;for ( ; j 0 ; j--) {if (array[j] temp) {array[j 1] array[j];} else {break;}}array[j 1] temp;}} 直接插入排序总结 1. 集合元素越接近有序时间效率越高 2. 时间复杂度 O(N^2) 3. 空间复杂度 O(1) 4. 稳定性 稳定 希尔排序
前言 既然同为插入排序那必然是有共同点的。 希尔排序是建立在直接插入排序基础上经过优化的插入排序。 希尔排序分为两步 1、预排序使得数据尽可能接近有序2、直接插入排序最后调用一次直接插入排序快速的完成排序基本思路 思路预排序是通过区间划分实现的假设当前区间为 gap那么 1、1gap*n 可以分成一组同理2、3、4 都可以分将这些组分别进行直接插入排序数据少效率高。每完成一次分组排序gap 就会缩小直到 gap 为1时进行一次直接插入排序整个希尔排序就完成了 代码如下
public static void shellSort(int[] array) {int gap array.length;while (gap 1) {shell(array,gap);gap / 2;}//整体进行插入排序shell(array,1);}public static void shell(int[] array,int gap) {for (int i 1; i array.length; i) {int temp array[i];int j i - gap;for ( ; j 0 ; j- gap) {if (array[j] temp) {array[j gap] array[j];} else {break;}}array[j gap] temp;}} 动图演示 预排序 直接插入排序 希尔排序总结 1. 希尔排序的时间复杂度要用到高数中的知识“根据大量的数据的得到了局部的结论...”我们直接记答案即可O(N^1.25) 2. 空间复杂度 O(1) 我们仅仅只创建了一个gap 3. 稳定性 不稳定 我们在排序过程中gap会有多次的改变不同的组别中可能会发生交换现象。 选择排序
直接选择排序
基本思想每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完
代码
//选择排序public static void selectSort(int[] array) {for (int i 0; i array.length; i) {int minIndex i;for (int j i 1; j array.length; j) {if(array[j] array[minIndex]) {minIndex j;}}int temp array[i];array[i] array[minIndex];array[minIndex] temp;}}
如果像这样去遍历的话时间复杂度为O(N^2)不算是个很优解我们可以考虑对此进行优化
优化每次遍历选最大与最小分别与 end 值和 begin 值交换
动图演示 直接选择排序总结 1. 直接选择排序思考非常好理解但是效率不是很好。实际中很少使用2. 时间复杂度O(N^2)3. 空间复杂度O(1)4. 稳定性不稳定 堆排序
我们之前也介绍过堆排序PriorityQueue本质就是个小根堆这里就不过多介绍了。
思路堆排序用到了堆的知识如果想排升序的话建大堆因为大堆中堆顶是最大值将堆顶值与堆低值交换后执行向下调整使其再次变为大堆就这样反复交换、调整堆排序就完成了。 /*** 堆排序* param array 目标数组*/public static void heapSort(int[] array) {createBigHeap(array);int end array.length - 1;while (end 0) {swap(array,0,end);shiftDown(array,0, end);end--;}}public static void createBigHeap(int[] array) {//父下标 从倒数第二层开始int parent (array.length - 1 -1) / 2;for (; parent 0 ; parent-- ) {shiftDown(array,parent, array.length);}}public static void shiftDown(int[] array,int parent,int len) {int child 2*parent 1;while (child len) {if (child 1 len array[child] array[child 1]) {child;}if (array[child] array[parent]) {swap(array, parent, child);parent child;child 2 * parent 1;} else {break;}}}private static void swap(int[] array,int i,int j) {int tmp array[i];array[i] array[j];array[j] tmp;}
向上调整动图演示 堆排序总结 1. 堆排序使用堆来选数相对于直接插入排序效率就高了很多。2. 时间复杂度O(N*logN)3. 空间复杂度O(1)4. 稳定性不稳定 本文只是排序的上半部分涉及的排序思想都还算简单下一篇文章中将会介绍排序大哥快速排序知识点很难敬请期待吧。
