河南省建设工程网站,科技馆网站建设方案,精灵代理ip,php团购网站开发作者#xff1a;✿✿ xxxflower. ✿✿ 博客主页#xff1a;xxxflower的博客 专栏#xff1a;【数据结构】篇 语录#xff1a;⭐每一个不曾起舞的日子#xff0c;都是对生命的辜负。⭐ 文章目录1.排序1.1排序的概念1.2常见的排序算法2.常见排序算法2.1插入排序2.1.1直接插入… 作者✿✿ xxxflower. ✿✿ 博客主页xxxflower的博客 专栏【数据结构】篇 语录⭐每一个不曾起舞的日子都是对生命的辜负。⭐ 文章目录1.排序1.1排序的概念1.2常见的排序算法2.常见排序算法2.1插入排序2.1.1直接插入排序2.1.2希尔排序缩小增量排序2.2选择排序2.2.1基本思想2.2.3 堆排序2.3交换排序2.3.1冒泡排序2.3.2快速排序2.3.2快速排序的优化2.3.3快速排序2.3.5非递归实现快速排序2.4 归并排序2.4.1递归实现归并排序2.4.2非递归的归并排序3.排序的总结计数排序1.排序
1.1排序的概念
排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。 稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持不变即在原序列中r[i]r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前则称这种排序算法是稳定的否则称为不稳定的。 内部排序数据元素全部放在内存中的排序。 外部排序数据元素太多不能同时放在内存中根据排序的要求不能在内外存之间移动数据的排序。
1.2常见的排序算法 2.常见排序算法
2.1插入排序
插入排序的基本思想是把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列 。实际中我们玩扑克牌时就用了插入排序的思想。
2.1.1直接插入排序 public static void insertSort(int[] array){for (int i 1; i array.length; i) {int tmp array[i];int j i-1;for (;j 0;j--) {if(array[j] tmp){array[j1] array[j];}else{break;}}array[j1] tmp;}}我们来分析一下插入排序时间复杂度 最好情况下顺序。O(N) 最坏情况下逆序。O(N^2) 因此我们可以得出一个结论当数据量不多且基本上趋于有序的时候直接插入排序是非常快的。 空间复杂度O(1) 稳定性稳定
2.1.2希尔排序缩小增量排序
希尔排序法又称缩小增量法。希尔排序法的基本思想是先选定一个整数把待排序文件中所有记录分成个组所有距离为的记录分在同一组内并对每一组内的记录进行排序。然后取重复上述分组和排序的工作。当到达1时所有记录在统一组内排好序。
//希尔排序private 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 - gap){if(tmp array[j]){array[jgap] array[j];}else{break;}}array[igap] tmp;}}public static void shellSort(int[] array){int gap array.length;while(gap 1){gap / 2;shell(array,gap);}}希尔排序的时间复杂度是数学上未解决的题它会随着组别的变化而变化。但是大量的实验的得出局部的结论O(N^1.3) 稳定性不稳定。 空间复杂度O(1)。 希尔排序实际上是对直接插入排序的优化。它使得数字趋于有序化最后在进行直接插入排序。
2.2选择排序
2.2.1基本思想
每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完 。 方法一
//选择排序public static void selectSort(int[] array){for(int i 0;i array.length;i){int minIndex i;for(int j i1;j array.length;j){if(array[j] array[minIndex]) {minIndex j;}}//处理两个下标一样的情况比如第一个数就是最大值后面找不到比它小的值if(i minIndex){swap(array,minIndex,i);}}}public static void swap(int[] array,int i,int j){int tmp array[i];array[i] array[j];array[j] tmp;}方法二
//为了提高效率可以左右一起找找最小值放在前面找最大值放在后面public static void selectSort2(int[] array){int left 0;int right array.length -1;while(left right){int minIndex left;int maxIndex right;for(int j left 1;j right;j){if(array[j] array[minIndex]){minIndex j;}if(array[j] array[maxIndex]){maxIndex j;}}//将最小值换到前面swap(array,minIndex,left);//如果max下标正好是Left说明上次已经把最大值从left位置换到了minIndex位置if(maxIndex left){maxIndex minIndex;}//吧最大值换到后面。swap(array,maxIndex,right);left;right--;}}选择排序的时间复杂度为O(n^2) 空间复杂度O(1) 稳定性不稳定
2.2.3 堆排序
堆排序(Heapsort)是指利用堆积树堆这种数据结构所设计的一种排序算法它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆排降序建小堆。 堆排序将要排序的数组创建成一个大根堆再将第一个值和最后一个值进行交换再将二叉树调整成为大根堆依次循环排序。
//堆排序public static void heapSort(int[] array){creatBigHeap(array);int end array.length -1;while(end 0){swap(array,0,end);shiftDown(array,0,end);end--;}}private static void creatBigHeap(int[] array){for(int parent (array.length - 1-1)/2;parent 0;parent--){shiftDown(array,parent,array.length);}}private static void shiftDown(int[] array,int parent,int len){int child (2* parent) 1;while(child len){if(child1 len array[child] array[child1]){child;}if(array[child] array[parent]){swap(array,child,parent);parent child;child 2 * parent 1;}else{break;}}}堆排序的时间复杂度O(N*logN) 空间复杂度O(1) 稳定性不稳定
2.3交换排序
基本思想所谓交换就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置交换排序的特点是将键值较大的记录向序列的尾部移动键值较小的记录向序列的前部移动。
2.3.1冒泡排序
//冒泡排序public static void bubbleSort(int[] array){for(int i 0;i array.length;i){boolean flg false;for(int j 0; j array.length - 1-i;j){if(array[j] array[j1]){swap(array,j,j1);flg true;}}if(flg false){break;}}}2.3.2快速排序
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法其基本思想为任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。 1.Hoare排序 hoare排序是从右边开始找一个比key值小的从左边找一个比key值大的数两者进行交换当leftright时将此数与key交换。以此来排序。
//快速排序public static int partitionHoare(int[] array,int left,int right){int key array[left];int i left;while(left right){while(left right array[right] key){right--;}while(left right array[left] key){left;}swap(array,left,right);}swap(array,left,i);return left;}挖坑法 挖坑法就是以第一个数字为基准值从右边找到一个比基准值大的数字放进基准的位置。再从左边找一个比基准值小的数字放进右边的位置
//挖坑法public static int partition2(int[] array,int left,int right){int key array[left];while(left right){while(left right array[right] array[key]){right--;}array[left] array[right];while(left right array[left] array[right]){left;}array[right] array[left];}array[left] key;return left;}前后指针法 //前后指针法private static int partition(int[] array, int left, int right) {int prev left ;int cur left1;while (cur right) {if(array[cur] array[left] array[prev] ! array[cur]) {swap(array,cur,prev);}cur;} swap(array,prev,left);return prev;}2.3.2快速排序的优化
三数取中法选key递归到小的子区间时可以考虑使用插入排序
public static void insertSort(int[] array,int left,int right){for (int i 1; i array.length; i) {int tmp array[i];int j i-1;for (;j 0;j--) {if(array[j] tmp){array[j1] array[j];}else{break;}}array[j1] tmp;}}
public static void quick(int[] array,int start,int end){if(start end){return;}if(end - start 1 15){insertSort(array,start,end);return;}int index findMidValIndex(array,start,end);swap(array,start,index);int key partition(array,start,end);quick(array,start,key-1);quick(array,end,key1);}public static int findMidValIndex(int[] array,int start,int end){int midIndex (start end)/2;if(array[start] array[end]){if(array[midIndex] array[start]){return start;} else if (array[midIndex] array[end]) {return end;}else{return midIndex;}}else{if(array[midIndex] array[start]){return start;} else if (array[midIndex] array[end]) {return end;}else{return midIndex;}}}2.3.3快速排序
快速排序整体的综合性能和使用场景都是比较好的所以才敢叫快速排序时间复杂度O(N*logN)空间复杂度O(logN)稳定性不稳定
2.3.5非递归实现快速排序 先找基准 判断基准元素左边和右边是否有两个及以上元素 如果有则将首位置和p-1位置放入栈中注意放入顺序处理左边再将p1位置和end位置放入栈中处理右边 当栈不为空的时候弹出两个元素在判断左边和右边的情况。依次循环
//非递归实现快速排序public static void quickSort(int[] array){StackInteger stack new Stack();int start 0;int end array.length-1;int pivot partition(array,start,end);//1.判断左边是否有两个元素if(pivot start 1){stack.push(start);stack.push(pivot-1);}//2.判断右边是否有两个元素if(pivot end-1){stack.push(pivot1);stack.push(end);}while(!stack.isEmpty()){end stack.pop();start stack.pop();pivot partition(array,start,end);//3.判断左边是否有两个元素if(pivot start 1){stack.push(start);stack.push(pivot-1);}//4.判断右边是否有两个元素if(pivot end-1){stack.push(pivot1);stack.push(end);}}}2.4 归并排序
2.4.1递归实现归并排序
归并排序首先要了解二叉树的基本知识通过递归将数组分成一个一个的然后在合并。合并的时候可以参考前面写过的例题即两个有序数组合并问题。通过合并可以使数组有序此时我们建立了新的数组。注意在最后给数组赋值的时候tmpArr当中的数据是right left之间的有序数据。因此要从右侧开始。 public static void mergeSort1(int[] array){mergeSortChild(array,0,array.length-1);}private static void mergeSortChild(int[] array,int left,int right){if(left right){return;}//拆分int mid (leftright)/2;mergeSortChild(array,left,mid);mergeSortChild(array,mid1,right);//合并merge(array,left,mid,right);}public static void merge(int[] array,int left,int mid,int right){int s1 left;int e1 mid;int s2 mid 1;int e2 right;int[] tmpArr new int [right - left 1];int k 0;while(s1 e1 s2 e2){if(array[s1] array[s2]){tmpArr[k] array[s1];}else{tmpArr[k] array[s2];}}while(s1 e1){tmpArr[k] array[s1];}while(s2 e2){tmpArr[k] array[s2];}for(int i 0;i k;i){array[ileft] tmpArr[i];}}由归并排序的思想可得其 空间复杂度为O(N) 时间复杂度为O(N*logN) 稳定性稳定 我们学过的稳定排序为插入冒泡归并
2.4.2非递归的归并排序
非递归实现归并排序时先将数组分成一个一个的然后通过调整left,mid right来合并数组。 //非递归实现归并排序public static void mergeSort(int[] array){int gap 1;while(gap array.length){for(int i 0;i array.length;igap){int left i;int mid left gap-1;int right midgap;//需要考虑mid和right越界的问题i在循环中所以不用考虑i越界的问题if(mid array.length){mid array.length -1;}if(right array.length){right array.length-1;}merge(array,left,mid,right);}gap 2*gap;}}3.排序的总结 计数排序 public static void countSort(int[] array) {//1、遍历数组 找到 最小值 和最大值 -》 才能确定 计数数组的大小int maxVal array[0];int minVal array[0];//O(n)for (int i 0; i array.length; i) {if(array[i] maxVal) {maxVal array[i];}if(array[i] minVal) {minVal array[i];}}//2、确定计数数组的长度int len maxVal - minVal 1 ;int[] countArr new int[len];//3. 开始遍历 当前数组 统计每个数字出现的次数 O(n)for (int i 0; i array.length; i) {int val array[i];countArr[val-minVal] ;//??????????????}int index 0;//4. 遍历计数数组看每个下标的值是几就打印几个下标的数据就好了 O(范围 n)//范围遍历一次位置上所有的数的个数加起来等于nfor (int i 0; i countArr.length; i) {while (countArr[i] 0) {//不敢打印array[index] iminVal;//??????????????index;countArr[i]--;}}}
