首页
后端开发
C
C语言六大经典排序算法实现及详解

C语言六大经典排序算法实现及详解

18 次浏览 0 条评论
c
c

C语言实现六大经典排序算法，包含冒泡排序、快速排序、选择排序、堆排序、简单插入排序和希尔排序，并附有详细的代码注释。以下为各算法的实现与解释：

1. 冒泡排序 (Bubble Sort)

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n xss=removed> arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

冒泡排序通过不断比较相邻元素并交换，逐步将最大值“冒”至数组末尾。时间复杂度为 $O(n^2)$。

2. 快速排序 (Quick Sort)

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);
    for (int j = low; j < high xss=removed xss=removed xss=removed xss=removed xss=removed xss=removed xss=removed>

快速排序通过分区递归地排序左右部分。平均时间复杂度为 $O(n log n)$，最坏情况下退化为 $O(n^2)$。

3. 选择排序 (Selection Sort)

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n xss=removed xss=removed xss=removed xss=removed xss=removed xss=removed>

选择排序每次从未排序部分中选出最小值放在开头，时间复杂度为 $O(n^2)$。

4. 堆排序 (Heap Sort)

void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    if (left < n> arr[largest])
        largest = left;
    if (right < n> arr[largest])
        largest = right;
    if (largest != i) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
    for (int i = n - 1; i >= 0; i--) {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        heapify(arr, i, 0);
    }
}

堆排序通过构建最大堆再交换堆顶与末尾元素来排序，时间复杂度为 $O(n log n)$。

5. 简单插入排序 (Insertion Sort)

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n xss=removed xss=removed>= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

简单插入排序逐一插入并排至有序区域，时间复杂度为 $O(n^2)$。

6. 希尔排序 (Shell Sort)

void shellSort(int arr[], int n) {
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n xss=removed xss=removed>= gap && arr[j - gap] > temp; j -= gap)
                arr[j] = arr[j - gap];
            arr[j] = temp;
        }
    }
}

希尔排序为插入排序的改进，通过间隔排序提高效率，时间复杂度为 $O(n^{3/2})$ 至 $O(n^2)$。

每种排序算法在实际应用中各有优劣，应根据数据量及特点选择合适的算法。
c 文件大小：6.15KB