排序算法在计算机科学中占据着非常基础且重要的地位。无论是在日常开发，还是在各种算法面试中，排序问题都频繁出现，其中快速排序、归并排序和堆排序更是面试中的重难点和高频考点。掌握这些排序算法不仅是算法学习的基石，更是应对复杂数据结构与问题的有力工具。

要想在算法面试中展现无敌的实力，光靠死记硬背显然不够。系统性地学习和理解这些排序算法，深入了解它们在不同场景中的优势与劣势，才能为自己建立一套坚固的“算法武装”。本文将详细介绍七大常见的排序算法(选择排序，插入排序，快速排序，归并排序，冒泡排序，希尔排序，以及堆排序)，并通过对比它们的优劣势，帮助大家培养在不同应用场景下算法/技术选型的意识和能力。这种系统性的学习方法，将让大家在未来的算法面试中更加从容不迫，稳步胜出。

一、选择排序

1. 介绍：
   选择排序（英语：Selection Sort）是一种原地比较排序算法。它的时间复杂度为O(n^2)，这使得它在处理大型列表时效率较低，并且通常比类似的插入排序表现更差。选择排序以其简单性著称，在某些情况下（尤其是辅助内存受限时）相比于更复杂的算法具有性能优势。
   选择排序的工作原理如下：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

2. 流程图
   

3. 代码实现：
   Java：

public int[] selectionSort(int[] nums) {
    if(nums == null || nums.length == 0) {
        return nums;
    }
    
    for (int i = 0; i < nums.length - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] < nums[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            swap(nums, i, minIndex);
        }
    }
    
    return nums;
}

private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

4. 性能分析：
   时间复杂度
   对于一个包含 n 个元素的数组，选择排序需要进行 n - 1 轮比较和交换操作。在每一轮中，需要比较未排序部分的所有元素，即大约 n - i 次比较（其中 i 是当前轮数）。所以总的比较次数为：(n - 1) + (n - 2) +... + 2 + 1 = n (n - 1)/2。在每一轮中，最多进行一次交换操作。总共进行 n - 1 轮，所以交换次数为 n - 1。由于比较次数为n (n - 1)/2，与交换次数 n - 1 相比，比较次数在数量级上占主导地位。n (n - 1)/2而可以近似看作n^2/2，忽略常数系数，时间复杂度为O(n^2)。
   空间复杂度
   选择排序是一种原地排序算法，即在排序过程中不需要额外的数组或数据结构来存储数据。它只需要几个额外的变量来记录最小元素的索引和进行交换操作时的临时变量。这些额外变量的数量与输入规模 n 无关，不随输入规模的增长而增长。所以选择排序的空间复杂度为O(1)。

   稳定性
   选择排序是不稳定的排序算法。
   稳定性的定义:
   在排序算法中，如果两个相等的元素在排序前后的相对顺序保持不变，则称该排序算法是稳定的；否则，称该排序算法是不稳定的。

   选择排序不稳定的原因:
   在选择排序的过程中，每次从待排序序列中选择最小（或最大）的元素，并将其与当前位置的元素交换。如果待排序序列中有两个相等的元素，且较小的那个元素在后面，当选择到较小的那个元素并与当前位置交换时，就可能会改变这两个相等元素的相对顺序。

   例如，有数组[4a, 4b, 1]，第一次选择最小元素1与第一个元素4a交换，变为[1, 4b, 4a]；这里原本在后面的4b在排序后跑到了前面的4a前面，破坏了相等元素的相对顺序，所以选择排序是不稳定的。

二、插入排序

1. 介绍：
   插入排序（英语：Insertion Sort）是一种简单的排序算法，它通过比较逐一构建最终的已排序数组（或列表）。相比于快速排序、堆排序或归并排序等更高级的算法，插入排序在处理大型列表时效率要低得多。然而，插入排序具有以下几个优势：

