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

一、插入排序

1. 直接插入排序

直接插入排序（Direct Insertion Sort）是一个简单的插入排序算法，其工作原理为通过不断将元素插入到一个有序的位置中，逐步形成一个有序序列。

特点：

• 在序列基本有序的情况下，直接插入排序的效率最好。
• 优化：将数组的第一个位置作为哨兵，剩下的数据作为真正的数据部分进行比较和插入。

2. 折半插入排序

折半插入排序（Half Insertion Sort）是在直接插入排序的基础上对寻找插入位置的算法进行了优化，采用了折半查找方法。

特点：

• 优化了插入位置的搜索算法，通常使用折半查找法。
• 插入位置始终是 high + 1 的位置。

3. 希尔排序

希尔排序（Shell Sort）是一种伪直接插入排序算法，通过一定的间隔来分组插入，以加快排序速度。

特点：

• 算法值得注意的是其时间复杂度并未被详细计算。
• 不是一个稳定的算法，可能导致相同元素的位置发生改变。

二、交换排序

1. 没冒泡排序

冒泡排序（Bubble Sort）是一种每次仅交换相邻元素的简单排序算法。

特点：

• 稳定性：冒泡排序是稳定的排序算法。
• 效率特点：在序列基本有序时效率较好，每次排序后会将最大或最小的元素位置确定。

2. 快速排序

快速排序（Quicksort）是一种经典的分治算法。

特点：

• 特点：
  • 每次快速排序都会确定一个元素的最终位置。
  • 小于枢轴的元素会被移到左边，大于枢轴的元素会被移到右边。
  • 不是一个稳定的算法，可能因枢轴选取位置导致相等元素的位置改变。
• 效率特点：在一般情况下效率最佳，时间复杂度为 O(n log n)，通常实现采用递归。
• 优化点：每次排序后会确定中间值的位置，而不是最大值或最小值的位置。

三、选择排序

1. 简单选择排序

简单选择排序（Simple Selection Sort）是一种选择排序算法，通过每次选择当前最小或最大值的位置来实现排序。

特点：

• 效率特点：效率与序列的初始状态无关。
• 稳定性：该算法是不稳定的，可能破坏序列的稳定性。

2. 堆排序

堆排序（Heap Sort）是一种基于优先队列的排序算法。

特点：

• 特点：
  • 堆排序需要注意其不稳定的性质，可能会破坏相等元素的位置。
  • 每一次排序后都会确定一个最大值的最终位置。
• 工作原理：通过不断调整大根堆的位置，将元素依次输出到最终的有序序列中。

四、归并排序

归并排序（Merge Sort）是一种外部比较排序算法。

特点：

• 特点：
  • 归并排序是稳定的，且每一趟的比较时间复杂度为 O(n) 。
  • 归并排序实现时通常需要确定归并的趟数 m 的值，满足 m ≥ log2(n) 。

五、基数排序

基数排序（Radix Sort）是一种不基于比较和移动的内部排序算法。

特点：

• 特点：
  • 基数排序是唯一一个不依赖比较操作的排序算法。
  • 基数排序是稳定的，其时间复杂度与数据的初始状态无关。

六、代码实现

以下是多种排序算法的伪代码实现：

void InsertSort(int *a, int n) {
    int i, j;
    for (i = 2; i <= n; i++) {
        a[0] = a[i];
        for (j = i - 1; a[0] < a[j]; j--) {
            a[j + 1] = a[j];
        }
    }
}
void MidSort(int *a, int n) {
    int i, j;
    for (i = 2; i <= n; i++) {
        a[0] = a[i];
        int low = mid + 1;
        int high = mid - 1;
        while (low <= high) {
            mid = (low + high) / 2;
            if (a[0] < a[mid]) {
                // 进入左半部分
            } else {
                // 进入右半部分
            }
        }
    }
}
void ShellSort(int *a, int n) {
    int dk;
    int i, j;
    for (dk = n / 2; dk >= 1; dk = dk / 2) {
        for (i = 1 + dk; i <= n; i++) {
            a[0] = a[i];
            for (j = i - dk; j > 0 && a[0] < a[j]; j -= dk) {
                a[j + dk] = a[j];
            }
        }
    }
}
void SwapSort(int *b, int n) {
    int i, j;
    for (i = 0; i < n - 1; i++) {
        if (b[i] > b[j]) {
            swap(b[i], b[j]);
            flag = 1;
        }
        if (flag == 0) {
            return;
        }
    }
}
void Divide(int *b, int low, int high) {
    int pivot = b[low];
    while (low < high) {
        while (low < high && b[high] >= pivot) {
            high--;
            b[low] = b[high];
        }
        while (low < high && b[low] <= pivot) {
            low++;
            b[high] = b[low];
        }
        b[low] = pivot;
        return low;
    }
}
void QuickSort(int *b, int low, int high) {
    if (low < high) {
        int divided;
        divided = Divide(b, low, high);
        QuickSort(b, low, divided - 1);
        QuickSort(b, divided + 1, high);
    }
}
void SelectSort(int *b, int n) {
    int i, j, min, swap;
    for (i = 0; i < n - 1; i++) {
        min = i;
        for (j = i + 1; j < n; j++) {
            if (b[j] < b[min]) {
                min = j;
            }
        }
        if (min != i) {
            swap = b[min];
            b[min] = b[i];
            b[i] = swap;
        }
    }
}
void HeapCreate(int *a, int len) {
    int i;
    for (i = len / 2; i > 0; i--) {
        HeapAdjust(a, i, len);
    }
}
void HeapSort(int *a, int len) {
    int i;
    HeapCreate(a, len);
    for (i = len; i > 1; i--) {
        swap = a[i];
        a[i] = a[1];
        a[1] = swap;
        HeapAdjust(a, 1, i - 1);
    }
}
void Merge(int *b, int low, int mid, int high) {
    int *c = (int *)malloc( (high - low + 1) * sizeof(int) );
    int i, j, k;
    for (k = low; k <= high; k++) {
        c[k] = b[k];
    }
    for (i = low, j = mid + 1, k = i; i <= mid && j <= high; k++) {
        if (c[i] <= c[j]) {
            b[k] = c[i];
            i++;
        } else {
            b[k] = c[j];
            j++;
        }
    }
    if (i <= mid) {
        b[k++] = c[i++];
    }
    if (j <= high) {
        b[k++] = c[j++];
    }
    free(c);
}
void MergeSort(int *b, int low, int high) {
    int mid;
    if (low < high) {
        mid = (low + high) / 2;
        MergeSort(b, low, mid);
        MergeSort(b, mid + 1, high);
        Merge(b, low, mid, high);
    }
}

七：代码运行结果

如上所述，以上代码均为多种排序算法的伪代码实现，具体运行结果可根据实际编译和测试了解。