怎么导入网站源码,wordpress备案号代码,如何制作wap网站,天津装修设计平台本章讲述数据结构中的六大排序算法 欢迎大佬们踊跃讨论#xff0c;感谢大家支持#xff01; 我的博客主页链接 六大排序算法 一.插入排序1.1 直接插入排序1.2 希尔排序 二.选择排序2.1 单向选择排序2.2双向选择排序2.3 堆排序 三.交换排序3.1 冒泡排序3.2 快速排序3.2.1 Hoa… 本章讲述数据结构中的六大排序算法 欢迎大佬们踊跃讨论感谢大家支持 我的博客主页链接 六大排序算法 一.插入排序1.1 直接插入排序1.2 希尔排序 二.选择排序2.1 单向选择排序2.2双向选择排序2.3 堆排序 三.交换排序3.1 冒泡排序3.2 快速排序3.2.1 Hoare排序3.2.2 挖坑法3.2.3 前后指针法3.4 非递归快速排序 四.归并排序4.1 递归归并排序4.2非递归归并排序 五.测试运行时间代码 一.插入排序
1.1 直接插入排序 1.已知第一个元素如果不包含其他元素没有元素可以比较为有序。 2.我们可以直接从第二个元素i开始创建一个对象tmp来接下标元素如果比前一个元素小前一个元素往后移动tmp插入i-1下标 3.当元素大于或者等于时则tmp直接放在i位置即可。 public static void insertSort(int[] array){for(int i1;iarray.length;i){//由数组1下标开始进行比较int tmparray[i];int ji-1;for(;j0;j--){if(tmparray[j]){array[j1]array[j];//将j放入j1位置}else{//进入else则为有序break跳出嵌套循环break;}}//当嵌套的for循环一直在比较最小值tmp知道为-1跳出循环这里需要j1//当大于时候因为i-1赋值给jbreak跳出后j需要1下标值得到tmparray[j1]tmp;}}时间复杂度:最坏情况时间复杂度为O(N*N) 最好情况时间复杂度为O(N) 空间复杂度O(1) 稳定排序 1.2 希尔排序 希尔排序又称缩小增量法。 希尔排序的思想定义一个整数将待排序数组元素长度分成多个组每一个组进行插入排序重复上述分组此时为预排序。当到达1时将所有记录好的元素在一组中进行排序。 每一次分组排序后都变为有序每组数据由少变多越来越有序。 划分为n/2组进行比较根据n/2的距离来划分每一组的数量。 public static void shellSort(int[] array){int gaparray.length;while(gap1){gap/2;//将数组/2有多组变少组直到为1shell(array,gap);}}public static void shell(int[] arr,int gap){//从gap开始遍历for(int igap;iarr.length;i){//获取gap下标的值int tmparr[i];求i-gap个差距得到j值int ji-gap;for(;j0;j-gap){if(tmparr[j]){arr[jgap]arr[j];}else{break;}}arr[jgap]tmp;}}时间复杂度O(N^1.25) 空间复杂度O(1) 二.选择排序
2.1 单向选择排序 单向选择排序通过定义minIndex值来获取最小的元素下标然后与0下标进行交换 public static void selectSort2(int[] array){for(int i0;iarray.length;i){int minIndexi;for(int ji1;jarray.length;j){if(array[j]array[minIndex]){minIndexj;}}swap(array,minIndex,i);}}2.2双向选择排序 双向选择排序是我们通过定义起始位置和终点位置的下标作为条件通过初始位置筛选最大值和最小值的下标将最大值下标与尾部交换最小值下标与初始位置交换然后继续重复上述知道筛选完成。 这里如果max的最大值为0下标的时候max已经被 minIndex交换maxIndex等于minIndex获取最大元素的下标值即可。 public static void selectSort(int[] array){//起始位置和末尾的下标值int left0;int rightarray.length-1;while(leftright){//都从0下标开始比较int maxIndexleft;int minIndexleft;for(int ileft1;iright;i){if(array[i]array[minIndex]) minIndexi;if(array[i]array[maxIndex]) maxIndexi;}swap(array,left,minIndex);//如果0下标就是maxIndex的最大值minIndex的位置就是maxIndex的最大值if(maxIndexleft)maxIndexminIndex;swap(array,right,maxIndex);left;right--;}} 时间复杂度O(N^2) 空间复杂度O(1) 2.3 堆排序
堆序详情堆排序 //创建二叉堆public static void createHeap(int[] array){for(int parent(array.length-1-1)/2;parent0;parent--){siftDown(array,parent,array.length);}}private static void siftDown(int[] array,int parent,int size) {int child2*parent1;while(childsize){if(child1sizearray[child]array[child1]){//child是左右孩子的最大值childchild1;}if(array[child]array[parent]){//交换孩子与父亲swap(array,child,parent);//调整父亲节点和孩子节点parentchild;child(2*parent)1;}else{break;}}}//根据创建好的大跟堆通过最后一个下标与0下标交换后缩小堆的范围直到称为有序数组public static void heapSort(int[] array){createHeap(array);int endarray.length-1;while(end0){swap(array,0,end);siftDown(array,0,end);end--;}}时间复杂度O(N*logN) 空间复杂度O(1) 三.交换排序
3.1 冒泡排序 冒泡排序是一种较为简单的排序算法它循环需要排序的元素依次比较相邻的两个元素如果顺序错误就进行交换直至没有元素交换完成排序若对数组n个元素进行比较则需要比较n-1次最后一个元素已经被前n-1个元素排序好。 排序一次将len-1最大值放到最后直到有序 本代码中的flag来记录是否有序如果有序则直接跳出循环。 public static void bubbleSort(int[] array){for(int i0;iarray.length-1;i){boolean flagfalse;//这里标记一下每一趟中给flag置为false当每趟为有序后则不进入if语句直接停止循环for(int j0;jarray.length-1-i;j){if(array[j]array[j1]){swap(array,j,j1);flagtrue;}}if(!flag){break;}}}时间复杂度最好情况下O(n) 最坏情况下O(n^2) 空间复杂度:O(1) 稳定排序 3.2 快速排序
3.2.1 Hoare排序 1.首先设定一个分界值通过该分界值将数组分成左右两部分。 2、将大于或等于分界值的数据集中到数组右边小于分界值的数据集中到数组的左边。此时左边部分中各元素都小于分界值而右边部分中各元素都大于或等于分界值。 3、然后左边和右边的数据可以独立排序。对于左侧的数组数据又可以取一个分界值将该部分数据分成左右两部分同样在左边放置较小值右边放置较大值。右侧的数组数据也可以做类似处理。 4、重复上述过程可以看出这是一个递归定义。通过递归将左侧部分排好序后再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后整个数组的排序也就完成了。 这里定义一个left为左right为右将任意左右位置两边定义一个基准值根据基准值的大小直到left为大于基准值数right为小于基准值数停下若定义左边为基准值则右边先走同理右边为基准值左边先走。 //快速排序public static void quickSort(int[] array){//记录左起始位置和右边的结束位置进行递归quick(array,0,array.length-1);}
public static void inSert(int[] array,int left,int right){for(int ileft1;iright;i){int tmparray[i];int ji-1;for(;jleft;j--){if(array[j]tmp){array[j1]array[j];}else {break;}}array[j1]tmp;}}private static void quick(int[] array, int left, int right) {if(leftright)return ;//说明两个相遇或者走出范围//当长度少时直接插入排序if(right-left110){inSert(array,left,right);return ;}int index middleNum(array,left,right);System.out.println(index下标值:index);//用来交换left和right范围内元素且最终将首位元素与相遇值交换swap(array,left,index);int pospartitionPointer(array,left,right);//递归quick(array,left,pos-1);quick(array,pos1,right);}private static int partitionHoare(int[] array, int left, int right) {int recordleft;//记录left最后交换int tmparray[left];//比较大小while(leftright){while(leftrightarray[right]tmp){//右边找到小于tmpright--;}while(leftrightarray[left]tmp){//左边找到大于tmpleft;}swap(array,left,right);}//这里left与right相遇swap(array,record,left);return left;}时间复杂度最坏情况下N*(logN) 最好情况下O(N^2) 有序或者逆序情况下 空间复杂度:最好情况下O(logN) 最坏情况下O(N) 有序或者逆序情况下 数据多时因递归可能容易栈溢出 3.2.2 挖坑法 1.由左或者右选出第一个坑位记录元素值放入key中创建left和right对数组遍历当选左坑右走右坑左走直到right和left相遇后将记录的坑位元素值放入即可。 public static void quickSort(int[] array){//记录左起始位置和右边的结束位置进行递归quick(array,0,array.length-1);}public static void inSert(int[] array,int left,int right){for(int ileft1;iright;i){int tmparray[i];int ji-1;for(;jleft;j--){if(array[j]tmp){array[j1]array[j];}else {break;}}array[j1]tmp;}}private static void quick(int[] array, int left, int right) {if(leftright)return ;//说明两个相遇或者走出范围if(right-left110){inSert(array,left,right);return ;}int index middleNum(array,left,right);System.out.println(index下标值:index);//用来交换left和right范围内元素且最终将首位元素与相遇值交换swap(array,left,index);int pospartitionPointer(array,left,right);//递归quick(array,left,pos-1);quick(array,pos1,right);}private static int partitionPit(int[] array, int left, int right) {int recordarray[left];//记录起始坑位while(leftright){while(leftrightarray[right]record){//右边找到小于tmpright--;}//说明找到小于tmp的值array[left]array[right];while(leftrightarray[left]record){//左边找到大于tmpleft;}//说明找到大于tmp的值array[right]array[left];}//这里left与right相遇后将记录的首个坑填入array[left]record;return left;}3.2.3 前后指针法 cur指向起始位置1pre是cur的前一位 判断条件如果cur找到基准值最初位置key为5前一项的条件满足后prev向后走不为cur为cur则不交换直到prev在前cur在后且cur基准值 cur如果大于基准值直到cur找到小于基准值的数或者走完直到递归调整为升序。 public static void quickSort(int[] array){//记录左起始位置和右边的结束位置进行递归quick(array,0,array.length-1);}public static void inSert(int[] array,int left,int right){for(int ileft1;iright;i){int tmparray[i];int ji-1;for(;jleft;j--){if(array[j]tmp){array[j1]array[j];}else {break;}}array[j1]tmp;}}private static void quick(int[] array, int left, int right) {if(leftright)return ;//说明两个相遇或者走出范围if(right-left110){inSert(array,left,right);return ;}int index middleNum(array,left,right);System.out.println(index下标值:index);//用来交换left和right范围内元素且最终将首位元素与相遇值交换swap(array,left,index);int pospartitionPointer(array,left,right);//递归quick(array,left,pos-1);quick(array,pos1,right);}private static int partitionPointer(int[] array, int left, int right) {//记录cur的前一项int Prevleft;int curleft1;while(curright){//cur与起始位置比较只有小于才能进行交换且prev不为curif(array[cur]array[left]array[Prev]!array[cur]){swap(array,cur,Prev);}cur;}//交换最后记录的cur的值swap(array,left,Prev);return Prev;}3.4 非递归快速排序
这里非递归排序的情况下因为每次最左边的数我们需要申请一个栈来记录其区间值出栈由区间值一步步缩小取值的范围并进行交换重复上述即可。 public static void quickNor(int[] array){quickSortNor(array,0,array.length-1);}private static void quickSortNor(int[] array, int left, int right) {StackInteger stacknew Stack();int pivotpartitionHoare(array,left,right);if(pivotleft1){stack.push(left);stack.push(pivot-1);}if(pivot1right){stack.push(pivot1);stack.push(right);}while(!stack.isEmpty()){right stack.pop();left stack.pop();pivotpartitionHoare(array,left,right);if(pivotleft1){stack.push(left);stack.push(pivot-1);}if(pivot1right){stack.push(pivot1);stack.push(right);}}四.归并排序
4.1 递归归并排序
定义一个分界线mid来获取其中间值递归左边和右边每次进入方法进行排序 将左起始到中间值与中间值到右侧比较创建一个数组来记录排序后放到数组中最后让原数组接收。 public static void mergeSort(int[] array){mergeSortM(array,0,array.length-1);}private static void mergeSortM(int[] array, int left, int right) {//知道left和right相遇返回if(leftright)return ;int mid(leftright)/2;//以中间值作为分区递归左边和右边mergeSortM(array,left,mid);mergeSortM(array,mid1,right);//每次递归传入后进行排序merge(array,left,mid,right);}private static void merge(int[] array, int left, int mid, int right) {int[] tmpArrnew int[right-left1];//创建一个数组接收每一次递归的数组int k0;//记录左边的起始位置与右边起始位置int s1left;int s2mid1;while(s1 mid s2 right){if(array[s1]array[s2]){tmpArr[k]array[s1];}else{tmpArr[k]array[s2];}}while(s1 mid){tmpArr[k]array[s1];}while(s2 right){tmpArr[k]array[s2];}for(int i0;itmpArr.length;i){//这里的left跟随着mid改变当递归右侧时left为mid1array[ileft]tmpArr[i];}}
}时间复杂度O(N*logN) 空间复杂度:O(logN) 稳定排序 4.2非递归归并排序 private static void merge(int[] array, int left, int mid, int right) {int[] tmpArrnew int[right-left1];//创建一个数组接收每一次递归的数组int k0;//记录左边的起始位置与右边起始位置int s1left;int s2mid1;while(s1 mid s2 right){if(array[s1]array[s2]){tmpArr[k]array[s1];}else{tmpArr[k]array[s2];}}while(s1 mid){tmpArr[k]array[s1];}while(s2 right){tmpArr[k]array[s2];}for(int i0;itmpArr.length;i){array[ileft]tmpArr[i];}}public static void mergeNor(int[] array){int gap1;//每组共有几个数据while(gaparray.length){for(int i0;iarray.length;iigap*2){int lefti;int midleftgap-1;int rightmidgap;if(midarray.length)midarray.length-1;if(rightarray.length){rightarray.length-1;}merge(array,left,mid,right);}gap*2;}}五.测试运行时间代码 // 有序public static void order(int[] arr){for(int i0;iarr.length;i){arr[i]i;}}//逆序public static void reverse(int[] arr){for(int i0;iarr.length;i){arr[i] arr.length-i;}}//无序public static void disorder(int[] arr){Random randomnew Random();for(int i0;iarr.length;i){arr[i] random.nextInt(100);}}//测试public static void testSort1(int[] arr){int[] tmpArray Arrays.copyOf(arr,arr.length);long startTimeSystem.currentTimeMillis();//开始结束记录Sort.shellSort(tmpArray);long endTimeSystem.currentTimeMillis();System.out.println(希尔排序时间(endTime-startTime));}public static void testSort2(int[] arr){int[] tmpArray Arrays.copyOf(arr,arr.length);long startTimeSystem.currentTimeMillis();//开始结束记录Sort.inSert(tmpArray);long endTimeSystem.currentTimeMillis();System.out.println(插入排序时间(endTime-startTime));}public static void testSort3(int[] arr){int[] tmpArray Arrays.copyOf(arr,arr.length);long startTimeSystem.currentTimeMillis();//开始结束记录Sort.selectSort2(tmpArray);long endTimeSystem.currentTimeMillis();System.out.println(双向选择排序时间(endTime-startTime));}public static void testSort4(int[] arr){int[] tmpArray Arrays.copyOf(arr,arr.length);long startTimeSystem.currentTimeMillis();//开始结束记录Sort.bubbleSort(tmpArray);long endTimeSystem.currentTimeMillis();System.out.println(冒泡排序时间(endTime-startTime));}public static void testSort5(int[] arr){int[] tmpArray Arrays.copyOf(arr,arr.length);long startTimeSystem.currentTimeMillis();//开始结束记录Sort.heapSort(tmpArray);long endTimeSystem.currentTimeMillis();System.out.println(堆排序时间(endTime-startTime));}public static void testSort6(int[] arr){int[] tmpArray Arrays.copyOf(arr,arr.length);long startTimeSystem.currentTimeMillis();//开始结束记录Sort.quickSort(tmpArray);long endTimeSystem.currentTimeMillis();System.out.println(Hoare快速排序时间(endTime-startTime));}public static void testSort7(int[] arr){int[] tmpArray Arrays.copyOf(arr,arr.length);long startTimeSystem.currentTimeMillis();//开始结束记录Sort.quickSort(tmpArray);long endTimeSystem.currentTimeMillis();System.out.println(挖坑法快速排序时间(endTime-startTime));}public static void testSort8(int[] arr){int[] tmpArray Arrays.copyOf(arr,arr.length);long startTimeSystem.currentTimeMillis();//开始结束记录Sort.quickSort(tmpArray);long endTimeSystem.currentTimeMillis();System.out.println(前后指针法快速排序时间(endTime-startTime));}