• 实现简单：Jon Bentley 展示了一种仅使用三行类C伪代码实现的版本，并且经过优化后只需五行代码。
• 对（相当）小的数据集效率较高，类似于其他时间复杂度为O(n^2)的排序算法。
• 在实践中比大多数其他简单的平方级别算法（如选择排序或冒泡排序）更高效。
• 自适应：即对于已经基本排序的数据集效率较高：当输入中的每个元素离其排序位置不超过 k 个位置时，时间复杂度为 O(kn)。
• 稳定：即不会改变具有相同键值的元素的相对顺序。
• 原地排序：即仅需要 O(1) 的常数额外内存空间。
• 在线排序：即可以在接收数据的同时进行排序。
  当人们手动整理一副桥牌时，大多数人使用的方法与插入排序类似。

插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

1. 初始状态下，将第一个元素视为已排序的序列，其余元素为未排序序列。
2. 从第二个元素开始，依次取出未排序序列中的元素，与已排序序列中的元素从后向前进行比较。
3. 如果当前未排序元素小于已排序序列中的某个元素，就将该元素向后移动一位，继续向前比较，直到找到合适的位置插入当前未排序元素。
4. 重复这个过程，直到所有元素都插入到已排序序列中的合适位置，此时整个序列就变为有序的了。

2.流程图

3. 代码实现：
   Java中：

public int[] insertionSort(int[] nums) {
    if (nums == null || nums.length == 0) {
        return nums;
    }

    for (int i = 1; i < nums.length; i++) {
        int current = nums[i];
        int j = i - 1;
        while (j >= 0 && current < nums[j]) {
            nums[j + 1] = nums[j];
            j--;
        }
        nums[j + 1] = current;
    }

    return nums;
}

4. 性能分析：
   时间复杂度
   插入排序的时间复杂度为 O(n^2)，其中 n 是待排序数组的长度。

1.最坏情况：当输入数组是逆序排列时，每次插入一个元素都需要与已排序部分的所有元素进行比较和移动，所以比较和移动的次数最多为 1 + 2 + 3 + ... + (n - 1)，即n(n - 1)/2，时间复杂度为O(n^2)。
2. 最好情况：当输入数组已经是有序的时，每个元素只需要与已排序部分的最后一个元素比较一次，不需要进行移动操作，时间复杂度为O(n)。

3. 平均情况：平均情况下，插入排序的时间复杂度也为O(n^2)。

空间复杂度
插入排序的空间复杂度为O(1)，因为它只需要常数级别的额外空间。

在排序过程中，只需要一个额外的变量来存储当前要插入的元素，不需要像一些其他排序算法那样需要额外的数组或数据结构来存储中间结果。

稳定性
插入排序是稳定的排序算法。

1. 稳定性的定义
   在排序算法中，如果两个相等的元素在排序前后的相对顺序保持不变，则称该排序算法是稳定的；否则，称该排序算法是不稳定的。

2. 插入排序稳定的原因
   插入排序在比较和移动元素的过程中，当遇到相等的元素时，不会交换它们的位置，而是保持不动。这样就保证了相等元素在排序前后的相对顺序不会改变。

例如，有数组[3a, 2, 3b, 1]，在插入排序过程中，首先2和3a比较，将2插入到合适位置得到[2, 3a, 3b, 1]；接着处理3b，由于3b和3a相等，发现已经在合适位置，所以保持不动，得到[2, 3a, 3b, 1]；最后处理1，将其插入到合适位置得到[1, 2, 3a, 3b]。这里原本在前面的3a和后面的3b在排序后相对顺序没有改变，所以插入排序是稳定的。

三、快速排序

