数据结构-八大排序

1. 插入排序

像玩扑克牌一样，将待排序的元素插入到已经排好序的序列中，直到所有记录插入完为止，得到一个新的有序序列。

1.1 直接插入排序

直接插入排序是一种简单直观的排序算法，适用于少量数据的排序。它的工作原理类似于玩扑克牌时整理手牌。具体步骤如下：

1. 初始状态：从第二个元素开始，认为第一个元素已经排好序。

2. 插入过程：

   • 取出下一个元素，在已经排好序的序列中从后向前扫描。
   • 如果已排序的元素大于新元素，则将已排序的元素向右移动一个位置。
   • 重复上述步骤，直到找到已排序元素小于或等于新元素的位置。
   • 将新元素插入到该位置。

3. 重复步骤：对每一个未排序的元素重复上述过程，直到所有元素都插入到正确的位置。

特点：

• 时间复杂度：最坏情况下为 (O(n^2))，最好情况下为 (O(n))（当输入数据已经有序时）。
• 空间复杂度：(O(1))，属于原地排序。
• 稳定性：插入排序是稳定的排序算法。

直接插入排序适合用于小规模数据的排序或部分有序的数组。

为什么要从后往前扫描？

便于移动元素：当从后向前扫描时，一旦发现一个已排序的元素比待插入元素大，就可以直接将这个元素向后移动一位。这样，可以为待插入元素腾出位置，直到找到合适的位置为止。

模拟实现

