本文共 4239 字，大约阅读时间需要 14 分钟。

常见算法分类

算法的分类可根据其时间复杂度和排序方式主要分为以下几类：

1. 非线性时间比较类排序

这一类算法的核心是通过比较操作来进行排序，时间复杂度均为 O(n²)。主要包括以下几种：

• 交换类排序：快速排序和冒泡排序。
• 插入类排序：简单插入排序和希尔排序。
• 选择类排序：简单选择排序和堆排序。
• 归并排序：属于比较类排序中的一种，且通常被认为是最快的比较类算法。

2. 线性时间非比较类排序

这一类算法的核心是通过非比较的方式完成排序，时间复杂度为 O(n+k)，其中 k 是数据范围的大小。主要包括以下几种：

• 计数排序：通过统计每个数出现的次数来完成排序。
• 基数排序：通过将数据按特定基数分配到桶中，再对每个桶内部进行排序。
• 桶排序：与基数排序类似，但其桶内的排序方式是先进的比较排序算法。

算法描述与实现

1. 交换类排序

1.1 冒泡排序

算法思想：通过一系列的交换操作，每次交换相邻比较小的元素，并向前“冒”泡到正确的位置。

算法步骤：

从数组的第一个元素开始，依次与后面的元素比较并交换，直到最后一个元素。

如果某次循环中没有发生交换，则数组已经排序，结束算法。

优点：简单易实现，稳定性强。

缺点：在数据严重逆序时，效率较低。

时间复杂度：

• 最好情况 O(n)。
• 最坏情况 O(n²)。

示例代码：

void bubbleSort(int array[], int len) {
    for(int i = 0; i < len - 1; ++i) {
        bool noswap = true;
        for(int j = 0; j < len - i - 1; ++j) {
            if(array[j] > array[j+1]) {
                int temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
                noswap = false;
            }
        }
        if(noswap) break;
    }
}

1.2 快速排序

算法思想：将数组分为两部分，通过划分、控制子数组的范围进行排序，改进了冒泡排序的效率。

算法步骤：

选择一个元素作为划分元素，将所有小于该元素的元素放到左边，其他放到右边。

重复上述过程，直到整个数组排序。

优点：平均时间复杂度为 O(n log n)，效率高。

缺点：同初始情况不同，稳定性较差。

时间复杂度：

• 最好情况 O(n log n)。
• 最坏情况 O(n²)。

示例代码：

void quickSort(int a[], int low, int high) {
    if(low >= high) return;
    int left = low, right = high;
    int key = a[left];
    while(left < right && a[right] >= key) {
        right--;
        a[left] = a[right];
        right++;
    }
    while(left < right && a[left] <= key) {
        left++;
        a[right] = a[left];
        right--;
    }
    a[left] = key;
    quickSort(a, low, left-1);
    quickSort(a, left+1, high);
}

2. 插入类排序

2.1 直接插入排序

算法思想：通过逐个插入元素到已经有序的数组中。

算法步骤：

从第二个元素开始，依次将元素插入到适当的位置。

一个个检查位置并进行交换。

优点：简单易实现。

缺点：当数据严格逆序时效率较低。

时间复杂度：

• 最好情况 O(n)。
• 最坏情况 O(n²)。

示例代码：

void insertSort(int A[], int len) {
    for(int i = 1; i < len; ++i) {
        int temp = A[i];
        int j = i-1;
        while(j >= 0 && A[j] > temp) {
            A[j+1] = A[j];
            j--;
        }
        if(j != i-1) {
            A[j+1] = temp;
        }
    }
}

2.2 希尔排序

算法思想：通过逐渐缩小增量，对相邻指定距离的元素进行排序。

优点：在数据局部有序时效率较高。

时间复杂度：

• 一般情况 O(n log n)。
• 最坏情况 O(n²)。

示例代码：

void shellSort(int A[], int len, int d) {
    for(int inc = d; inc > 0; inc /= 2) {
        for(int i = inc; i < len; ++i) {
            int j = i - inc;
            while(j >= 0 && A[j] > A[i]) {
                A[j+inc] = A[j];
                j -= inc;
            }
            if(j != i - inc) {
                A[j+inc] = A[i];
            }
        }
    }
}

3. 选择类排序

3.1 简单选择排序

算法思想：每次从剩余数组中找到最小的元素交换到当前位置。

优点：实现简单。

缺点：比较次数较多，效率低。

时间复杂度：

• 最好情况 O(n)。
• 最坏情况 O(n²)。

示例代码：

void selectSort(int A[], int len) {
    for(int i = 0; i < len; ++i) {
        int j = i;
        for(int k = i + 1; k < len; ++k) {
            if(A[k] < A[j]) {
                j = k;
            }
        }
        if(i != j) {
            int temp = A[i];
            A[i] = A[j];
            A[j] = temp;
        }
    }
}

3.2 堆排序

算法思想：通过构建大顶堆或小顶堆，将最大元素逐步移动到数组的末尾。

优点：时间复杂度近似于 O(n log n)。

时间复杂度：

• 建立堆：O(n)。
• 调整堆：O(n log n)。

示例代码：

void minHeapFixUp(int a[], int i) {
    int j;
    while(j = (i-1)/2, j >= 0 && a[j] <= a[i]) {
        a[i] = a[j];
        j = (j-1)/2;
    }
    a[j+1] = a[i];
}

4. 归并排序

算法思想：通过分治法将数组分成两部分，分别排序后进行合并。

时间复杂度：

• 最好情况 O(n log n)。

示例代码（部分）：

void merge(int left[], int left_len, int right[], int right_len, int result[]) {
    int i = j = 0;
    while(i < left_len && j < right_len) {
        if(left[i] <= right[j]) {
            result[i + j] = left[i];
            i++;
        }
        else {
            result[i + j] = right[j];
            j++;
        }
    }
    while(i < left_len) result[i + j++] = left[i++];
    while(j < right_len) result[i + j++] = right[j++];
}
void mergeSort(int a[], int len) {
    int len_left = len / 2;
    int len_right = len - len_left;
    mergeSort(a, len_left);
    mergeSort(a, len_right);
    merge(a, len_left, a, len_right, a);
}

5. 线性时间非比较类排序

5.1 计数排序

算法思想：对数据进行计数，然后根据计数重新排列数据。

时间复杂度：O(n + k)，k 为数据范围。

示例代码：

int countSort(int *arr, int *sorted_arr, int n) {
    int max = 100;
    int count[max];
    for(int i = 0; i < n; ++i) {
        count[arr[i]]++;
    }
    for(int i = 0; i < max; ++i) {
        sorted_arr[cnt[i]]++;
        cnt[i]--;
    }
    free(count);
}