1. 介绍：
   快速排序（英语: Quick Sort）是一种高效的通用排序算法。它由英国计算机科学家Tony Hoare于1959年开发，并于1961年发表。至今，快速排序仍然是一种常用的排序算法。总体上，对于随机化数据，特别是较大的数据集，快速排序比归并排序和堆排序稍快一些。
   快速排序是一种分治算法。它的工作原理如下：
   1.选择基准值：首先从待排序的数组中选择一个元素作为基准值（pivot）。通常可以选择第一个元素、最后一个元素或者随机选择一个元素作为基准值。
   2.分区操作：对数组进行分区（partition），使得比基准值小的元素都在基准值的左边，比基准值大的元素都在基准值的右边。经过分区操作后，基准值将数组分为了两部分，左边部分的元素都小于等于基准值，右边部分的元素都大于等于基准值。
   3.递归排序：对分区后的左右两部分子数组分别重复上述步骤，即选择基准值、进行分区操作、递归排序，直到子数组的长度为 1 或 0，此时子数组已经有序，则整个数组有序，排序完成。

2. 流程图
   

3. 代码实现：
   Java中：

public int[] quickSort(int[] array) {
    if (array == null || array.length == 0) {
        return array;
    }
    quickSortRecursive(array, 0, array.length - 1);
    return array;
}

private void quickSortRecursive(int[] array, int left, int right) {
    if (left >= right) {
        return;
    }

    int pivotIndex = partition(array, left, right);
    quickSortRecursive(array, left, pivotIndex - 1);
    quickSortRecursive(array, pivotIndex + 1, right);
}

private int partition(int[] array, int left, int right) {
    int pivot = array[right];
    int i = left;
    int j = right - 1;
    while (i <= j) {
        if (array[i] <= pivot) {
            i++;
        } else {
            swap(array, i, j);
            j--;
        }
    }
    swap(array, i, right);
    return i;
}

private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

4. 性能分析：
   时间复杂度
   1.最好情况：

• 当每次划分都能将数组分为两个大小相等的子数组时，时间复杂度为O(nlogn)。
• 这是因为每次划分都将问题规模减半，划分次数为logn（以 2 为底），而每次划分需要线性时间O(n)来处理子数组，所以总的时间复杂度为O(nlogn)。
  2.平均情况：
• 平均情况下，快速排序的时间复杂度也为O(nlogn)。
• 快速排序在平均情况下表现良好，因为它随机选择基准值的概率较大，使得划分相对均匀。
  3.最坏情况：
• 当每次划分都将数组分为一个非常小的子数组和一个非常大的子数组时，时间复杂度为O(n^2)。
• 例如，当数组已经有序或者逆序时，每次选择的基准值都是最小或最大的元素，导致划分极不均匀，需要进行O(n)次划分，每次划分需要O(n)的时间，所以总的时间复杂度为O(n^2)

空间复杂度

1. 快速排序的空间复杂度主要取决于递归调用的栈空间。
2. 最好情况和平均情况下，空间复杂度为logn，因为每次划分都能将问题规模减半，递归深度为logn。
3. 最坏情况（数组已经有序或逆序）下，空间复杂度为O(n)，因为每次划分都只能减少一个元素，递归深度为O(n)。

稳定性
快速排序是不稳定的排序算法。因为在分区过程中，如果有两个相等的元素，它们的相对顺序可能会因为分区而改变。

四、归并排序

1. 介绍：
   归并排序（英语：Merge Sort）采用分治（Divide and Conquer）策略。首先将待排序的数组不断地分成两半，直到每个子数组只包含一个元素或者为空。这个过程被称为 “分”。然后，将两个已排序的子数组合并成一个更大的有序数组。这个过程被称为 “治” 或 “归并”。

2. 流程图
   

3. 代码实现：
   Java中：

public int[] mergeSort(int[] array) {
    if (array == null || array.length == 0) {
        return array;
    }
    
    int[] helper = new int[array.length];
    mergeSort(array, helper, 0, array.length - 1);
    return array;
}

private void mergeSort(int[] array, int[] helper, int left, int right) {
    if (left == right) {
        return;
    }

    int mid = left + (right - left) / 2;
    mergeSort(array, helper, left, mid);
    mergeSort(array, helper, mid + 1, right);
    merge(array, helper, left, mid, right);
}