public void directInsertionSort(int[] array) {int length = array.length;for (int i = 1; i < length; i++) {int currentElement = array[i];int j = i - 1;// 从后向前扫描已排序部分，寻找插入位置while (j >= 0 && array[j] > currentElement) {array[j + 1] = array[j]; // 向后移动元素j--;}// 插入当前元素到正确位置array[j + 1] = currentElement;}
}

1.2 希尔排序

希尔排序（Shell Sort）是一种基于插入排序的高效排序算法。它通过比较相距一定间隔的元素来实现排序，这种间隔逐渐缩小，最终进行一次普通的插入排序。希尔排序的核心思想是通过不断减少间隔（也称为“增量”）来逐步提高序列的有序性。

算法步骤：

1. 选择增量序列：希尔排序的关键在于选择增量序列。最初的增量可以是数组长度的一半，然后逐步减小，通常选择为原增量的一半或其他合适的值，直到增量为1。

2. 分组排序：对于每一个增量，将数组元素分成若干组，每组包含相隔该增量的元素。对每组分别进行插入排序。

3. 缩小增量：减小增量，重复分组排序的过程，直到增量减小到1。

4. 最后排序：当增量为1时，进行一次标准的插入排序，此时整个数组已经基本有序，所以效率较高。

特点：

• 时间复杂度：希尔排序的时间复杂度依赖于增量序列的选择，最坏情况下为 $O(n^2)$，但通常情况下可以达到 $O(n^{1.3})$ 到 $O(n^{1.5})$。
• 空间复杂度：$O(1)$，属于原地排序。
• 稳定性：希尔排序不是稳定排序，因为相同元素可能会因为增量的变化而改变相对顺序。

优势：

希尔排序通过对大规模无序数据的初步排序，使得数据在后续的插入排序中更接近有序状态，从而减少了插入排序的移动次数，提高了整体效率。对于中等规模的数据集，希尔排序通常表现良好。

模拟实现：

    public void shellSort(int[] array) {int length = array.length;int gap = length;while (gap > 1) {gap = gap / 3 + 1;// 一共有多轮排序for (int start = 0; start < gap; start++) {// 插入排序for (int i = start + gap; i < length; i += gap) {int currentElement = array[i];int j = i - gap;// 从后向前扫描已排序部分，寻找插入位置while (j >= start && array[j] > currentElement) {array[j + gap] = array[j]; // 向后移动元素j -= gap;}// 插入当前元素到正确位置array[j + gap] = currentElement;}}}}

2. 选择排序

每一次从待排序的元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序元素排完。

2.1 直接选择排序

直接选择排序（Selection Sort）是一种简单直观的排序算法。它的基本思想是每次从待排序序列中选择最小（或最大）的元素，放到已排序序列的末尾，直到所有元素都被排序。

算法步骤：

1. 初始化未排序序列：将整个数组视为未排序序列。

2. 选择最小元素：从未排序序列中找到最小元素。

3. 交换位置：将找到的最小元素与未排序序列的第一个元素交换位置。

4. 缩小未排序序列：将已排序序列扩大一个元素，未排序序列缩小一个元素。

5. 重复步骤 2-4：直到未排序序列为空。

特点：

• 时间复杂度：最坏、平均、最好情况下的时间复杂度均为 (O(n^2))。
• 空间复杂度：(O(1))，属于原地排序。
• 稳定性：直接选择排序是不稳定的，因为相同元素的相对顺序可能会在交换过程中改变。

模拟实现：

    public void selectionSort(int[] array) {// 实现代码int length=array.length;for (int i=0;i<length;i++){int minIndex=i;for(int j=i+1;j<length;j++){if (array[minIndex]>array[j]){minIndex=j;}}if (minIndex!=i){swap(array,i,minIndex);}}}

2.2 堆排序

堆排序（Heap Sort）是一种基于堆数据结构的比较排序算法。堆是一种特殊的完全二叉树结构，分为最大堆和最小堆。堆排序通常使用最大堆来实现升序排序。

算法步骤：

1. 构建最大堆：将待排序数组构造成一个最大堆。最大堆的性质是每个节点的值都大于或等于其子节点的值。

2. 堆排序：

   • 交换堆顶元素（最大值）与堆的最后一个元素。
   • 减少堆的有效大小（即忽略最后一个元素）。
   • 调整堆，使其重新成为最大堆。
   • 重复以上步骤，直到堆的大小缩小到1。

特点：

• 时间复杂度：堆排序的时间复杂度为 (O(n \log n)) ，因为构建堆的时间复杂度为 (O(n))，每次调整堆的时间复杂度为 (O(\log n))，需要进行 (n-1) 次调整。
• 空间复杂度：(O(1))，属于原地排序。
• 稳定性：堆排序是不稳定的，因为在调整堆的过程中，可能会改变相同元素的相对顺序。

优势与劣势：

• 优势：堆排序具有较好的时间复杂度表现，尤其是在处理大规模数据时。
• 劣势：堆排序不是稳定排序，且在实现过程中可能不如快速排序等算法容易优化。

堆排序适用于需要原地排序且不要求稳定性的场景。它在最坏情况下的时间复杂度表现优于快速排序的 (O(n^2))，因此在某些情况下可能更具优势。

模拟实现：

   public void shiftDown(int[] array, int parent,int end){// 升序用大堆while(true){int leftChild=parent*2+1;int rightChild=parent*2+2;int largest=parent;if (leftChild<=end&&array[leftChild]>array[largest]){largest=leftChild;}if (rightChild<=end&&array[rightChild]>array[largest]){largest=rightChild;}if (largest==parent){return;}swap(array,parent,largest);}}public void heapSort(int[] array) {// 实现代码int length=array.length;// 构建大堆for (int parent=(length-1)/2;parent>=0;parent--){shiftDown(array,parent,length-1);}// 逐步将最大堆移到数组末尾，并调整剩余元素for (int i=length-1;i>0;i--){swap(array,0,i); // 将当前最大的放到数组末尾shiftDown(array,0,i-1); // 调整剩余的堆}}

3. 交换排序

根据序列中的两个元素的大小来交换这两个元素在序列中的位置。

3.1 冒泡排序

冒泡排序（Bubble Sort）是一种简单的交换排序算法，其基本思想是通过重复地遍历待排序序列，比较相邻元素并交换不符合顺序要求的元素，从而逐步将最大或最小的元素“冒泡”到序列的末尾。

算法步骤：

1. 初始化序列：从序列的起始位置开始。

2. 比较相邻元素：依次比较序列中的每对相邻元素。

3. 交换位置：如果前一个元素比后一个元素大（对于升序排序），则交换这两个元素的位置。

4. 重复遍历：对整个序列重复上述过程，直到没有任何元素需要交换，即序列已经有序。

特点：

• 时间复杂度：最坏和平均情况下的时间复杂度均为 (O(n^2))，最好情况下（序列已经有序）为 (O(n))。
• 空间复杂度：(O(1))，属于原地排序。
• 稳定性：冒泡排序是稳定的，因为相同元素的相对顺序不会改变。

模拟实现：

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

3.2 快速排序

快速排序（Quick Sort）是一种高效的排序算法，通常用于处理大规模数据。它的基本思想是通过分治法将数组分成较小的子数组进行排序。

算法步骤：

1. 选择基准（Pivot）：从数组中选择一个元素作为基准。基准的选择可以是随机的、固定位置的（如第一个或最后一个元素），或通过某种策略（如中位数）来选择。

2. 分区（Partition）：将数组分为两个子数组：一个子数组中的元素都小于基准，另一个子数组中的元素都大于基准。

3. 递归排序：对两个子数组递归地应用快速排序。

4. 合并结果：由于分区过程已经将数组分为有序的两个部分，因此不需要额外的合并步骤。

特点：

• 时间复杂度：平均情况下时间复杂度为 (O(n \log n))，最坏情况下（如每次选择的基准都是最大或最小元素）为 (O(n^2))。通过随机化基准选择或使用“三数取中”策略，可以有效减少出现最坏情况的概率。
• 空间复杂度：(O(\log n))，用于递归调用栈。
• 稳定性：快速排序是不稳定的，因为在分区过程中可能改变相同元素的相对顺序。

优势与劣势：

• 优势：快速排序通常比其他 (O(n \log n)) 排序算法（如堆排序、归并排序）更快，因为它对缓存友好，且递归层次较少。
• 劣势：在最坏情况下表现较差，但可以通过优化基准选择来减轻这种情况。

模拟实现：

    public void quickSort(int[] array, int low, int high) {// 实现代码if (low<high){int pivotIndex=medianOfThree(array,low,high);swap(array,low,pivotIndex);int pi=partition(array,low,high);quickSort(array,low,pi-1);quickSort(array,pi+1,high);}}private int partition(int[] array, int low, int high) {// 以array[low]为基准int left=low;int right =high;int pivot=array[low];while (left<right){while (left<right&&array[right]>=pivot){right--;}array[left]=array[right];while (left<right&&array[left]<=pivot){left++;}array[right]=array[left];}// 最终位置为什么会是这里？array[left]=pivot;return left;}private int medianOfThree(int[] array, int low, int high) {int mid=(low+high)/2;if (array[low]>array[mid]){swap(array,low,mid);}if (array[low]>array[high]){swap(array,low,high);}if (array[mid]>array[high]){swap(array,mid,high);}return mid;}

1. medianOfThree 方法从数组的第一个元素、最后一个元素和中间元素中选择基准，目的是减少最坏情况下（如已经有序的数组）出现的概率。

2. 分区过程：

   • 使用 partition 方法对数组进行分区。以 array[low] 为基准，初始化 left 和 right 指针。

   • 从右向左移动 right 指针，找到第一个小于基准的元素，并将其移动到 left 的位置。

   • 从左向右移动 left 指针，找到第一个大于基准的元素，并将其移动到 right 的位置。

   • 继续此过程，直到 left 和 right 相遇。

   • 最后，将基准放置在 left 的位置，这就是基准的最终位置。此位置左边的元素都小于基准，右边的元素都大于基准。

3.3 归并排序

归并排序（Merge Sort）是一种有效的、基于比较的排序算法，采用了分治法的思想。它将待排序的数组分成较小的子数组，分别进行排序，然后合并这些已排序的子数组，从而得到一个完全排序的数组。

算法步骤：

1. 分解（Divide）：

   • 将数组分成两个大致相等的子数组。

2. 递归排序（Conquer）：

   • 对每个子数组递归地应用归并排序。

3. 合并（Combine）：

   • 合并两个已排序的子数组，生成一个排序后的数组。

特点：

• 时间复杂度：无论最坏、最好或平均情况下，时间复杂度均为 (O(n \log n))。
• 空间复杂度：需要额外的 (O(n)) 空间来存储临时数组。
• 稳定性：归并排序是稳定的，因为在合并过程中可以保持相同元素的相对顺序。

优势与劣势：

• 优势：

  • 稳定性好，适用于链表等需要稳定排序的场景。
  • 对于非常大的数据集，归并排序的性能表现良好，尤其是在外部排序中。

• 劣势：

  • 需要额外的内存空间，这在内存受限的环境中可能是个问题。
  • 相比于快速排序，归并排序的常数因子较大，实际运行速度稍慢。

应用场景：

归并排序适用于处理大规模数据，尤其是在数据量超出内存限制的情况下（如外部排序）。它也常用于需要稳定排序的场合。由于其稳定性和良好的时间复杂度，归并排序在许多标准库中被实现为一种通用排序算法。

    public void mergeSort(int[] array, int left, int right) {// 实现代码if (left>=right){return;}int mid=(left+right)/2;mergeSort(array,left,mid);mergeSort(array,mid+1,right);merge(array,left,mid,right);}private void merge(int[] array, int left, int mid, int right) {int n1=mid-left+1;int n2=right-mid;int[]L=new int[n1];int[]R=new int[n2];System.arraycopy(array,left,L,0,n1);System.arraycopy(array,mid+1,R,0,n2);int k=left;int i=0;int j=0;while(i<n1&&j<n2){if (L[i]<R[j]){array[k]=L[i];i++;}else {array[k]=R[j];j++;}k++;}while (i<n1){array[k]=L[i];i++;}while (j<n2){array[k]=R[j];j++;}}

4. 计数排序

计数排序（Counting Sort）是一种线性时间复杂度的排序算法，适用于对整数进行排序，特别是在元素值范围较小的情况下。它通过计数每个元素出现的次数来确定每个元素在排序后的数组中的位置。

算法步骤：

1. 确定范围：

   • 找出待排序数组中的最大值和最小值，以确定计数数组的大小。

2. 计数元素出现次数：

   • 创建一个计数数组 count，其大小等于最大值与最小值的差加一。
   • 遍历待排序数组，计算每个元素出现的次数，并将结果存储在计数数组中。

3. 累加计数：

   • 对计数数组进行累加，以便确定每个元素在排序后的数组中的最终位置。

4. 构建排序后的数组：

   • 创建一个输出数组 output，根据计数数组中的信息，将每个元素放到正确的位置。

5. 将结果复制回原数组（可选）：

   • 将排序后的结果复制回原数组。

特点：

• 时间复杂度：计数排序的时间复杂度为 (O(n + k))，其中 (n) 是数组的大小，(k) 是计数数组的大小（即最大值与最小值的范围）。
• 空间复杂度：需要额外的 (O(k)) 空间来存储计数数组。
• 稳定性：计数排序是稳定的，因为在构建输出数组时，保持了相同元素的相对顺序。

优势与劣势：

• 优势：

  • 对整数排序非常快，尤其是范围较小时。
  • 适用于需要稳定排序的场合。

• 劣势：

  • 如果元素范围很大，计数数组会占用大量内存。
  • 不适合排序浮点数或非整数类型的数据。

应用场景：

计数排序常用于排序整数或字符（如 ASCII 码），尤其是在元素范围较小且需要稳定排序的情况下。它在某些特殊场合下可以提供非常高效的排序性能。

模拟实现：

    private void countingSort(int[] array){if (array.length==0){return;}// 找到数组中的最大最小值int max=array[0];int min=array[0];for (int i = 1; i < array.length; i++) {if (array[i] > max) {max = array[i];}if (array[i] < min) {min = array[i];}}// 创建计数数组int range=max-min+1;int[] count =new int[range];// 填充计数数组for (int num:array){count[num-min]++;}// 计算每个数组的最终位置for (int i=1;i<count.length;i++){count[i]+=count[i-1];}// 创建输出的数组int[] output=new int[array.length];// 将元素放到正确位置,从后面开始放保持稳定性for (int i=array.length-1;i>=0;i--){output[count[array[i]-min]-1]=array[i];count[array[i]-min]--;}System.arraycopy(output,0,array,0,array.length);}