【数据结构】七种常见排序算法

🥰🥰🥰来都来了，不妨点个关注叭！
👉博客主页：欢迎各位大佬!👈

欢迎来到排序算法的学习，恭喜你！本期内容主要介绍排序算法，一起来探索吧~
（ps：真的一直都想写有关排序的文章，奈何每天尊嘟好忙，终于开写啦！）

1. 排序的基本概念

1.1 排序预备知识

排序：排序的目的是使一串记录，将一组“无序”的记录序列调整为"有序"的记录序列，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

1.2 内部排序与外部排序

内部排序：数据元素全部放在内存中的排序，内部排序的过程是一个逐步扩大记录的有序序列长度的过程。
外部排序：数据元素数量非常大，不能同时放在内存中，整个过程不可能在内存中完成。

1.3 排序的稳定性

稳定性：假定在待排序的记录序列中，存在两个或者两个以上的具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，则称为稳定，否则为不稳定

1.4 排序的分类

插入类排序：将待排序的值插入到前面已经有序的序列中
选择类排序：每次排序选出序列的最大值/最小值，放到序列的最后面
交换排序：两两比较待排序的序列，并交换不满足序列的那对数

以上为经典排序，本文主要介绍常见的 7 种排序算法，我们需要掌握~ 一起来正式进入下面的学习吧！

2. 插入类排序

2.1 直接插入排序

【基本思想】 将记录的值，插入到已经排序好的有序序列中，直到所有记录的值全部插入，则该过程完成。

【基本思路】 仅有一个数据时，则认为该数据为已经排好序的，则我们可以这样思考：

1. 第1个元素已排好序，从第2个元素开始，下标为i，取出该元素放在变量 tmp 中，从已排好序序列中从后往前使用 j 遍历比较
2. 如果下标 j 的值大于 tmp，则 j+1 的值替换为 j 下标的值，继续遍历
3. 如果下标 j 的值小于 tmp，则 break，跳出遍历
4. 最后 j+1 的值替换成临时变量 tmp 存储的值
5. 此时前两个元素已经是有序的了，再用 i 继续遍历(详细解释可以看示意图~)

有没有点像打扑克牌时候呢？拿到一张牌就在以往排好序的牌中插入~

【示意图】