private void merge(int[] array, int[] helper, int left, int mid, int right) {
    for (int i = left; i <= right; i++) {
        helper[i] = array[i];
    }
    
    int i = left;
    int j = mid + 1;
    int index = left;
    while (i <= mid && j <= right) {
       if (helper[i] <= helper[j]) {
           array[index] = helper[i];
           i++;
       } else {
           array[index] = helper[j];
           j++;
       }
       index++;
   }
   
    while (i <= mid) {
       array[index] = helper[i];
       i++;
       index++;
   }
   
   while (j <= right) {
       array[index] = helper[j];
       j++;
       index++;
   }
}

4. 性能分析：
   时间复杂度
   归并排序的时间复杂度始终为O(nlogn) ，其中 n 是待排序数组的长度。

• 归并排序的主要思想是分治，将数组不断地分成两半，直到每个子数组只有一个元素，然后再将子数组合并起来。
• 分治的过程可以用一个递归树来表示，树的高度为logn（以 2 为底），因为每次都将问题规模减半。
• 而每次合并两个子数组的时间复杂度为 ，因为需要遍历两个子数组的所有元素。
• 所以总的时间复杂度为 。

空间复杂度
归并排序的空间复杂度为O(n)。

• 在归并过程中，需要额外的空间来存储临时数组，临时数组的大小与原数组的大小相同，所以空间复杂度为O(n)。
• 但是，归并排序可以通过一些技巧来减少空间复杂度，例如在原地进行归并，或者使用链表来实现归并排序，这样可以将空间复杂度降低到 O(logn)（递归栈的空间)。

稳定性
归并排序是稳定的排序算法。在归并过程中，当比较两个相等的元素时，会先将左边子数组中的元素放入临时数组，这样就保证了相等元素的相对顺序不会改变。

五、冒泡排序

1. 介绍：
   冒泡排序（英文：Bubble Sort）是一种简单的排序算法，它通过反复遍历输入列表，逐个比较当前元素与其后面的元素，如果需要则交换它们的值。这种遍历会一直重复，直到在一次遍历中不再需要进行任何交换，这意味着列表已经完全排序。该算法是一种比较排序，之所以得名，是因为较大的元素在排序过程中会像气泡一样“冒”到列表的顶端。

2. 流程图
   

3. 代码实现：
   Java中：

public int[] bubbleSort(int[] array) {
    if (array == null || array.length == 0) {
        return array;
    }

    int n = array.length;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                swap(array, j, j + 1);
            }
        }
    }

    return array;
}

private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

优化版本：
优化策略：冒泡排序通过每轮比较未排序部分，确定一个元素的最终排序位置。其基本原理是通过比较相邻元素，将较大的元素逐步交换至右侧。如果在某一轮排序中未发生任何交换，则说明相邻元素的比较过程中，较大的元素已位于右侧，无需进一步调整，表明数组已然有序，此时排序过程可以终止。

public int[] bubbleSort(int[] array) {
    if (array == null || array.length == 0) {
        return array;
    }

    int n = array.length;
    for (int i = 0; i < n; i++) {
        boolean swapped = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                swap(array, j, j + 1);
                swapped = true;
            }
        }
        if (!swapped) {
            break;
        }
    }

    return array;
}

private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

4. 性能分析：
   时间复杂度
   1.最坏情况：

• 当输入数组是逆序排列时，每一次比较都需要进行交换操作。
• 对于长度为n的数组，外层循环需要执行n - 1次，内层循环在每次外层循环中，分别执行n - 1、n - 2、n - 3……1 次。
• 总的比较和交换次数为：(n - 1) + (n - 2) + (n - 3) + ... + 3 + 2 + 1 = n(n - 1)/2。
• 所以最坏情况下时间复杂度为 O(n^2)。
  2.最好情况：
