本文主要是介绍八大排序算法（面试被问到），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
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)。
缺点：
不稳定——取决于增量序列的选择，它是一种非稳定排序算法，这意味着在排序过程中，相同的元素可能会移动位置，导致最终顺序与原始顺序不同。
这篇关于八大排序算法（面试被问到）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
