排序算法实现与比较的C语言实验

排序算法是计算机科学中的基础算法之一，对于算法的实现和比较也是非常重要的。下面是一些排序算法的C语言实现和比较的实验：

1. 冒泡排序(Bubble Sort)

冒泡排序是一种简单的排序算法，它重复地遍历数列，每次比较相邻的两个元素，如果它们的顺序错误就交换它们。

C语言实现：

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

2. 选择排序(Selection Sort)

选择排序是一种简单直观的排序算法，它的工作原理是每次从待排序的数据元素中选出最小(或最大)的一个元素存放到序列的起始位置，直到全部待排序的数据元素排完。

C语言实现：

void selectionSort(int arr[], int n) {
    int i, j, min;
    for (i = 0; i < n-1; i++) {
        min = i;
        for (j = i+1; j < n; j++) {
            if (arr[j] < arr[min]) {
                min = j;
            }
        }
        int temp = arr[i];
        arr[i] = arr[min];
        arr[min] = temp;
    }
}

3. 插入排序(Insertion Sort)

插入排序是一种简单直观的排序算法，它的基本操作是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据。

C语言实现：

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

4. 快速排序(Quick Sort)

快速排序是一种基于分治的排序算法，它通过递归地将数据集分成独立的两部分，其中一部分的所有数据都比另一部分的所有数据都要小，然后按照此方法对这两部分数据分别进行快速排序，整个过程可以递归进行，以达到整个数据集都有序的目的。

C语言实现：

void quickSort(int arr[], int left, int right) {
    if (left < right) {
        int i = left, j = right, pivot = arr[left];
        while (i < j) {
            while (i < j && arr[j] >= pivot) {
                j--;
            }
            if (i < j) {
                arr[i++] = arr[j];
            }
            while (i < j && arr[i] < pivot) {
                i++;
            }
            if (i < j) {
                arr[j--] = arr[i];
            }
        }
        arr[i] = pivot;
        quickSort(arr, left, i-1);
        quickSort(arr, i+1, right);
    }
}

5. 归并排序(Merge Sort)

归并排序是一种基于分治的排序算法，它将待排序的数据元素分成两个长度相等的子序列，对每个子序列分别进行排序，然后将两个有序子序列合并成一个有序序列。

C语言实现：

void merge(int arr[], int left, int mid, int right) {
    int i, j, k;
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int L[n1], R[n2];
    for (i = 0; i < n1; i++) {
        L[i] = arr[left+i];
    }
    for (j = 0; j < n2; j++) {
        R[j] = arr[mid+1+j];
    }
    i = 0;
    j = 0;
    k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k++] = L[i++];
        } else {
            arr[k++] = R[j++];
        }
    }
    while (i < n1) {
        arr[k++] = L[i++];
    }
    while (j < n2) {
        arr[k++] = R[j++];
    }
}

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid+1, right);
        merge(arr, left, mid, right);
    }
}

在实验中，可以将这些算法的实现放在一个C文件中，然后使用相同的数据集对它们进行排序，比较它们的时间复杂度和实际运行时间，以及对于大数据集时的优缺点。