• 当输入数组已经是有序的时，内层循环第一次遍历后就不会再进行任何交换操作，直接退出排序过程。
• 此时时间复杂度为O(n)，因为只需要进行n - 1次比较。
  3.平均情况：
• 平均情况下，时间复杂度也为O(n^2)。因为平均来说，需要进行多次比较和交换才能将数组排序。

空间复杂度

1. 冒泡排序是一种原地排序算法，只需要常数级别的额外空间。
2. 在排序过程中，只使用了一个临时变量用于交换两个元素的值，没有其他额外的数据结构占用空间。
3. 所以空间复杂度为O(1)。

稳定性

1. 冒泡排序是一种稳定的排序算法。
2. 当进行相邻元素的比较和交换时，如果两个元素相等，不会进行交换操作，从而保证了相等元素的相对顺序不会改变。

六、希尔排序

1. 介绍：
   希尔排序（英语：Shellsort），是一种原地比较排序算法。它可以看作是交换排序（如冒泡排序）或插入排序的一种推广。该方法通过首先排序相隔较远的元素对，然后逐渐减少比较元素之间的间隔。通过从相隔较远的元素开始，希尔排序能够比简单的相邻交换更快地将一些错位的元素移动到正确的位置。Donald Shell 于1959年首次发表了这种排序算法。希尔排序的运行时间高度依赖于所使用的间隔序列，对于许多实际变体而言，确定其时间复杂度仍然是一个未解的问题。
   其基本原理如下：
   一、分组与间隔
   1.希尔排序首先将待排序的数组分割成若干个子序列，每个子序列的元素间隔为一个特定的 “增量”（increment）。
   2.初始时，增量通常取数组长度的一半，然后逐渐减小增量，直到增量为 1。
   二、子序列排序
   1.对每个子序列分别进行插入排序。

   • 由于子序列中的元素间隔较大，移动元素的距离较远，能够快速地将不相邻的元素移动到大致正确的位置上，从而使整个数组在早期阶段就变得部分有序。
     三、逐步缩小增量
     1.随着增量的逐渐减小，子序列中的元素越来越接近相邻的位置。
     2.当增量为 1 时，实际上就是对整个数组进行一次普通的插入排序。但此时由于数组已经部分有序，插入排序的效率会大大提高。

2. 流程图
   

3. 代码实现：
   Java中：

public int[] shellSort(int[] array) {
    if (array == null || array.length == 0) {
        return array;
    }
    int n = array.length;
    for(int gap = n / 2; gap > 0; gap /= 2){
        for(int i = gap; i < n; i++){
            int j = i;
            int temp = array[i];
            while (j - gap >= 0 && array[j - gap] > temp){
                array[j] = array[j - gap];
                j -= gap;
            }
            array[j] = temp;
        }
    }
    return array;
}

4. 性能分析：
   时间复杂度
   希尔排序的时间复杂度与增量序列的选择有关，并且在实践中通常比 O(n^2) 的排序算法（如插入排序）更有效。
   空间复杂度
   希尔排序是一种原地排序算法，只需要常数级别的额外空间。在排序过程中，只使用了有限个临时变量用于交换元素，没有其他额外的数据结构占用空间。所以空间复杂度为 O(1) 。
   稳定性
   希尔排序是不稳定的排序算法。因为在不同的子序列中进行插入排序时，相同元素的相对位置可能会发生改变。

七、堆排序：

1. 基本原理：
   堆排序（英语：Heap Sort）是一种基于比较的排序算法，可以被视为“使用高效的数据结构实现的选择排序”。与选择排序类似，堆排序将输入数据分为已排序区域和未排序区域，并通过从未排序区域中提取最大元素并将其插入已排序区域来逐步缩小未排序区域。不同于选择排序，堆排序不会浪费时间对未排序区域进行线性扫描，而是通过维持一个堆数据结构来高效地找到每一步中的最大元素。
   尽管在大多数计算机上比实现良好的快速排序稍慢，但堆排序具有实现非常简单和更有利的最坏情况时间复杂度 O(nlog⁡n)的优点。大多数实际应用的快速排序变体在检测到快速排序性能下降时，会包括堆排序作为备选方案。堆排序是一种原地算法，但它不是稳定排序算法。
   其基本原理如下：
   一、堆的概念
   1.堆是一种完全二叉树，分为大顶堆和小顶堆。

