宁波网站优化公司价格,wordpress手机端滑动侧栏,邮箱或企业邮箱,seo排名培训学校数据结构中的八大排序算法是计算机科学领域经典的排序方法#xff0c;它们各自具有不同的特点和适用场景。以下是这八大排序算法的详细介绍#xff1a;
五、选择排序#xff08;Selection Sort#xff09;
核心思想#xff1a;每一轮从未排序的元素中选择最小#xff0… 数据结构中的八大排序算法是计算机科学领域经典的排序方法它们各自具有不同的特点和适用场景。以下是这八大排序算法的详细介绍
五、选择排序Selection Sort
核心思想每一轮从未排序的元素中选择最小或最大的元素放到已排序的序列末尾。时间复杂度O(n^2)因为每一轮都需要遍历整个未排序的数组。空间复杂度O(1)。稳定性不稳定因为选择最小或最大元素时可能会破坏相同元素的相对位置。 package 排序;import java.util.Arrays;public class Selection{//选择排序public static void main(String[] args) {int[] arr {15,27,34,62,30,16};sort(arr);System.out.println(Arrays.toString(arr));}public static void sort(int[] arr) {for(int j0;jarr.length;j) {int minarr[j];int minIndexj;for(int ij;iarr.length;i) {if(arr[i]min) {minarr[i];minIndexi;}}arr[minIndex]arr[j];arr[j]min;} }
}
六、堆排序Heap Sort
核心思想利用堆这种数据结构进行排序。首先构建一个大顶堆或小顶堆然后依次将堆顶元素最大或最小与堆底元素交换并减少堆的大小。最后对剩余的元素重新调整成堆直到整个数组有序。时间复杂度O(nlogn)因为构建堆和调整堆的时间复杂度都是O(logn)而需要构建和调整n次。空间复杂度O(1)因为排序过程中只需要常量的额外空间用于交换元素。稳定性不稳定因为堆的调整过程中可能会破坏相同元素的相对位置。
package 排序;import java.util.Arrays;public class Heap{
//堆排序public static void main(String[] args) {int[] arr {5,7,4,2,0,1,6};//一、构建大顶堆for (int parr.length-1;p0;p--) {sort(arr, p, arr.length);}//二、堆底堆顶元素进行交换for(int iarr.length-1;i0;i--) {int temparr[i];arr[i]arr[0];arr[0]temp;sort(arr, 0, i);}//打印System.out.println(堆排序的结果为);System.out.println(Arrays.toString(arr));}//堆的维护public static void sort(int[] arr,int parent,int length) {//定义左孩子int child2*parent1;while(childlength) {//定义右孩子int rchildchild1;if(rchildlength arr[rchild]arr[child]) {child;}//child指向左右孩子中的最大值//父子节点进行比较if(arr[parent]arr[child]) {//父子节点进行交换int temparr[parent];arr[parent]arr[child];arr[child]temp;//parent指向child,child继续指向左右孩子中的最大值parentchild;child2*child1;}else {break;}}}
}
七、归并排序Merge Sort
核心思想将数组分成两部分分别进行排序然后将两部分合并成一个有序数组。这个过程可以递归地进行。时间复杂度O(nlogn)因为每次合并都需要遍历两个有序数组。空间复杂度O(n)因为需要额外的空间来存储合并后的有序数组虽然可以使用原地归并算法来减少空间复杂度但实现起来较为复杂。稳定性稳定因为合并过程中相同元素会保持相对位置不变。
package 排序;import java.util.Arrays;public class Merge{public static void main(String[] args) {int[] arr {11,22,33,55,2,11,24,63};mergeSort(arr,0,arr.length-1);System.out.println(Arrays.toString(arr));}//拆分public static void mergeSort(int[] arr, int left, int right) {//递归出口if(leftright) {return;}int mid(leftright)/2;//向左拆分mergeSort(arr,left,mid);//向右拆分mergeSort(arr,mid1,right);//合并merge(arr,left,right,mid);}public static void merge(int[] arr,int left,int right,int mid) {//定义第一段和第二段的开始int s1left;int s2mid1;//定义临时空间int[] temp new int[right-left1];int index0;//定义游标遍历临时空间//判断s1和s2指向的数据大小将其存入临时数组while(s1mids2right) {if(arr[s1]arr[s2]) {temp[index]arr[s1];s1;index;}else {temp[index]arr[s2];s2;index;}}//判断s1中是否有数据如果有将其放入临时数组当中while(s1mid) {temp[index]arr[s1];s1;index;}//判断s2中是否有数据如果有将其放入临时数组当中while(s2right) {temp[index]arr[s2];s2;index;}//将临时数组中的数据写回原数组for(int i0;itemp.length;i) {arr[lefti] temp[i];}}
}
八、基数排序Radix Sort
核心思想基数排序是一种非比较型排序算法它根据元素的位数或字符进行排序。通常从最低有效位或字符开始依次对每一位或字符进行计数排序或桶排序直到最高有效位或字符为止。时间复杂度O(d(nr))其中d是位数或字符数n是待排序元素的个数r是基数如对于十进制数r10。空间复杂度O(nr)因为需要额外的空间来存储桶或计数数组。稳定性稳定因为每一位或字符的排序过程中都保持相同元素的相对位置不变。
package 排序;import java.util.Arrays;public class Radix{//基数排序注意基数排序只能排整数。适用于数据位数不多但数据量大的数据集public static void main(String[] args) {int[] arr {50,17,41,20,101,11,26,35,47,63,214,63,88};sort(arr);System.out.println(Arrays.toString(arr));}public static void sort(int[] arr) {//取最大值计算最大值的位数int maxarr[0];for(int j0;jarr.length;j) {if(arr[j]max) {maxarr[j];}}int maxLen(max).length();//返回最大值的位数System.out.println(最大值的位数为maxLen);//定义桶本质上定义二维数组int[][] bucketnew int[10][arr.length];//定义桶记录工具一维数组长度为10int[] elementCountsnew int[10];int n1;//放入取出来来回回执行maxLen遍for(int m0;mmaxLen;m) {//遍历数组将数组中的数据放入桶中for(int i0;iarr.length;i) {//个位开始排序int element arr[i]/n%10; //element代表个位数值也代表要被放在哪个桶//读取桶记录工具中的数值int countelementCounts[element];//数据放入bucket[element][count]arr[i];elementCounts[element];}//将桶中的数据取出int index0;//定义index游标遍历数组将桶中数据存入数组里for(int k0;kelementCounts.length;k) {if(elementCounts[k]!0) {//不为0桶中有数据将数据取出for(int l0;lelementCounts[k];l) {arr[index]bucket[k][l];index;}}//清理桶记录elementCounts[k]0;}nn*10;}} }
综上所述这八大排序算法各有优缺点和适用场景。在实际应用中需要根据待排序数据的特点和具体需求来选择合适的排序算法。
