为什么做可信网站,视频拍摄培训,白石龙做网站,大连港健康打卡二维码1.八大排序算法都是什么#xff1f;
八大排序算法有#xff1a;插入排序、冒泡排序、归并排序、选择排序、快速排序、希尔排序、堆排序、基数排序#xff08;通常不提#xff09;。此外#xff0c;还可以直接调用Arrays.sort()进行排序。
2.八大排序算法时间复杂度和稳定…1.八大排序算法都是什么
八大排序算法有插入排序、冒泡排序、归并排序、选择排序、快速排序、希尔排序、堆排序、基数排序通常不提。此外还可以直接调用Arrays.sort()进行排序。
2.八大排序算法时间复杂度和稳定性
这里有一个口诀记法
插插入帽冒泡龟归并他很稳稳定
插冒归喜欢选选择插插入帽冒泡插完他就方了O(n^2)
快快速归归并队堆n老O(logn)
基基数你太稳稳定
3.算法讲解 (1) 冒泡排序
过程
①从数列的开头开始在这趟遍历中对没有进行比较的一对两两比较直到数列的结尾
②如果第一个元素比第二个元素大则交换它们的位置这样较大的元素就逐渐“浮”到数列的末尾
③然后算法再次从数列的开始执行相同的操作但是排好序的元素即最大的元素不再参与比较这个过程一直持续到整个数列都排好序为止。
代码实现
public class BubbleSort {
11 public static void main(String[] args) {
12 int[] arr{5,4,2,1};
13 bubblesort(arr);
14 System.out.println(Sorted array: Arrays.toString(arr));
15 for(int i0;iarr.length;i){
16 System.out.print(arr[i] );
17 }
18 }
19
20 private static void bubblesort(int[] arr) {
21 int narr.length;
22 for(int i0;in;i){//控制整个冒泡排序的次数
23 for(int j0;jn-1-i;j){//控制两两交换的次数
24 if(arr[j]arr[j1]){
25 int temparr[j];
26 arr[j]arr[j1];
27 arr[j1]temp;
28 }
29 }
30 }
31 }
34 } 优点
稳定性——在排序过程中相同元素的相对顺序保持不变。
缺点
不适合大规模数据——对于大规模乱序序列的排序效率较低时间复杂度较高。
2插入排序
过程 ①将第一个元素视为已排序序列。
②从第二个元素开始将其与已排序序列中的元素逐个比较并插入到正确的位置上。这个过程不断重复直到整个数组变得有序。
③在实现上插入排序使用双层循环外层循环遍历数组中的每个元素内层循环则在已排序的部分中查找新元素应插入的位置。
代码实现
public class InsertSort {
11 public static void main(String[] args) {
12 int[] arr{23,46,87,11,24,1};
13 System.out.println(Original array: Arrays.toString(arr));
14 insertsort(arr);
15 System.out.println(Sorted array:Arrays.toString(arr));
16 for(int i0;iarr.length;i){
17 System.out.print(arr[i] );
18 }
19 }
20 public static void insertsort(int[] arr){
21 //遍历除第一个数之外的所有数字
22 for(int i1;iarr.length;i){
23 //当前数字比前一个数字小
24 if(arr[i]arr[i-1]){
25 //把当前数字保存起来当前位置腾开
26 int temparr[i];
27 //当前数字和他之前所有数字进行比较
28 int j0;
29 for(ji-1;j0arr[j]temp;j--){//如果前面的数字大于temp右移
30 arr[j1]arr[j];
31 }
32 arr[j1]temp;//如果前面的数字小于等于temp将temp放入
33 }
34 }
35 }
36
37 } 优点
稳定性——在排序过程中相同元素的相对顺序保持不变。
缺点
不适合大规模数据——对于大规模乱序序列的排序效率较低时间复杂度较高。
3归并排序
过程
①分解Divide将数组递归地分成两半直到数组被分解为单个元素。 ②解决Conquer对每一对分解后的子数组进行排序这一过程通常通过归并排序递归地完成。 ③合并Merge将已排序的子数组合并成一个完整的、有序的数组。
代码实现
public class MergeSort {
11 public static void main(String[] args) {
12 int[] arr{12,11,13,43,5,9};
13 System.out.println(Original Array: Arrays.toString(arr));
14 mergesort(arr,0,arr.length-1);
15 System.out.println(Sorted Array:Arrays.toString(arr));
16 }
17
18 private static void mergesort(int[] arr,int left,int right) {
19 if(leftright){
20 int mid(left right) / 2;
21 mergesort(arr,left,mid);
22 mergesort(arr,mid1,right);
23 Merge(arr,left,mid,right);
24 }
25
26 }
27
28 private static void Merge(int[] arr, int left, int mid, int right) {
29 int ileft;int jmid1;int k0;
30 int[] tempnew int[right-left1];
31 while(imidjright){
32 if(arr[i]arr[j]){
33 temp[k]arr[i];
34 }else{
35 temp[k]arr[j];
36 }
37 }
38 while(imid){
39 temp[k]arr[i];
40 }
41 while(jright){
42 temp[k]arr[j];
43 }
44 //按照排好的顺序给arr赋值
45 for(int t0;ttemp.length;t){
46 arr[tleft]temp[t];
47 }
48 }
49 }
优点
稳定性——在排序过程中相同元素的相对顺序保持不变。
缺点
内存占用大——在划分和合并过程中需要额外的内存来存储列表的两半和最终排序的列表
4选择排序
过程
①从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置
②再从剩余的未排序元素中继续寻找最小或最大元素然后放到已排序序列的末尾
③重复操作直到所有元素均排序完毕。
代码实现
public class SelectSort {
11 public static void main(String[] args) {
12 int[] arr{12,45,72,32,10};
13 System.out.println(Original Array: Arrays.toString(arr));
14 insertsort(arr);
15 System.out.println(Sorted Array:Arrays.toString(arr));
16 for(int i0;iarr.length;i){
17 System.out.print(arr[i] );
18 }
19 }
20 public static void insertsort(int[] arr){
21 int narr.length;
22 for(int k0;kn;k){
23 int mink;//设置第一个下标为最小值
24 for(int ik1;in;i){//将其他元素与最小值作比较
25 if(arr[i]arr[min]){
26 mini;//更新最小值对应的下标
27 }
28 }
29 int temparr[k];//交换将最小值标记到最前面之后k寻找第二个最小值循环
30 arr[k]arr[min];
31 arr[min]temp;
32 }
33 }
35 }
优点
可读性高——简单易懂、易于实现以及它是原地排序算法不占用额外的内存空间。
缺点
时间复杂度较高——无论数据是否有序都需要进行O(n²)次比较处理大规模数据集时效率较低。
不稳定——这意味着在排序过程中相等元素的相对位置可能发生变化导致相同元素的相对顺序不同。
5快速排序
过程
①选择基准元素从待排序序列中选取一个元素作为基准pivot。 ②分区操作通过比较其他元素与基准元素的大小将序列分为两部分。所有比基准元素小的元素放在其左边所有比基准元素大的元素放在其右边。 ③递归排序对基准元素左右两边的子序列递归执行上述步骤直到子序列的长度为0或1此时子序列已经有序。
代码实现
public class QuickSort {
11 //快速排序
12 //首先在序列中随机选择一个基准值privot)
13 //除了基准值以外的数分为“比基准值小的数”、“比基准值大的数”再将其排列成以下形式 【比基准值小的数】 基准值 【比基准值大的数】
14 //对【】中的数据进行递归同样使用快速排序
15 public static void main(String[] args) {
16 int[] arr{12,45,67,81,1,2};
17 System.out.println(Original array: Arrays.toString(arr));
18 quicksort(arr,0,arr.length-1);
19 System.out.println(Sorted array:Arrays.toString(arr));
20 for(int i0;iarr.length;i){
21 System.out.print(arr[i] );
22 }
23 }
24 public static void quicksort(int[] arr,int left,int right){
25 if(leftright) {
26 int partitionIndexpartition(arr,left,right);
27 quicksort(arr,left,partitionIndex-1);
28 quicksort(arr,partitionIndex1,right);
29 }
30 }
31 public static int partition(int[] arr,int left,int right) {
32 int privotarr[left];
33 while(leftright){
34 while(leftrightarr[right]privot){
35 right--;
36 }
37 arr[left]arr[right];
38 while(leftrightarr[left]privot){
39 left;
40 }
41 arr[right]arr[left];
42 }
43 //在leftright时候将privot放进去此时privot左边都是比privot小的privot右边都是比privot大的
44 arr[left]privot;
45 return left;
46 }
47 }
优点
高效率——快速排序的平均时间复杂度为O(NlogN)使其在处理大量数据时表现出色。
数据移动少——在排序过程中快速排序需要移动的数据量相对较小。
缺点
不稳定——当处理大量重复元素时可能会导致递归深度过大甚至栈溢出。 6堆排序
过程
①最大堆调整Max Heapify将堆的末端子节点作调整使得子节点永远小于父节点 ②创建最大堆Build Max Heap将堆中的所有数据重新排序按照最大堆调整 ③堆排序HeapSort移除位在第一个数据的根节点最大堆顺序就会被打乱并重复做最大堆调整的递归运算。
代码实现
public class HeapSort {
11 //大顶堆
12 // 孩子节点下标为i时父节点下标i-1/2
13 //父亲节点下标为k时左孩子下标(k*2)1;右孩子下标k*22
14 public static void main(String[] args) {
15 //测试用例
16 int[] arr{12,45,72,32,10};
17 System.out.println(Original Array: Arrays.toString(arr));
18 heapsort(arr);
19 System.out.println(Sorted Array:Arrays.toString(arr));
20 for(int k:arr){
21 System.out.print(k );
22 }
23 }
24
25 //堆排序函数
26 private static void heapsort(int[] arr) {
27 int narr.length;
28 //建堆
29 buildMaxHeap(arr,n);
30 for(int in-1;i0;i--){
31 //交换
32 swap(arr,0,i);
33 //维护最大堆的性质
34 heapify(arr,0,i);
35 }
36 //
37 }
38
39 private static void heapify(int[] arr, int x, int n) {
40 int fatherx;
41 int left2*x1;
42 int right2*x2;
43 if(leftnarr[left]arr[father]){
44 fatherleft;
45 }
46 if(rightnarr[right]arr[father]){
47 fatherright;
48 }
49 if(father!x){
50 swap(arr,x,father);
51 heapify(arr,father,n);//向下调整维护大堆性质
52 }
53
54 }
55
56 private static void swap(int[] arr, int a, int b) {
57 int temparr[a];
58 arr[a]arr[b];
59 arr[b]temp;
60 }
61
62 private static void buildMaxHeap(int[] arr, int n) {
63 //寻找最后一个非叶子节点
64 for(int in/2-1;i0;i--){
65 heapify(arr,i,n);
66 }
67 }
68 }
优点
速度快——时间复杂度为O(nlogn)这意味着无论数据规模多大堆排序都能在多项式时间内完成。排序空间复杂度O(1)这意味着它不需要额外的存储空间来保存数据这使得堆排序在空间效率方面表现优异
稳定——堆排序是一种稳定的排序算法堆排序适用于多种场景包括在数据频繁变动的情况下因为它可以在不重建整个堆的情况下更新堆顶元素。 缺点
堆维护问题——需要频繁地重建和维护堆这可能会在数据频繁变动的情况下导致效率降低因为每次数据更新都可能需要调整堆的结构这增加了额外的计算负担。
7希尔排序
希尔排序是一种改进后的插入排序算法也被称为缩小增量排序。
过程
①选择一个小于数组长度的增量(gap)最开始gapn/2然后将数组分为多个子序列每个子序列的元素间隔为这个增量值对每个子序列分别进行直接插入排序。 ②逐渐减小增量值减半再次进行子序列的划分和排序。
③直到增量减至1此时整个数组被当作一个序列进行插入排序。
代码实现
public class ShellSort {
11 public static void main(String[] args) {
12 int[] arrnew int[]{12,23,11,5,65,88};
13 System.out.println(Original Array: Arrays.toString(arr));
14 shellsort(arr);
15 System.out.println(Sorted Array:Arrays.toString(arr));
16 for(int i0;iarr.length;i){
17 System.out.print(arr[i] );
18 }
19 }
20
21 private static void shellsort(int[] arr) {//时间复杂度n^1.3
22 int narr.length;
23 //初始化间隔为数组长度的一半
24 int gapn/2;
25 while(gap0){
26 //对每个间隔进行直接插入排序
27 for(int igap;in;i){
28 int temparr[i];
29 int j0;
30 //对间隔为 gap 的元素进行插入排序
31 for(ji;jgaptemparr[j-gap];jj-gap){
32 arr[j]arr[j-gap];
33 }
34 arr[j]temp;
35 }
36 // 缩小间隔
37 gapgap/2;
38 }
39 }
40 }
优点
速度快——由于开始时增量的取值较大每个子序列中的元素较少所以排序速度快随着增量逐渐减小虽然子序列中的元素个数增多但是由于前面工作的基础大多数元素已经基本有序因此排序速度仍然较快。希尔排序的时间复杂度为O(n^1.3)至O(n^2)。
缺点
不稳定——取决于增量序列的选择它是一种非稳定排序算法这意味着在排序过程中相同的元素可能会移动位置导致最终顺序与原始顺序不同。