• 大顶堆：每个节点的值都大于或等于其子节点的值。
• 小顶堆：每个节点的值都小于或等于其子节点的值。
  二、排序过程
  1.首先，将待排序的数组构建成一个堆。
• 从最后一个非叶子节点开始，逐步调整以满足堆的性质。对于一个长度为n的数组，最后一个非叶子节点的索引为(n/2)-1。
• 通过不断地比较节点与其子节点的值，进行交换操作，使整个数组满足堆的性质。
  2.构建好堆之后，数组的第一个元素就是堆中的最大（或最小）元素。
• 将第一个元素与最后一个元素交换，此时最大（或最小）元素就被放置在数组的最后位置。
• 然后，对剩余的n-1个元素重新调整为堆。
• 重复这个过程，每次将当前堆的最大（或最小）元素与未排序部分的最后一个元素交换，然后调整堆，直到整个数组有序。

2. 流程图
   

3. 代码

Java代码：

public int[] heapSort(int[] array) {
    if (array == null || array.length == 0) {
        return array;
    }

    int n = array.length;
    // 建一个大顶堆
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(array, i, n);
    }

    // 将未排序部分的最大数交换至已排序部分，再进行一次堆化以保持堆的结构
    for (int i = 0; i < n - 1; i++) {
        swap(array, 0, n - 1 - i);
        heapify(array, 0, n - 1 - i);
    }

    return array;
}

private void heapify(int[] array, int i, int length) {
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    int largest = i;

    if (left < length && array[left] > array[largest]) {
        largest = left;
    }

    if (right < length && array[right] > array[largest]) {
        largest = right;
    }

    if (largest != i) {
        swap(array, i, largest);
        heapify(array, largest, length);
    }
}

private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

4. 性能分析
   时间复杂度
   堆排序的时间复杂度为O(nlogn)。

• 构建初始堆的过程需要的时间为O(n)。
  • 自底向上从非叶子节点开始堆化，每一层的时间复杂度为当前层的高度 x 节点的个数，总的时间复杂度为
    1 * n / 4 + 2 * n / 8 + 3 * n / 16 + … + logn
    令 n / 4 = 2 ^ k, 2 ^ k (1 / 2 ^ 0 + 2 / 2 ^ 1 + 3 / 2 ^ 2 + … + (k + 1) / 2 ^ k) = C n (C 为一个常数)
    所以总的时间复杂度为O(n)
• 在排序过程中，每次从堆中取出最大（或最小）元素并调整堆，需要O(logn)的时间，一共进行 n 次操作，所以排序的时间复杂度为O(nlogn)。
  综上，时间复杂度为O(n + nlogn) = O(nlogn)
  空间复杂度
  堆排序的空间复杂度可以从两方面来分析：原地排序和递归调用栈的空间。

1. 原地排序的空间复杂度：
   堆排序是一种原地排序算法，它在排序过程中只使用了常数的额外空间，不需要开辟额外的数组来存储元素。因此，它的额外空间复杂度是 O(1)。
2. 递归调用的空间复杂度：
   在实现中，堆排序使用递归来进行堆化操作。递归的深度等于堆的高度，而堆的高度为 O(logn)，因此递归调用栈的空间复杂度是 O(logn)。
   稳定性
   堆排序是不稳定的排序算法。

• 在调整堆的过程中，如果有相同的值，它们的相对位置可能会发生改变。例如，当一个较大的值在后面，而在调整堆时被交换到前面，就可能导致相同值的相对顺序改变。