免费网站建设合同范本,亚马逊电商平台怎么入驻,海外高端网站建设,酒类销售公司的网站建设排序的概念 排序#xff1a;所谓排序#xff0c;就是使一串记录#xff0c;按照其中的某个或某些关键字的大小#xff0c;递增或递减的排列起来的操稳定性#xff1a;假定在待排序的记录序列中#xff0c;存在多个具有相同的关键字的记录#xff0c;若经过排序#xff…
排序的概念 排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持不变即在原序列中r[i]r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前则称这种排序算法是稳定的否则称为不稳定的 内部排序数据元素全部放在内存中的排序。 外部排序数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序。 插入排序 基本思想 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列 。 直接插入排序的特性总结
元素集合越接近有序直接插入排序算法的时间效率越高时间复杂度O(N^2)空间复杂度O(1)它是一种稳定的排序算法稳定性稳定 一个本身就稳定的排序 可以实现为不稳定 但是一个本身就不稳定的排序 不可能实现为稳定的排序 希尔排序( 缩小增量排序 ) 希尔排序法的基本思想是先选定一个整数把待排序文件中所有记录分成多个组所有距离为的记录分在同一组内并对每一组内的记录进行排序。然后取重复上述分组和排序的工作。当到达gap1时所有记录在统一组内排好序。 希尔排序的特性总结
希尔排序是对直接插入排序的优化。当gap 1时都是预排序目的是让数组更接近于有序。当gap 1时数组已经接近有序的了这样就会很快。希尔排序的时间复杂度不好计算因为gap的取值方法很多导致很难去计算。我们就记为n^1.3稳定性不稳定 选择排序 基本思想 每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完 。 选择排序的第二种写法 有两个疑点 1. 2.当left等于right时说明当前下标的左边已经排号当前下标的右边也已经排好那么当前下标的值一定是中间值 【直接选择排序的特性总结】
直接选择排序思考非常好理解但是效率不是很好。实际中很少使用时间复杂度O(N^2)空间复杂度O(1)稳定性不稳定 堆排序 它是通过堆来进行选择数据。 堆排序使用堆来选数效率就高了很多。时间复杂度O(N*logN)空间复杂度O(1)稳定性不稳定 冒泡排序 快速排序 快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法其基本思想为任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。 上述为快速排序递归实现的主框架发现与二叉树前序遍历规则非常像同学们在写递归框架时可想想二叉树前序遍历规则即可快速写出来后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。 Hoare版 挖坑法 快速排序优化
三数取中法选key目的将待排序数组分开不要只有左边或者只有右边 递归到小的子区间时可以考虑使用插入排序。因为这时的区间元素已经趋近于有序 快速排序非递归形式 采用栈 快速排序总结
快速排序整体的综合性能和使用场景都是比较好的所以才敢叫快速排序时间复杂度O(N*logN)空间复杂度O(logN)稳定性不稳定 归并排序 基本思想 归并排序MERGE-SORT是建立在归并操作上的一种有效的排序算法,该算法是采用分治Divide andConquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。 非递归形式实现归并排序 归并排序总结
归并的缺点在于需要O(N)的空间复杂度归并排序的思考更多的是解决在磁盘中的外排序问题。时间复杂度O(N*logN)空间复杂度O(N)稳定性稳定 海量数据的排序问题 外部排序排序过程需要在磁盘等外部存储进行的排序 前提内存只有 1G需要排序的数据有 100G 因为内存中因为无法把所有数据全部放下所以需要外部排序而归并排序是最常用的外部排序
先把文件切分成 200 份每个 512 M分别对 512 M 排序因为内存已经可以放的下所以任意排序方式都可以进行 2路归并同时对 200 份有序文件做归并过程磁盘IO读写最终结果就有序了 排序算法复杂度及稳定性分析 其他非基于比较排序 计数排序 思想计数排序又称为鸽巢原理是对哈希直接定址法的变形应用。 操作步骤
统计相同元素出现次数根据统计的结果将序列回收到原来的序列中 基数排序 基数排序是一种非比较型整数排序算法其原理是将整数按位数切割成不同的数字然后按每个位数分别比较。由于整数也可以表达字符串比如名字或日期和特定格式的浮点数所以基数排序也不是只能使用于整数。 桶排序 上述涉及的所有代码 Sort.java
import java.util.Arrays;
import java.util.Stack;/*** Created with IntelliJ IDEA.* Description:* User: Home-pc* Date: 2023-08-26* Time: 12:04*/
public class Sort {Overridepublic String toString() {return Sort{};}public static void insertSort(int[] array ){for (int i 1; i array.length; i) {int temparray[i];//记录当前的元素准备随时插入同时放置元素被覆盖掉int ji-1;for (; j0; j--) {if(array[j]temp){//当前j下标的元素后移array[j1]array[j];}else{break;}}array[j1]temp;//没有j下标的元素大插入它的后面}}//public static void shell(int[] array,int gap){for (int i gap; i array.length; i) {//这里的i可以针对每一个分组int temparray[i];//记录当前的元素准备随时插入同时放置元素被覆盖掉int ji-gap;for (; j0; j-gap) {if(array[j]temp){//当前j下标的元素后移array[jgap]array[j];}else{break;}}array[jgap]temp;//没有j下标的元素大插入它的后面}}public static void shellSort(int[] array){int gaparray.length;while(gap1){gap/2;shell(array,gap);//这里在最后一定会进行一次gap1的插入排序}}//public static void selectSort(int[] array){for(int i0;i array.length;i){int minIndexi;for (int j i1; j array.length; j) {if(array[j]array[minIndex]){minIndexj;}}swap(array,i,minIndex);}}private static void swap(int[] array,int i,int j){int temparray[i];array[i]array[j];array[j]temp;}//public static void selectSort2(int[] array){int left0;int right array.length-1;while(leftright){int minIndexleft;int maxIndexleft;for (int i left1; i right; i) {if(array[i]array[minIndex]){minIndexi;}if(array[i]array[maxIndex]){maxIndexi;}}swap(array,minIndex,left);if(leftmaxIndex){maxIndexminIndex;}swap(array,maxIndex,right);left;right--;}}//public static void heapSort(int[] array){createBigHeap(array);int end array.length-1;while(end0){swap(array,end,0);shiftDown(array,0,end);end--;}}private static void createBigHeap(int[] array){for (int i (array.length-1-1)/2; i0; i--) {shiftDown(array,i, array.length);}}private static void shiftDown(int[] array,int parent,int len){int childparent*21;while(childlen){if(child1len array[child]array[child1]){childchild1;}if(array[child]array[parent]){swap(array,child,parent);parentchild;childparent*21;}else{break;}}}//public static void bubbleSort(int[] arrary){for (int i 0; i arrary.length-1; i) {boolean flagfalse;for (int j 0; j arrary.length-1-i; j) {if(arrary[j]arrary[j1]){swap(arrary,j,j1);flagtrue;}}if(!flag){break;}}}//public static void quickSort(int[] array){quick(array,0,array.length-1);}private static void quick(int[] array,int start,int end){if(startend){return;}//直接插入排序优化if(end-start110){insertSortForQuick(array,start,end);return;}//三数取中优化int midthreeNum(array,start,end);swap(array,mid,start);int pivotparttion(array,start,end);//求出基准值依次为中间值划分序列quick(array,start,pivot-1);//左数quick(array,pivot1,end);//右数}public static void insertSortForQuick(int[] array,int left,int right ){for (int i left1; i right; i) {int temparray[i];//记录当前的元素准备随时插入同时放置元素被覆盖掉int ji-1;for (; jleft; j--) {if(array[j]temp){//当前j下标的元素后移array[j1]array[j];}else{break;}}array[j1]temp;//没有j下标的元素大插入它的后面}}private static int parttion1(int[] array,int left,int right){int ileft;int temparray[left];//拿这个值和其它元素比较while(leftright){while(leftright array[right]temp){//找到右边第一个比temp小的值right--;}while(leftright array[left]temp){//找到左边第一个比temp大的值left;}swap(array,left,right);//交换这两个值}swap(array,left,i);//交换某个中间值和temp的值使得temp为真正的中间值return left;//返回这个中间位置的下标}//private static int parttion(int[] array,int left,int right){int temparray[left];while(leftright){while(leftright array[right]temp){right--;}array[left]array[right];while(leftright array[left]temp){left;}array[right]array[left];}array[right]temp;return left;}//优化三数取中private static int threeNum(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{if(array[mid]array[right]){return right;}else if(array[mid]array[left]){return left;}else{return mid;}}}//非递归实现public static void quickSortByStack(int[] array){StackInteger stacknew Stack();stack.push(array.length-1);//这里先push的右边后push的左边stack.push(0);while(!stack.empty()){int leftstack.pop();int rightstack.pop();if(leftright){//成立说明该区间排序结束continue;}int indexparttion(array,left,right);stack.push(right);stack.push(index1);stack.push(index-1);stack.push(left);}}//归并private static void merge(int[] array,int left,int mid,int right){//两个有序组合并为一个有序组int s1left;int e1mid;int s2mid1;int e2right;//看似拆分为了两组实际是一直在一个数组中进行的操作int[] tmpArrnew int[right-left1];//用于存放合并后的数组int k0;while(s1e1s2e2){//if(array[s1]array[s2]){//将s1放入数组中tmpArr[k]array[s1];}else{tmpArr[k]array[s2];}}while(s1e1){tmpArr[k]array[s1];}while(s2e2){tmpArr[k]array[s2];}for (int i 0; i k; i) {array[ileft]tmpArr[i];//tmpArr数组的首元素的下标不一定为0但一定为left}}private static void mergeSortFunc(int[] array,int left,int right){if(leftright){//最小拆分组的数量为1return;}int mid(leftright)/2;mergeSortFunc(array,left,mid);mergeSortFunc(array,mid1,right);//递归拆分至最小组准备排序后合并merge(array,left,mid,right);}public static void mergeSort1(int[] array){mergeSortFunc(array,0,array.length-1);}//非递归归并public static void mergeSort(int[] array){int gap1;while(gaparray.length){for (int i 0; i array.length; igap*2) {int lefti;int midleftgap-1;int rightmidgap;//mid和right可能越界这里我们将其归置到一个数组中if(midarray.length){midarray.length-1;}if(rightarray.length){rightarray.length-1;}merge(array,left,mid,right);}gap*2;}}//计数排序public static void countArray(int[] array){int maxValarray[0];int minValarray[0];for (int i 0; i array.length; i) {//找到数组里的最大值和最小值if(array[i]minVal){minValarray[i];}if(array[i]maxVal){maxValarray[i];}}//建立一个计数的数组int rangemaxVal-minVal1;int[] countnew int[range];//遍历数组做计数统计for (int i 0; i array.length; i) {int valarray[i];count[val-minVal];}//遍历计数数组并重写array数组的元素int index0;for (int i 0; i count.length; i) {int valcount[i];while(val!0){array[index]iminVal;val--;}}}
}
测试代码
import com.sun.scenario.effect.impl.sw.sse.SSEBlend_SRC_OUTPeer;import java.util.Arrays;
import java.util.Random;/*** Created with IntelliJ IDEA.* Description:* User: Home-pc* Date: 2023-08-26* Time: 13:48*/
public class TestSort {public static void notOrderArray(int[] array){Random randomnew Random();for (int i 0; i array.length; i) {array[i]random.nextInt(100);}}public static void testShellSort(int[] array){arrayArrays.copyOf(array,array.length);Sort.shellSort(array);System.out.println(Arrays.toString(array));}public static void testSelectSort(int[] array){arrayArrays.copyOf(array,array.length);Sort.selectSort(array);System.out.println(Arrays.toString(array));}public static void testSelectSort2(int[] array){arrayArrays.copyOf(array,array.length);Sort.selectSort2(array);System.out.println(Arrays.toString(array));}public static void testheapSort(int[] array){arrayArrays.copyOf(array,array.length);Sort.heapSort(array);System.out.println(Arrays.toString(array));}public static void testbubbleSort(int[] array){arrayArrays.copyOf(array,array.length);Sort.bubbleSort(array);System.out.println(Arrays.toString(array));}public static void testquickSort(int[] array){arrayArrays.copyOf(array,array.length);//long startTimeSystem.currentTimeMillis();Sort.quickSort(array);//long endTimeSystem.currentTimeMillis();System.out.println(Arrays.toString(array));//System.out.println(优化后排序时间(endTime-startTime));}public static void testquickSortByStack(int[] array){arrayArrays.copyOf(array,array.length);//long startTimeSystem.currentTimeMillis();Sort.quickSortByStack(array);//long endTimeSystem.currentTimeMillis();System.out.println(Arrays.toString(array));//System.out.println(优化后排序时间(endTime-startTime));}public static void testmergeSort(int[] array){arrayArrays.copyOf(array,array.length);//long startTimeSystem.currentTimeMillis();Sort.mergeSort(array);//long endTimeSystem.currentTimeMillis();System.out.println(Arrays.toString(array));//System.out.println(优化后排序时间(endTime-startTime));}public static void testcountArray(int[] array){arrayArrays.copyOf(array,array.length);//long startTimeSystem.currentTimeMillis();Sort.countArray(array);//long endTimeSystem.currentTimeMillis();System.out.println(Arrays.toString(array));//System.out.println(优化后排序时间(endTime-startTime));}public static void main(String[] args) {int[] arraynew int[30];notOrderArray(array);System.out.println(Arrays.toString(array));testShellSort(array);notOrderArray(array);System.out.println(Arrays.toString(array));testSelectSort(array);notOrderArray(array);System.out.println(Arrays.toString(array));testSelectSort2(array);notOrderArray(array);System.out.println(Arrays.toString(array));testheapSort(array);notOrderArray(array);System.out.println(Arrays.toString(array));testbubbleSort(array);notOrderArray(array);System.out.println(Arrays.toString(array));testquickSort(array);notOrderArray(array);System.out.println(Arrays.toString(array));testquickSortByStack(array);System.out.println(我是分割线);notOrderArray(array);System.out.println(Arrays.toString(array));testmergeSort(array);System.out.println(我是分割线);notOrderArray(array);System.out.println(Arrays.toString(array));testcountArray(array);}
}
***
