遵义市营商环境建设局网站,百度关键词排名点,网站建设制作费 税前扣除吗,品牌高端网站建设公司直接插入排序 直接插入排序#xff08;Straight Insertion Sorting#xff09;的基本思想#xff1a;在要排序的一组数中#xff0c;假设前面(n-1) [n2] 个数已经是排好顺序的#xff0c;现在要把第n个数插到前面的有序数中#xff0c;使得这n个数也是排好顺序的。如…直接插入排序 直接插入排序Straight Insertion Sorting的基本思想在要排序的一组数中假设前面(n-1) [n2] 个数已经是排好顺序的现在要把第n个数插到前面的有序数中使得这n个数也是排好顺序的。如此反复循环直到全部排好顺序。 直接插入排序是一种稳定的排序方法,最好的时间复杂是O(n)也就是已经排好的序列,最差的时间复杂度是O(n^2)逆序 //插入排序是一种稳定的排序方法,最好的时间复杂是O(n)也就是已经排好的序列,最差的时间复杂度是O(n^2)逆序 public void insertSort(int nums[]){ int tmp; for(int i1;inums.length;i){ int ji; while (j0 nums[j]nums[j-1]){ tmpnums[j]; nums[j]nums[j-1]; nums[j-1]tmp; j--; } } } 希尔排序 希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”Diminishing Increment Sort是直接插入排序算法的一种更高效的改进版本。 希尔排序是把记录按下标的一定增量分组对每组使用直接插入排序算法排序随着增量逐渐减少每组包含的关键词越来越多当增量减至1时整个文件恰被分成一组算法便终止。 算法思想 对于直接插入排序问题数据量巨大时。将数的个数设为n取奇数kn/2将下标差值为k的数分为一组构成有序序列。再取kk/2 将下标差值为k的书分为一组构成有序序列。重复第二步直到k1执行简单插入排序。
希尔排序是一种非常不稳定的排序方法它的时间复杂度为O(n^1.3—2)
//希尔排序是一个不稳定的排序算法,它的时间复杂度为O(n^1.3—2) public void shellSortHelper(int nums[],int incr){ int tmp; for(int iincr;inums.length;iincr){ int ji; while (j0 nums[j]nums[j-incr]){ tmpnums[j]; nums[j]nums[j-incr]; nums[j-incr]tmp; j-incr; } } } //希尔排序 public void shellSort(int nums[]){ for(int inums.length/2;i 0;i/2){ shellSortHelper(nums,i); } } 选择排序 常用于取序列中最大最小的几个数时。 (如果每次比较都交换那么就是交换排序如果每次比较完一个循环再交换就是简单选择排序。)
遍历整个序列将最小的数放在最前面。
遍历剩下的序列将最小的数放在最前面。
重复第二步直到只剩下一个数。
选择排序的时间复杂度为O(n^2) 选择排序不是一个稳定的排序
//交换排序是一种稳定的排序方法最好最坏的时间复杂度都是O(n^2) public void swapSort(int nums[]) { int tmp; for(int i0;inums.length;i){ for(int ji1;jnums.length;j){ if(nums[i]nums[j]){ tmpnums[j]; nums[j]nums[i]; nums[i]tmp; } } } } //选择排序是一种不稳定的排序方法最好最坏的时间复杂度都是O(n^2) public void selectSort(int nums[]){ for(int i0;inums.length;i){ int valuesnums[i]; int positioni; for(int ji1;jnums.length;j){ if(nums[j]values){ valuesnums[j]; positionj; } } //swap nums[position]nums[i]; nums[i]values; } 冒泡排序 很简单用到的很少据了解面试的时候问的比较多将序列中所有元素两两比较将最大的放在最后面。将剩余序列中所有元素两两比较将最大的放在最后面。重复第二步直到只剩下一个数。
冒泡排序的时间复杂度为O(n^2) 冒泡排序是一个稳定的排序 //冒泡排序 一种稳定的排序算法最好最坏的时间复杂度都是O(n^2) public void bubbleSort(int nums[]){ int tmp; for(int i0;inums.length;i){ for (int j0;jnums.length-i-1;j){ if(nums[j]nums[j1]){ tmpnums[j1]; nums[j1]nums[j]; nums[j]tmp; } } } } 快速排序 要求时间最快时。
选择第一个数为p小于p的数放在左边大于p的数放在右边。 递归的将p左边和右边的数都按照第一步进行直到不能递归。 快速排序是由一种不稳定的排序算法最好的时间复杂度是O(nLogN)最差时间复杂度是O(n^2) //快速排序是由一种不稳定的排序算法最好的时间复杂度是O(nLogN)最差时间复杂度是O(n^2) private void quickSortHelper(int nums[],int start,int end){ if(startend) return; int highend; int lowstart; int targetnums[start]; while (lowhigh){ while (lowhigh nums[high]target){ high--; } nums[low]nums[high]; while (lowhigh nums[low]target){ low; } nums[high]nums[low]; } nums[low]target; quickSortHelper(nums,start,low-1); quickSortHelper(nums,low1,end); } public void quickSort(int nums[]) { quickSortHelper(nums,0,nums.length-1); } 归并排序 速度仅次于快速排序内存少的时候使用可以进行并行计算的时候使用。
选择相邻两个数组成一个有序序列。 选择相邻的两个有序序列组成一个有序序列。重复第二步直到全部组成一个有序序列。 归并排序,是一种稳定的排序是算法这个算法的时间复复杂度都是O(NlogN) //归并排序,是一种稳定的排序是算法这个算法的时间复复杂度都是O(NlogN) public void mergeSrot(int nums[],int start,int end){ if(startend) return; int mid(startend)/2; mergeSrot(nums,start,mid); mergeSrot(nums,mid1,end); mergeSrotHelper(nums,start,mid,end); } // 将两个有序序列归并为一个有序序列(二路归并) private void mergeSrotHelper(int[] nums, int start, int mid, int end) { int[] arrnew int[end1]; int lowstart; int leftstart; int centermid1; while (leftmid centerend){ arr[low] nums[left] nums[center] ? nums[left] : nums[center]; } while (leftmid){ arr[low]nums[left]; } while (centerend){ arr[low]nums[center]; } for(int istart;iend;i){ nums[i]arr[i]; } } 堆排序 对简单选择排序的优化。
将序列构建成大顶堆。 将根节点与最后一个节点交换然后断开最后一个节点。 重复第一、二步直到所有节点断开。 //堆排序 private boolean isLeaf(int nums[],int pos) { //没有叶子节点 return pos*21nums.length; } private void swap(int[] nums,int pos1,int pos2) { int tmp; tmpnums[pos2]; nums[pos2]nums[pos1]; nums[pos1]tmp; } private void shiftdown(int[] nums,int pos) { while(!isLeaf(nums,pos)) { int leftpos*21; int rightpos*22; if(rightnums.length) { leftnums[left]nums[right]?left:right; } //是否需要调整堆 if(nums[pos]nums[left]) return; swap(nums,pos,left); posleft; } } public void buildHeap(int nums[]) { for(int inums.length/2-1;i0;i--) { shiftdown(nums,i); } } public void heapSort(int nums[]) { for(int inums.length-1;i0;i--) { swap(nums,0,i); shiftdown(nums,i); } } 总结 一、稳定性: 稳定冒泡排序、插入排序、归并排序和基数排序 不稳定选择排序、快速排序、希尔排序、堆排序 二、平均时间复杂度 O(n^2):直接插入排序简单选择排序冒泡排序。
在数据规模较小时9W内直接插入排序简单选择排序差不多。当数据较大时冒泡排序算法的时间代价最高。性能为O(n^2)的算法基本上是相邻元素进行比较基本上都是稳定的。
O(nlogn):快速排序归并排序希尔排序堆排序。
其中快排是最好的其次是归并和希尔堆排序在数据量很大时效果明显。
三、排序算法的选择 数据规模较小 1待排序列基本序的情况下可以选择直接插入排序
2对稳定性不作要求宜用简单选择排序对稳定性有要求宜用插入或冒泡
数据规模不是很大 1完全可以用内存空间序列杂乱无序对稳定性没有要求快速排序此时要付出logN的额外空间。
2序列本身可能有序对稳定性有要求空间允许下宜用归并排序
数据规模很大 1对稳定性有求则可考虑归并排序。
2对稳定性没要求宜用堆排序