【具体代码】

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: wlx
 * Date: 2025-06-01
 * Time: 23:58
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] array = {1,4,2,9,6,7};
        insertSort(array);
		System.out.println(Arrays.toString(array));
    }
    
    public static void insertSort(int[] array) {
        for(int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j = i-1;
            for(; j >= 0; j--) {
                if(array[j] > tmp) {
                    array[j+1] = array[j];
                }else {
                    //array[j+1] = tmp;
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }
}

【特性总结】

1. 时间复杂度：O(n²)，当数据本身就有序的时候，时间复杂度为O(n)
2. 空间复杂度：O(1)
3. 稳定性：稳定
4. 适用场景：当数据基本趋于有序时，建议使用直接插入排序

2.2 希尔排序

【基本思想】希尔排序又称为缩小增量法，其基本思想是先选定一个整数 gap，将待排序的数据分为多个组，每组距离 gap，对每一组进行排序，每一组两个元素，接着 gap/2 ，缩小每组的距离，当 gap = 1 时，所有数据就排好序了
简单理解就是按照 gap 分组，组内进行插入排序，当 gap = 1 时，则为直接插入排序

【基本思路】与直接插入排序思路一致，希尔排序是直接插入排序的优化，先用 gap 分组，让数组预有序，当 gap 为 1 时，数组也基本有序了，此时就是直接插入排序~

【示意图】

【具体代码】

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: wlx
 * Date: 2025-06-02
 * Time: 10:28
 */
public class ShellSort {
    public static void main(String[] args) {
        int[] array = {1,4,2,9,6,7};
        int gap = array.length;
        while(gap > 1) {
            shellSort(array,gap);
            gap /= 2;
        }
        shellSort(array,1);
		System.out.println(Arrays.toString(array));
    }

    public static void shellSort(int[] array,int gap) {
        for(int i = gap; i < array.length; i++) {
            int tmp = array[i];
            int j = i-gap;
            for(; j >= 0; j-=gap) {
                if(array[j] > tmp) {
                    array[j+gap] = array[j];
                }else {
                    //array[j+1] = tmp;
                    break;
                }
            }
            array[j+gap] = tmp;
        }
    }

【特性总结】

1. 时间复杂度：O(n^1.3) - O(n^1.5) ，当数据本身就有序的时候，时间复杂度为O(n)，且希尔排序的时间复杂度取决于增量值 gap 的选取，即时间复杂度并不是一个定值
2. 空间复杂度：O(1)
3. 稳定性：不稳定
4. 希尔排序是直接插入排序的优化，gap >1 的排序是预排序，使数据趋于有序，gap=1 时则是直接插入排序

3. 选择类排序

3.1 直接选择排序

【基本思想】每次从待排序的序列中选出最小/最大元素，放在序列的起始位置，直到全部待排序的数据排完

【基本思路】定义一个 minIndex 下标用来存储最小值的下标，第1次 minIndex = 0 下标，遍历整个待排序序列，当有更小数据时，更新 minIndex 下标，再交换起始位置 i 与 minIndex 下标值，这样就找到第1小的元素，接着再遍历，minIndex = 1，遍历后面的待排序元素，找到第2小数据，并进行交换，以此类推…

【示意图】

【具体代码】

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: wlx
 * Date: 2025-06-02
 * Time: 10:53
 */
public class SelectSort {

    public static void main(String[] args) {
        int[] array = {1,4,2,9,6,7};
        selectSort(array);
		System.out.println(Arrays.toString(array));
    }

    public static void selectSort(int[] array) {
        for(int i = 0; i < array.length; i++) {
            int minIndex = i;
            for(int j = i+1; j < array.length; j++) {
                if(array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            swap(array,i,minIndex);
        }
    }

    public static void swap(int[] array,int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
}

【特性总结】

1. 时间复杂度：O(n²)
2. 空间复杂度：O(1)
3. 稳定性：不稳定

3.2 堆排序

【基本思想】堆排序是指利用堆这种数据结构所设计的一种算法，它是选择排序的一种，通过堆进行选择数据，排升序是建大堆，排降序建立小堆

大根堆：每个节点的值都 >= 其子节点的值，用于升序排列
小根堆：每个节点的值都 <= 其子节点的值，用于降序排列

【基本思路】堆排序就是先将我们的数组进行一次建堆，循环交换堆顶元素（最大值）与最后一个元素，即交换数组头和尾的元素，然后重新建堆，再进行交换堆顶元素与最后一个元素

【示意图】

【具体代码】

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: wlx
 * Date: 2025-06-22
 * Time: 23:52
 */
public class HeapSort {
    public static void heapSort(int[] array) {
        createBigHeap(array);
        int end = array.length - 1;
        while (end > 0) {
            swap(array, 0, end);
            shiftDown(array, 0, end);
            end--;
        }

    }

    public static void createBigHeap(int[] array) {
        for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {
            shiftDown(array, parent, array.length);
        }
    }

    //建大堆
    private static void shiftDown(int[] array, int parent, int len) {
        int child = 2 * parent + 1;
        while (child < len) {
            if (child + 1 < len && array[child] < array[child + 1]) {
                child++;
            }
            if (array[child] > array[parent]) {
                swap(array, child, parent);
                parent = child;
                child = 2 * parent + 1;
            } else {
                break;
            }
        }
    }

    public static void swap(int[] arr,int i,int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) {
        int[] array = {1,4,2,9,6,7};
        heapSort(array);
        System.out.println(Arrays.toString(array));
    }
}

【特性总结】

1. 时间复杂度：O(N*logN)
2. 空间复杂度：O(1)
3. 稳定性：不稳定

4. 交换类排序

4.1 冒泡排序

【基本思想】将待排序的数据两两进行比较，按比较结果来交换序列位置，将值大/值小的数据放到序列的尾部，将值小/值大的数据放到序列的首部位置，依次比较放置，最后得到有序序列

【基本思路】冒泡排序的每一次循环比较就是找出最大值(最小值)，将最大值(最小值)放在数组尾部(首部)，经过n次比较后，数据变成有序的，这里 flag 变量是优化作用，如果一轮下来没交换，则数组已经有序~

【示意图】

【具体代码】

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: wlx
 * Date: 2025-06-03
 * Time: 23:00
 */
public class BubbleSort {

    public static void main(String[] args) {
        int[] array = {1,4,2,9,6,7};
        bubbleSort(array);
        for(int i = 0; i < array.length; i++) {
            System.out.print(array[i]+" ");
        }
    }

    private static void bubbleSort(int[] array) {
        for(int i = 0; i < array.length-1; i++) {
            boolean flag = false;
            for(int j = 0; j < array.length-1-i;j++) {
                if(array[j+1] < array[j]) {
                    swap(array,j,j+1);
                    flag = true;
                }
            }
            if(flag == false) {
                break;
            }
        }
    }


    public static void swap(int[] array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
}

【特性总结】

1. 时间复杂度：O(N^2)
2. 空间复杂度：O(1)
3. 稳定性：稳定

4.2 快速排序

【基本思想】先从数组中取一个数作为基准数，进行分区，将比这个大的数全放到它的右边，小于或等于它的数全部放到它的左边，直到所有元素在它的位置上，此时就有序了~

【主体框架】

这是快速排序的主框架，我们可以看到这和二叉树的前序遍历递归实现的方式很类似，因此，我们在写快速排序的时候，可以联想到二叉树的前序遍历是如何写的，接下来，介绍快速排序的几种方式：

public class quickSort {
    public void quickSort(int[] num) {
        int left = 0;
        int right = num.length-1;
        quick(num,left,right);
    }

    private void quick(int[] num, int left, int right) {
        if(left >= right) {
            return;
        }
        
        // 按照基准值对数组的[left,right]划分
        int pivot = partition(num,left,right);
        
        // 划分区间：[left,pivot-1] [pivot,right]
        // 递归排序[left,pivot-1]
        quick(num,left,pivot-1);
        // 递归排序[pivot,right]
        quick(num,pivot+1,right);
    }

    private int partition(int[] num, int left, int right) {
        // 根据一定的规则返回基准值
        return -1;
    }
}

4.2.1 三种实现方式

4.2.1.1 hoare 法

【基本思路】

hoare法就是定义两个标志位，right 从右往左找到比基准值小的值停下，left 从左往右找到比基准值大的值停下，交换 left 和 right 位置的值，循环继续，直到 left 和 right 相遇，最后再交换基准值和相遇处的值，再对左右子序列重复此过程，直到数据变成有序

1）先取最左侧即第一个元素为基准值
2）两个指针 left 和 right，left 从最左侧向右走，找到比基准大的元素停下，right 从最右侧向左走，找到比基准小的元素停下，交换 left 下标的值和 right 下标的值
3）当 left >= right 两个指针不再移动，此时 left = right 的下标即为基准值对应的下标，交换基准值初始下标和left(right)下标

【示意图】

【具体代码】

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: wlx
 * Date: 2025-06-22
 * Time: 0:05
 */
public class quickSort {
    public static void quickSort(int[] num) {
        int left = 0;
        int right = num.length-1;
        quick(num,left,right);
    }

    public static void quick(int[] num, int left, int right) {
        if(left >= right) {
            return;
        }
        int pivot = partition(num,left,right);
        quick(num,left,pivot-1);
        quick(num,pivot+1,right);
    }
    // 1.hoare法
    public static int partition(int[] num, int left, int right) {
        // 根据一定的规则返回基准值
        int i = left+1;
        int j = right;
        int tmp = num[left];
        while(true) {
            while(i <= j && num[i] < tmp) {
                i++;
            }
            while(i <= j && num[j] > tmp) {
                j--;
            }
            if(i >= j) {
                break;
            }
            swap(num,i,j);
        }
        swap(num,left,j);
        return left;
    }


    public static void swap(int[] num,int i,int j) {
        int tmp = num[i];
        num[i]  = num[j];
        num[j] = tmp;
    }

    public static void main(String[] args) {
        int[] array = {1,4,2,9,6,7};
        quickSort(array);
        System.out.println(Arrays.toString(array));
    }
}

4.2.1.2 挖坑法

【基本思路】

1）先取最左侧即第一个元素为基准值
2）两个指针 left 和 right，left 从最左侧向右走，找到比基准大的元素停下，将 right 下标处的值赋值给 left 下标的值，right 从最右侧向左走，找到比基准小的元素停下，将 left 下标处的值赋值给 right 下标的值，如此循环
3）当 left >= right 两个指针不再移动，此时 left = right 的下标即为基准值对应的下标，交换基准值初始下标和left(right)下标

【示意图】

【具体代码】

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: wlx
 * Date: 2025-06-22
 * Time: 0:10
 */
public class quickSort {
    public static void quickSort(int[] num) {
        int left = 0;
        int right = num.length-1;
        quick(num,left,right);
    }

    public static void quick(int[] num, int left, int right) {
        if(left >= right) {
            return;
        }
        int pivot = partition(num,left,right);
        quick(num,left,pivot-1);
        quick(num,pivot+1,right);
    }
    // 2.挖坑法
    public static int partition(int[] arr,int left,int right) {
        int tmp = arr[left];
        
        while(left < right) {
            // 找到比基准tmp小的
            while(left < right && arr[right] >= tmp) {
                right--;
            }
            arr[left] = arr[right];
            // 找到比基准tmp大的
            while(left < right && arr[left] <= tmp) {
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] = tmp;
        return left;
    }


    public static void main(String[] args) {
        int[] array = {1,4,2,9,6,7};
        quickSort(array);
        System.out.println(Arrays.toString(array));
    }
}

4.2.1.3 前后指针法

【基本思路】

1）先取最左侧即第一个元素为基准值
2）前后指针 prev 和 cur，prev初始为left，cur初始为right，如果 cur 下标值小于基准值并且前指针prev++后的值与cur下标值不相等，前后指针至少一个间隔，并且值不相等，则交换前后指针的值
3）最后cur走到right，循环结束，交换prev和left值，此时prev就是基准值的位置

【示意图】

【具体代码】

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: wlx
 * Date: 2025-06-22
 * Time: 0:30
 */
public class quickSort {
    public static void quickSort(int[] num) {
        int left = 0;
        int right = num.length-1;
        quick(num,left,right);
    }

    public static void quick(int[] num, int left, int right) {
        if(left >= right) {
            return;
        }
        int pivot = partition(num,left,right);
        quick(num,left,pivot-1);
        quick(num,pivot+1,right);
    }


    //3.前后指针法
    private static int partition(int[] array,int left,int right) {
        int prev = left ;
        int cur = left+1;
        while (cur <= right) {
            if(array[cur] < array[left] && array[++prev] != array[cur]) {
                swap(array,cur,prev);
            }
            cur++;
        }
        swap(array,prev,left);
        return prev;
    }


    public static void swap(int[] arr,int i,int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) {
        int[] array = {1,4,2,9,6,7};
        quickSort(array);
        System.out.println(Arrays.toString(array));
    }
}

4.2.1.4 快排优化

快排的基准是随机选取的，一般情况下，快排的时间复杂度为 O(nlog(n))，比如数据是有序的1,2,3,4,5… 会变成 O(n²)

时间复杂度我们可以用二叉树来理解，如下：

一般情况下，基准到达对应的位置后，序列被分为了左右子序列，基准元素为根结点，左边都比根节点的值小，右边都比根节点的值大，此时时间复杂度为 O(nlog(n))

存在特殊情况，数据是有序的1,2,3,4,5…

只有一个分支，此时树的高度就是结点的个数，时间复杂度则为O(n²)，而当数据量足够大的时候，上述代码就无法跑通了~

【优化方法】

1）基准优化：三数取中法

即基准值取 left，mid，right 三个值中间的值，而不再是单纯取下标为 left 的值

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: wlx
 * Date: 2025-06-22
 * Time: 0:40
 */
public class quickSort {
    public static void quickSort(int[] num) {
        int left = 0;
        int right = num.length-1;
        quick(num,left,right);
    }

    public static void quick(int[] num, int left, int right) {
        if(left >= right) {
            return;
        }
        // 基准值优化
        int index = midThree(num,left,right);
        swap(num,index,left);

        int pivot = partition(num,left,right);
        quick(num,left,pivot-1);
        quick(num,pivot+1,right);
    }
    
    private static int midThree(int[] array,int left,int right) {
        int mid = (left + right) / 2;
        if (array[left] < array[right]) {
            if (array[mid] < array[left]) {
                return left;
            } else if (array[mid] > array[right]) {
                return right;
            } else {
                return mid;
            }
        } else {
            if (array[mid] < array[right]) {
                return right;
            } else if (array[mid] > array[left]) {
                return left;
            } else {
                return mid;
            }
        }
    }
    
    public static int partition(int[] arr,int left,int right) {
        int tmp = arr[left];

        while(left < right) {
            // 找到比基准tmp小的
            while(left < right && arr[right] >= tmp) {
                right--;
            }
            arr[left] = arr[right];
            // 找到比基准tmp大的
            while(left < right && arr[left] <= tmp) {
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] = tmp;
        return left;
    }



    public static void swap(int[] arr,int i,int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) {
        int[] array = {1,4,2,9,6,7};
        quickSort(array);
        System.out.println(Arrays.toString(array));
    }
}

2) 递归至较小的子区间时，使用插入排序：

递归至较小区间的时间，数据渐渐趋于有序，当数据有序的时候，建议直接使用插入排序，这样效率是比较高的

4.2.2 快排非递归实现

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: wlx
 * Date: 2025-06-22
 * Time: 22:41
 */

// 非递归实现快排
public class quickSort {
    public static void quickSort(int[] array) {
        Deque<Integer> stack = new LinkedList<>();
        int left = 0;
        int right = array.length - 1;
        int pivot = partition(array,left,right);
        if (pivot > left + 1) {
            stack.push(left);
            stack.push(pivot - 1);
        }
        if (pivot < right-1) {
            stack.push(pivot+1);
            stack.push(right);
        }
        while (!stack.isEmpty()) {
            right = stack.pop();
            left = stack.pop();
            pivot = partition(array,left,right);
            if (pivot > left + 1) {
                stack.push(left);
                stack.push(pivot - 1);
            }
            if (pivot < right-1) {
                stack.push(pivot+1);
                stack.push(right);
            }
        }
    }

    public static int partition(int[] arr,int left,int right) {
        int tmp = arr[left];

        while(left < right) {
            // 找到比基准tmp小的
            while(left < right && arr[right] >= tmp) {
                right--;
            }
            arr[left] = arr[right];
            // 找到比基准tmp大的
            while(left < right && arr[left] <= tmp) {
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] = tmp;
        return left;
    }

    public static void main(String[] args) {
        int[] array = {1,4,2,9,6,7};
        quickSort(array);
        System.out.println(Arrays.toString(array));
    }

}

5. 归并排序

【基本思想】归并排序是建立在归并操作上的一种有效算法，该算法是分治法的一种典型应用，将已有序的子序列合并，得到完全有序的序列，即先使每个子序列有序，将两个有序序列合并为一个有序序列，称为二路归并

【基本思路】使用递归的方式，先分解，再进行合并

【示意图】

【具体代码】

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: wlx
 * Date: 2025-06-21
 * Time: 22:53
 */
public class Mergesort {
    public static void mergeSort(int[] arr) {
        mergeFunc(arr,0,arr.length-1);
    }

    public static void mergeFunc(int[] arr,int left,int right) {
        if(left >= right) {
            return;
        }
        int mid = (left+right) / 2;
        mergeFunc(arr,left,mid);
        mergeFunc(arr,mid+1,right);
        merge(arr,left,right,mid);
    }

    public static void merge(int[] arr,int left,int right,int mid) {
        int start1 = left;
        int start2 = mid+1;
        int k = 0;
        int[] tmp = new int[right-left+1];
        while(start1 <= mid && start2 <= right) {
            if(arr[start1] < arr[start2]) {
                tmp[k++] = arr[start1++];
            } else {
                tmp[k++] = arr[start2++];
            }
        }

        while(start1 <= mid) {
            tmp[k++] = arr[start1++];
        }

        while(start2 <= right) {
            tmp[k++] = arr[start2++];
        }

        for(int i = 0; i < k; i++) {
            arr[left+i] = tmp[i];
        }
    }

    public static void main(String[] args) {
        int[] arr = {1,4,2,9,6,7};
        mergeSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

【特性总结】

1. 时间复杂度：O(O(N*logN))
2. 空间复杂度：O(1)
3. 稳定性：稳定
4. 应用场景：适合数据特别大的时候，当待排序数据特别大的时候，比如内存只要 10G，但是待排序的数据有 100G，此时可以将待处理的数据分为 20份，每一份 512M，利用归并排序分别对这 512M 的数据进行排序，同时进行二路归并，最后使数据变为有序，这就是文章一开头介绍的外部排序~

6. 特性总结

【注意】这里的时间复杂度为最坏时间复杂度

✨✨✨本期内容到此结束啦~