八大排序算法（面试被问到）

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 i=0;i<arr.length;i++){
16	            System.out.print(arr[i]+" ");
17	        }
18	    }
19	
20	    private static void bubblesort(int[] arr) {
21	        int n=arr.length;
22	        for(int i=0;i<n;i++){//控制整个冒泡排序的次数
23	            for(int j=0;j<n-1-i;j++){//控制两两交换的次数
24	                if(arr[j]>arr[j+1]){
25	                    int temp=arr[j];
26	                    arr[j]=arr[j+1];
27	                    arr[j+1]=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 i=0;i<arr.length;i++){
17	            System.out.print(arr[i]+" ");
18	        }
19	    }
20	    public static  void insertsort(int[] arr){
21	        //遍历除第一个数之外的所有数字
22	        for(int i=1;i<arr.length;i++){
23	           //当前数字比前一个数字小
24	            if(arr[i]<arr[i-1]){
25	                //把当前数字保存起来，当前位置腾开
26	                int temp=arr[i];
27	                //当前数字和他之前所有数字进行比较
28	                int j=0;
29	                for(j=i-1;j>=0&&arr[j]>temp;j--){//如果前面的数字大于temp，右移
30	                    arr[j+1]=arr[j];
31	                }
32	                arr[j+1]=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(left<right){
20	            int mid=(left + right)  / 2;
21	            mergesort(arr,left,mid);
22	            mergesort(arr,mid+1,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 i=left;int j=mid+1;int k=0;
30	        int[] temp=new int[right-left+1];
31	       while(i<=mid&&j<=right){
32	           if(arr[i]<arr[j]){
33	               temp[k++]=arr[i++];
34	           }else{
35	               temp[k++]=arr[j++];
36	           }
37	       }
38	       while(i<=mid){
39	           temp[k++]=arr[i++];
40	       }
41	       while(j<=right){
42	           temp[k++]=arr[j++];
43	       }
44	       //按照排好的顺序给arr赋值
45	       for(int t=0;t<temp.length;t++){
46	           arr[t+left]=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 i=0;i<arr.length;i++){
17	            System.out.print(arr[i]+" ");
18	        }
19	    }
20	    public static void insertsort(int[] arr){
21	        int n=arr.length;
22	        for(int k=0;k<n;k++){
23	            int min=k;//设置第一个下标为最小值
24	            for(int i=k+1;i<n;i++){//将其他元素与最小值作比较
25	                if(arr[i]<arr[min]){
26	                    min=i;//更新最小值对应的下标
27	                }
28	            }
29	           int temp=arr[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 i=0;i<arr.length;i++){
21	            System.out.print(arr[i]+" ");
22	        }
23	    }
24	    public static void quicksort(int[] arr,int left,int right){
25	        if(left<right) {
26	            int partitionIndex=partition(arr,left,right);
27	            quicksort(arr,left,partitionIndex-1);
28	            quicksort(arr,partitionIndex+1,right);
29	        }
30	    }
31	    public static int partition(int[] arr,int left,int right) {
32	        int privot=arr[left];
33	while(left<right){
34	    while(left<right&&arr[right]>=privot){
35	        right--;
36	    }
37	    arr[left]=arr[right];
38	    while(left<right&&arr[left]<=privot){
39	        left++;
40	    }
41	    arr[right]=arr[left];
42	        }
43	//在left==right时候，将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*2+2
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 n=arr.length;
28	        //建堆
29	        buildMaxHeap(arr,n);
30	        for(int i=n-1;i>0;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 father=x;
41	        int left=2*x+1;
42	        int right=2*x+2;
43	        if(left<n&&arr[left]>arr[father]){
44	           father=left;
45	        }
46	        if(right<n&&arr[right]>arr[father]){
47	            father=right;
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 temp=arr[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 i=n/2-1;i>=0;i--){
65	            heapify(arr,i,n);
66	        }
67	    }
68	}

优点：

速度快——时间复杂度为O(nlogn)，这意味着无论数据规模多大，堆排序都能在多项式时间内完成。排序空间复杂度O(1)，这意味着它不需要额外的存储空间来保存数据，这使得堆排序在空间效率方面表现优异；

稳定——堆排序是一种稳定的排序算法，堆排序适用于多种场景，包括在数据频繁变动的情况下，因为它可以在不重建整个堆的情况下更新堆顶元素。

缺点：

堆维护问题——需要频繁地重建和维护堆，这可能会在数据频繁变动的情况下导致效率降低，因为每次数据更新都可能需要调整堆的结构，这增加了额外的计算负担。

（7）希尔排序

希尔排序是一种改进后的插入排序算法，也被称为缩小增量排序。

过程：

①选择一个小于数组长度的增量(gap)，最开始gap=n/2，然后将数组分为多个子序列，每个子序列的元素间隔为这个增量值，对每个子序列分别进行直接插入排序。
②逐渐减小增量值（减半），再次进行子序列的划分和排序。

③直到增量减至1，此时整个数组被当作一个序列进行插入排序。

代码实现：

public class ShellSort {
11	    public static void main(String[] args) {
12	int[] arr=new 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 i=0;i<arr.length;i++){
17	            System.out.print(arr[i]+" ");
18	        }
19	    }
20	
21	    private static void shellsort(int[] arr) {//时间复杂度n^1.3
22	int n=arr.length;
23	//初始化间隔为数组长度的一半
24	int gap=n/2;
25	while(gap>0){
26	    //对每个间隔进行直接插入排序
27	    for(int i=gap;i<n;i++){
28	        int temp=arr[i];
29	        int j=0;
30	        //对间隔为 gap 的元素进行插入排序
31	        for(j=i;j>=gap&&temp<arr[j-gap];j=j-gap){
32	            arr[j]=arr[j-gap];
33	        }
34	        arr[j]=temp;
35	    }
36	    // 缩小间隔
37	    gap=gap/2;
38	}
39	    }
40	}

优点：

速度快——由于开始时增量的取值较大，每个子序列中的元素较少，所以排序速度快；随着增量逐渐减小，虽然子序列中的元素个数增多，但是由于前面工作的基础，大多数元素已经基本有序，因此排序速度仍然较快。希尔排序的时间复杂度为O(n^1.3)至O(n^2)。

缺点：

不稳定——取决于增量序列的选择，它是一种非稳定排序算法，这意味着在排序过程中，相同的元素可能会移动位置，导致最终顺序与原始顺序不同。