前端排序算法 -- 希尔和计数排序

站长

2023年09月28日 21:49 · 阅读数 16

希尔排序算法

1. 介绍

希尔排序是一种插入排序的改进算法，也被称为缩小增量排序。它通过将待排序的数组分割成多个子序列来进行排序，最终逐步减少子序列的长度，直至完成整个数组的排序。

2. 实现过程

选择增量序列：选择一个适当的增量序列，通常使用希尔增量序列。希尔增量序列的选择可以根据经验或者实验得出，常见的选择方式是n/2、n/4、n/8...，其中n为数组长度。
根据增量将数组分割成子序列：根据选定的增量，将待排序的数组分割成多个子序列。每个子序列包含相距一定间隔（即增量）的元素。例如，如果增量为5，则第一个子序列包含原数组的索引为0、5、10...的元素，第二个子序列包含原数组的索引为1、6、11...的元素，以此类推。
对每个子序列进行插入排序：对每个子序列应用插入排序算法。插入排序是一种简单直观的排序算法，它将每个元素插入到已经排好序的子数组中的正确位置。
缩小增量并重复步骤2和步骤3：在上一步中，我们使用了一个较大的增量对数组进行了初步排序。现在，我们缩小增量的大小，并再次重复步骤2和步骤3。这样做的目的是逐渐减少子序列的长度，使得整个数组在每一轮排序中更加接近有序状态。
最后一次使用增量为1的插入排序：当增量减小至1时，最后一次进行插入排序时，即可完成整个排序过程。此时，整个数组被看作一个序列，通过插入排序将其完全有序化。

3. 伪代码

函数 希尔排序(数组arr):
    n = 数组长度
    增量序列 = 选择增量序列(n)  // 选择合适的增量序列
    
    while 增量序列 不为空:
        增量 = 增量序列.pop()  // 取出当前增量
        
        // 根据增量将数组分割成子序列并对每个子序列进行插入排序
        for i = 增量 到 n-1:
            temp = arr[i]
            j = i
            
            // 对当前子序列进行插入排序
            while j >= 增量 and arr[j-增量] > temp:
                arr[j] = arr[j-增量]
                j = j - 增量
                
            arr[j] = temp
        
    返回 排序后的数组

4. ts实现

function shellSort(arr: number[]): number[] {
  const n = arr.length;
  let gap = Math.floor(n / 2);

  while (gap > 0) {
    for (let i = gap; i < n; i++) {
      const temp = arr[i];
      let j = i;

      while (j >= gap && arr[j - gap] > temp) {
        arr[j] = arr[j - gap];
        j -= gap;
      }

      arr[j] = temp;
    }

    gap = Math.floor(gap / 2);
  }

  return arr;
}

const array = [7, 3, 9, 5, 1, 8, 2, 6, 4];
console.log(shellSort(array)); // Output: [1, 2, 3, 4, 5, 6, 7, 8, 9]

5. c实现

#include <stdio.h>

void shellSort(int arr[], int n) {
  int gap = n / 2;

  while (gap > 0) {
    for (int i = gap; i < n; i++) {
      int temp = arr[i];
      int j = i;

      while (j >= gap && arr[j - gap] > temp) {
        arr[j] = arr[j - gap];
        j -= gap;
      }

      arr[j] = temp;
    }

    gap /= 2;
  }
}

void printArray(int arr[], int n) {
  for (int i = 0; i < n; i++) {
    printf("%d ", arr[i]);
  }
  printf("\n");
}

int main() {
  int array[] = {7, 3, 9, 5, 1, 8, 2, 6, 4};
  int n = sizeof(array) / sizeof(array[0]);

  shellSort(array, n);
  printArray(array, n); // Output: 1 2 3 4 5 6 7 8 9

  return 0;
}

6. 复杂度分析

交换复杂度：希尔排序算法中的交换操作发生在子序列内部的插入排序过程中，而不是相邻元素之间的直接交换。因此，在每个子序列内部进行插入排序时，交换操作的次数会受到子序列长度和元素之间的比较结果影响。总体来说，希尔排序的交换次数通常会比冒泡排序或快速排序少。

比较复杂度：与交换复杂度类似，希尔排序的比较操作也发生在子序列内部的插入排序过程中。在每个子序列内部进行插入排序时，需要进行多次元素之间的比较。因此，与普通的插入排序相比，希尔排序的比较次数会减少，但仍然取决于增量序列的选择。

空间复杂度：希尔排序是一种原地排序算法，即它不需要额外的空间来存储临时数据。除了存储待排序数组外，希尔排序只需要使用常数级别的额外空间，因此其空间复杂度为O(1)。

时间复杂度：希尔排序的时间复杂度难以精确计算，取决于增量序列的选择。对于某些特定的增量序列，希尔排序的时间复杂度可以达到O(n log^2 n)级别。然而，在实际应用中，常见的增量序列（如希尔增量序列）通常能够将希尔排序的时间复杂度控制在O(n^2)以下，并且具有较好的性能。

计数排序算法