清远市建设工程造价信息网站黑马程序员培训在哪里

当前位置： 首页 > news >正文

清远市建设工程造价信息网站,黑马程序员培训在哪里,内蒙古建设厅官网站,历史价格查询文章目录 一、排序的概念及引用1.1 排序概念1.2 排序运用1.3 常见排序算法 二、常见排序算法的实现2.1 插入排序2.1.1 基本思想2.1.2 直接插入排序2.1.3 希尔排序 2.2 选择排序2.2.1 基本思想2.2.2 直接选择排序2.2.3 堆排序 2.3 交换排序2.3.1 冒泡排序2.3.2 快速排序2.3.3 快… 文章目录 一、排序的概念及引用1.1 排序概念1.2 排序运用1.3 常见排序算法 二、常见排序算法的实现2.1 插入排序2.1.1 基本思想2.1.2 直接插入排序2.1.3 希尔排序 2.2 选择排序2.2.1 基本思想2.2.2 直接选择排序2.2.3 堆排序 2.3 交换排序2.3.1 冒泡排序2.3.2 快速排序2.3.3 快速排序优化2.3.4 快速排序非递归 2.4 归并排序2.4.1 基本思想2.4.2 海量数据的排序问题 三、排序算法复杂度及稳定性分析四、其他非基于比较排序1.计数排序2.基数排序3.桶排序 五.选择题 一、排序的概念及引用 1.1 排序概念 排序使一串数据按照其中某个或某些关键字的大小递增或递减排列起来的操作。本文所讲排序都是按升序排列。 稳定性假设在待排序的记录序列中存在多个具有相同的关键字若经过排序这些数据的相对次序保持不变即在原序列中r[i]r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前则称这种排序算法是稳定的否则称为不稳定的。 内部排序数据元素全部放在内存中的排序。 外部排序数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序。 1.2 排序运用 1.3 常见排序算法 二、常见排序算法的实现 2.1 插入排序 2.1.1 基本思想 把待排序的数据集合按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有数据插入完为止得到一个新的有序序列。
2.1.2 直接插入排序 初始时第一个元素为有序序列从第二个元素i所指的值(tmp)开始与前面的有序序列的末尾下标j所指值开始进行比较如果j所指的值大于tmpj所指元素向后移直到j所指的值小于等于tmpj后一位存放tmpi向后走重复上述步骤。
public static void insertSort(int[] array){for(int i 1;i array.length; i){int j i-1;int tmp array[i];for(;j 0;j–){if(array[j] tmp){array[j1] array[j];}else {break;}}array[j1] tmp;}}直接插入排序的特性总结 1. 元素集合越有序算法的时间效率越高 适用于待排序序列 已经基本上趋于有序了 2. 时间复杂度最坏情况O(N^2) 最好情况O(N) 3. 空间复杂度O(1) 4. 稳定性稳定 2.1.3 希尔排序 希尔排序法又称缩小增量法基本思想先选定一个整数gab把待排序集合中所有元素分成多个组所有距离为gab的元素分在同一组并对每一组内的记录进行插入排序。然后设定一个新的整数重复上述分组和排序的工作。当到达1时所有记录在一组内排好序。
/**

• 希尔排序 */ public static void shellSort(int[] array){int gab array.length;while (gab 1){gab / 2;shell(array,gab);}} /**
• 将array分为gab组进行插入排序 */ private static void shell(int[] array,int gab){for (int i gab; i array.length; i) {int j i-gab;int tmp array[i];for (;j 0; j - gab){if (array[j] tmp){array[jgab] array[j];}else {break;}}array[jgab] tmp;} }希尔排序的特性总结 希尔排序是对直接插入排序的优化。当gap 1时都是预排序目的是让集合更接近于有序。当gap 1时数组已经接近有序的了这样就会很快。希尔排序的时间复杂度不好计算因为gap的取值方法很多导致很难去计算因此在好些树中给出的希尔排序的时间复杂度都不固定按O(N1.25)到O(1.6*N1.25)来算稳定性不稳定 2.2 选择排序 2.2.1 基本思想 每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列起始位置直到全部待排序的数据元素排完。 2.2.2 直接选择排序 以i0遍历数组从i开始的数中找到最小大值下标minindexmaxindexminindexmaxindex和i位置的值进行交换。
  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;}}//最小值不是i位置的数据if(minindex ! i){swap(array,minindex,i);}} } //交换 private static void swap(int[] array,int i,int j) {int tmp array[i];array[i] array[j];array[j] tmp; }双向选择排序 1.从数组指定区间leftright内找到最小值和最值下标—minindex与maxindex 2.将其与区间端点值进行交换,缩小区间重复执行上述操作直到区间只剩下一个元素
  public static void selectSort(int[] array){int left 0;int right array.length-1;while(left right){int minindex left;int maxindex left;for (int i left; i right; i) {if (array[i] array[minindex]){minindex i;}if(array[i] array[maxindex]){maxindex i;}}//走到这里minindex和maxindex是区间leftright内的最小值和最值下标//最小值不是区间第一个元素if (minindex ! left){swap(array,minindex,left);}swap(array,maxindex,right);left;right–;} }直接选择排序的特性总结 直接选择排序思考非常好理解但是效率不是很好实际中很少使用时间复杂度O(N^2)空间复杂度O(1)稳定性不稳定 2.2.3 堆排序 堆排序(Heapsort)是指利用堆积树堆这种数据结构所设计的一种排序算法它是选择排序的一种。 步骤 1.建堆—-升序建大根堆降序建小根堆 2.利用堆删除思想进行排序 public static void heapSort(int[] array){//创建大根堆createHeap(array);//利用堆删除思想进行排序int end array.length-1;while(end 0){swap(array,0,end);sifiDown(array,0,end);end–;} } /**
• 创建大根堆 */ private static void createHeap(int[] array){//从最后一颗子树开始向下调整for (int parent (array.length-1)/2; parent 0 ; parent–) {sifiDown(array,parent,array.length);} } /**
• 向下调整 */ private static void sifiDown(int[] array,int parent,int length){int child 2*parent1;//至少存在左孩子while(child length){//存在右孩子 且 右孩子值大于左孩子if(child1 length array[child] array[child1]){child;}//走到这里child是孩子节点最大值的下标//父亲节点的值小于最大孩子节点值if(array[parent] array[child]){swap(array,parent,child);//子树向下调整parent child;child parent21;}else {break;}} }堆排序的特性总结 堆排序使用堆来选数效率就高了很多。时间复杂度O(N log ⁡ 2 N \log_{2}N log2​N)空间复杂度O(1)稳定性不稳定 2.3 交换排序 基本思想比较序列中两个值如果不满足排序要求交换两个值交换排序的特点是将值较大的向序列的尾部移动值较小的向序列的前部移动。 2.3.1 冒泡排序 j遍历集合j和j1对应的值比较如果j对应值大于j1对应值交换j向后走直至j指向最后一个元素一趟排序结束需要比较n-1趟冒泡排序特点每一趟确定一个数的位置且位置在待排序序列最后下一趟就可以少比较一个数趟数为n-1n是集合中元素的个数如果本趟没有进行交换说明集合已经排好序。
  public static void bubbleSort(int[] array){//i表示趟数for (int i 0; i array.length-1; i) {boolean flog false;for (int j 0; j array.length-1-i; j) {if(array[j] array[j1]){swap(array,j,j1);flog true;}}if(!flog){break;}} }//交换private static void swap(int[] array,int i,int j) {int tmp array[i];array[i] array[j];array[j] tmp;}冒泡排序的特性总结 冒泡排序是一种非常容易理解的排序时间复杂度O(N^2)空间复杂度O(1)稳定性稳定 2.3.2 快速排序 以区间内第一个数为基准值将整个区间划分为两个子序列左子序列都是比基准值小的数右子序列都是比基准值大的数对左、右子序列为新的区间进行前面操作直至区间只存在一个元素。 public static void quick(int[] array,int left,int right){//区间不存在或区间只有一个元素if(left right){return;}//按基准值对数组的leftright区间进行划分 并返回基准值所在下标int pivot partion(array,left,right);//对数组的leftpivot区间进行快速排序quick(array,left,pivot-1);//对数组的pivot1right区间进行快速排序quick(array,pivot1,right);}将区间按照基准值划分为左右两半部分的常见方式有 1. Hoare 版
  private static int partion(int[] array,int left,int right){int tmp array[left];int i left;while(left right){while (left right array[right] tmp){right–;}while(left right array[left] tmp){left;}swap(array,left,right);}swap(array,i,left);return left;}2. 挖坑法
  private static int partion(int[] array,int left,int right){int tmp array[left];while (left right){while (left right array[right] tmp){right–;}//走到这right是比基准值小的下标或left rightarray[left] array[right];while (left right array[left] tmp){left;}//走到这left是比基准值大的下标或left rightarray[right] array[left];}//基准值放入坑中array[left] tmp;return left;}3. 前后指针法 写法一 private static int partion(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,left,prev);return prev; }写法二 private static int partition(int[] array, int left, int right) {int d left 1;int pivot array[left];for (int i left 1; i right; i) {if (array[i] pivot) {swap(array, i, d);d;}}swap(array, d - 1, left);return d - 1; }2.3.3 快速排序优化 1.三数取中法选key 在下标为left区间第一个数下标、right区间最后一个数下标和mid区间中间数下标对应数值中找到中间数与区间第一个数进行交换使得以基准值区间第一个数划分的尽可能使左右区间都超过一个数从而减少递归次数。 private static void quick(int[] array,int start,int end) {if(start end) {return;}//1 2 3 4 5 6 7int index middleNum(array,start,end);swap(array,index,start);//4 2 3 1 5 6 7int pivot partition(array,start,end);quick(array,start,pivot-1);quick(array,pivot1,end); } /**
• 求中位数的下标 */ private static int middleNum(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 {//array[left] array[right]if(array[mid] array[right]) {return right;}else if(array[mid] array[left]) {return left;}else {return mid;}} }2. 递归到小的子区间时可以考虑使用插入排序 private static void quick(int[] array,int start,int end) {if(start end) {return;}//区间比较小if(end - start 1 15) {insertSort(array, start, end);return;}int pivot partition(array,start,end);quick(array,start,pivot-1);quick(array,pivot1,end); } public static void insertSort(int[] array,int left,int right) {for (int i left1; i right; i) {int tmp array[i];int j i-1;for (; j left ; j–) {if(array[j] tmp) {array[j1] array[j];}else {break;}}array[j1] tmp;} }2.3.4 快速排序非递归 /快速排序非递归 */ public static void quickSortNor(int[] array){int start 0;int end array.length-1;//存放要排序的区间端点下标StackInteger stack new Stack();//基准值下标int privot partion(array,start,end);//基准值的左边左区间的元素至少有2个if(privot-1 start){stack.push(start);stack.push(privot-1);}//基准值的右边右区间的元素至少有2个if(privot1 end){stack.push(privot1);stack.push(end);}while ( !stack.isEmpty()){end stack.pop();start stack.pop();privot partion(array,start,end);//基准值的左边左区间的元素至少有2个if(privot-1 start){stack.push(start);stack.push(privot-1);}//基准值的右边右区间的元素至少有2个if(privot1 end){stack.push(privot1);stack.push(end);}} }快速排序总结 1.快速排序整体的综合性能和使用场景都比较好 2.时间复杂度O(N*logN) 3. 空间复杂度O(logN) 4. 稳定性不稳定 2.4 归并排序 2.4.1 基本思想 归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。
  /递归实现排序*/public static void mergeSort(int[] array){merge(array,0,array.length-1); } private static void merge(int[] array, int left, int right) {if(left right){return;}int mid (left right)/ 2;//划分为两组merge(array,left,mid);merge(array,mid1,right);//合并combine(array,left,mid,right); } /**合并两个有序数组 */ private static void combine(int[] array, int left, int mid, int right) {//第一个数组的区间端点下标int s1 left;int e1 mid;//第二个数组的区间端点下标int s2 mid1;int e2 right;//新数组的长度int length right-left1;int[] arr new int[length];//新数组下标int k 0;//合并while( s1 e1 s2 e2){if(array[s1] array[s2]){arr[k] array[s1];}else {arr[k] array[s2];}}while (s1 e1){arr[k] array[s1];}while (s2 e2){arr[k] array[s2];}//将合并的新数组放入原来数组对应位置for (int i 0; i arr.length; i) {array[ileft] arr[i];} }//非递归 public static void mergeSortNor(int[] array){//每个子序列元素个数int gap 1;while( gap array.length){for (int i 0; i array.length; igap*2) {//left 代表一组的第一个元素下标int left i;//mid 代表此组最后一个元素下标int mid leftgap-1;if(mid array.length){mid array.length-1;}//right 代表下一组的最后一个元素下标int right midgap;if(right array.length){right array.length-1;}combine(array,left,mid,right);}gap * 2;} }归并排序总结 归并的缺点在于需要O(N)的空间复杂度归并排序更多是解决在磁盘中的外排序问题时间复杂度: O(N*logN)空间复杂度O(logN)稳定性稳定 2.4.2 海量数据的排序问题 外部排序排序过程需要在磁盘等外部存储进行的排序 前提内存只有 1G需要排序的数据有 100G 因为内存中因为无法把所有数据全部放下所以需要外部排序而归并排序是最常用的外部排序 先把文件切分成 200 份每个 512 M分别对 512 M 排序因为内存已经可以放的下所以任意排序方式都可以进行 2路归并同时对 200 份有序文件做归并过程最终结果就有序了 三、排序算法复杂度及稳定性分析 四、其他非基于比较排序 1.计数排序 计数排序以数组来实现数组的下标是待排序序列值数组存储的是元素出现的个数。操作步骤 统计待排序序列中各个元素的个数到新数组遍历新数组将原序列进行覆盖 public static void countSort(int[] array){//获取集合中的最大值和最小值int minvalue array[0];int maxvalue array[0];for (int i 0; i array.length; i) {if(array[i] minvalue){minvalue array[i];}if(array[i] maxvalue){maxvalue array[i];}}//新建数组长度int length maxvalue-minvalue1;//以数组值存储元素的个数数组的下标值为元素值-minvalue的结果int[] count new int[length];//记录集合中元素个数for (int i 0; i array.length; i) {count[array[i]-minvalue];}//array下标int k 0;//遍历count数组将实际值重写回array中for (int i 0; i count.length; i) {while( count[i] 0){array[k] iminvalue;count[i]–;}} }计数排序总结 3. 计数排序在数据范围集中时效率很高但是适用范围及场景有限。 4. 时间复杂度O(MAX(N,范围)) 5. 空间复杂度O(范围) 6. 稳定性稳定 2.基数排序 基数排序 3.桶排序 桶排序 五.选择题

1. 快速排序算法是基于()的一个排序算法。 A分治法 B贪心法 C递归法 D动态规划法 2.对记录54,38,96,23,15,72,60,45,83进行从小到大的直接插入排序时当把第8个记录45插入到有序表时为找到插入位置需比较()次采用从后往前比较 A: 3 B: 4 C: 5 D: 6 3.以下排序方式中占用O(n)辅助存储空间的是() A: 简单排序 B: 快速排序 C: 堆排序 D: 归并排序 4.下列排序算法中稳定且时间复杂度为O(n^2)的是() A: 快速排序 B: 冒泡排序 C: 直接选择排序 D: 归并排序 5.关于排序下面说法不正确的是() A: 快排时间复杂度为O(N*logN)空间复杂度为O(logN) B: 归并排序是一种稳定的排序,堆排序和快排均不稳定 C: 序列基本有序时快排退化成 冒泡排序直接插入排序最快 D: 归并排序空间复杂度为O(N), 堆排序空间复杂度的为O(logN) 6.设一组初始记录关键字序列为(65,56,72,99,86,25,34,66)则以第一个关键字65为基准而得到的一趟快速排序结果是 A: 3456256586997266 B: 2534566599867266 C: 3456256566998672 D: 3456256599867266答案1.A 2.C 3.D 4.B 5.D 6.A