c语言排序方法有哪几种

一. 排序方法的介绍

排序是计算机程序中常用的操作，对于处理大量数据有着重要的作用，也是算法和数据结构中的重要内容。C语言是一种支持各种排序算法的编程语言，下面将会介绍几种常用的排序方法。

二. 内部排序和外部排序

1.内部排序

内部排序是指在排序过程中，所有需要排序的数据都可以全部存放在内存中，这种排序称为内部排序。内部排序有很多种算法，例如：

插入排序

冒泡排序

选择排序

快速排序

归并排序

堆排序

其中插入排序，冒泡排序和选择排序是比较简单的排序算法，而快速排序，归并排序和堆排序则是更高效的算法。

2.外部排序

当内存无法容纳排序需要的数据时，就必须使用外部排序。外部排序是指将数据分成多个部分，每个部分在内存中排序，然后将已排序的子序列合并成有序的结果。外部排序的使用是因为内存大小的限制，需要排序的数据太大，无法一次性加载进内存中。

三. 常用的排序算法

1.插入排序

插入排序是一种简单直观的排序算法。其基本思想是将待排序的数据元素按照一定的顺序逐个插入到有序的子序列中。插入排序具体步骤如下：

从第一个元素开始，该元素可以认为已经被排序

取出下一个元素，在已经排序的元素序列中从后向前扫描

如果该元素（已排序）大于新元素，将该元素移到下一位置

重复步骤3，直到找到已排序的元素小于或者等于新元素的位置

将新元素插入到该位置后

重复步骤2~5

代码如下：

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

在插入排序中，每次比较需要交换两个元素的位置时，都需要进行多次赋值操作，因此在对大规模数据进行排序时可能会变的比较慢。

2.冒泡排序

冒泡排序是一种基础的排序算法，它重复地走访过要排序的数列，一次比较两个元素，将较大的元素交换到右侧。具体过程如下：

从数列的左侧开始比较相邻的两个元素；

如果第一个元素比第二个元素大，就交换这两个元素的位置；

否则，将两个元素保持原来的位置不变；

重复上述步骤，直到到达数列的右侧；

再从数列的左侧开始，重复上述步骤，直到有序。

代码如下：

void bubble_sort(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        bool flag = false;
        for (int 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;
                flag = true;
            }
        }
        if (flag == false) break;
    }
}

冒泡排序每一轮比较会将数列中最大或最小的数“冒泡”到最上面或者最下面，因此代码最后的地方需要添加flag优化。若上一轮排序已经将数列中的数排好了，则不需要再进行比较排序操作。

3.选择排序

选择排序是一种简单直观的排序算法，其基本思想是每次选择当前未排序序列中的最小元素，把它放在已排序序列的末尾。具体过程如下：

从待排数组中找出最小的元素

将最小元素与数组的第一个元素进行交换位置

对剩下的元素进行重复上述步骤，直到排成有序数列。

代码如下：

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

选择排序每一轮选择数列中最小的数与数列中的第一个元素交换，因此比较次数较少，适合于排序数量较小的数列。

4.快速排序

快速排序是一种基于分治的排序算法，其基本思想是通过一趟之后的操作，将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分小，分别对这两部分再次进行排序，以达到整个序列有序的目的。具体过程如下：

设定一个分界值，将数据分成两部分

重新排序序列，所有比分界值小的元素摆放在左边，所有比分界值大的元素摆放在右边

递归地对左部分进行快速排序，递归地对右部分进行快速排序，直到整个序列有序。

代码如下：

void quickSort(int arr[], int low, int high) {
    int i = low, j = high;
    int temp;
    int pivot = arr[(low + high) / 2];
    while (i <= j) {
        while (arr[i] < pivot) i++;
        while (arr[j] > pivot) j--;
        if (i <= j) {
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
    }
    if (low < j) quickSort(arr, low, j);
    if (i < high) quickSort(arr, i, high);
}

快速排序的实现非常简单，但是其过程较为复杂，需要多次递归和交换操作，在数据量极大时导致性能下降。

5.归并排序

归并排序是一种将两个或两个以上的有序表合并成一个新的有序表的算法，它利用分治的思想，首先将待排序的序列拆分成一个个子问题，然后对这些子问题进行递归求解，最后再将所有的有序子序列归并成一个有序序列。具体过程如下：

将序列每相邻两个数进行合并，也就是初始的每个数自成一个有序序列，然后两两合并。

若此时序列中的小序列并未全部合并，仍需合并剩余的小序列，合并后仍得到一系列的有序序列。

重复步骤2，直到所有元素都在同一个有序序列中。

代码如下：

void merge(int arr[], int low, int mid, int high) {
    int temp[high - low + 1];
    int i = low, j = mid + 1, k = 0;
    while (i <= mid && j <= high) {
        if (arr[i] < arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    while (j <= high) {
        temp[k++] = arr[j++];
    }
    for (int i = 0; i < k; i++) {
        arr[low + i] = temp[i];
    }
}
void mergeSort(int arr[], int low, int high) {
    if (low < high) {
        int mid = (low + high) / 2;
        mergeSort(arr, low, mid);
        mergeSort(arr, mid + 1, high);
        merge(arr, low, mid, high);
    }
}

归并排序的运行时间与其他排序算法相比，其优势在于始终保持O(n log n)的复杂度，并且对于大数据量的排序传统的实现方法难以保证时间效率。

6.堆排序

堆排序是一种树形选择排序算法，它的实质是建立完全二叉树，通过对堆的调整来实现排序，堆的根节点是最大（小）的数。具体过程如下：

将待排序的序列构造成一个大顶堆

将堆顶元素与末尾元素交换，并将最后一个元素从堆中删除；

对剩余的堆进行调整，使其成为一个新的堆。

重复2、3步，直到堆的大小为1。

代码如下：

void adjustHeap(int arr[], int i, int n) {
    int temp = arr[i];
    for (int j = 2 * i + 1; j < n; j = 2 * j + 1) {
        if (j < n - 1 && arr[j] < arr[j + 1]) {
            j++;
        }
        if (temp > arr[j]) {
            break;
        } else {
            arr[i] = arr[j];
            i = j;
        }
    }
    arr[i] = temp;
}
void heapSort(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--) {
        adjustHeap(arr, i, n);
    }
    for (int i = n - 1; i > 0; i--) {
        int temp = arr[i];
        arr[i] = arr[0];
        arr[0] = temp;
        adjustHeap(arr, 0, i);
    }
}

堆排序的优点是平均性能较好，最坏情况下时间复杂度也保证在O(n log n)级别，但是缺点是不稳定。

四. 算法的比较

下表列出了各种排序算法的时间复杂度和空间复杂度:

在时间复杂度方面，快速排序的平均时间复杂度是最快的，而归并排序具有稳定的时间复杂度，都是比较常用的排序算法。

总的来说，不同的排序算法适合处理不同的问题，程序员需要在实际问题中，选择最合适的排序算法。

五. 总结

本文介绍了常用的排序算法，包括插入排序、冒泡排序、选择排序、快速排序、归并排序和堆排序。这些排序算法是计算机程序中常用的操作，对于处理大量数据有着重要的作用，也是算法和数据结构中的重要内容。

程序员在选择排序算法时，需要考虑时间复杂度、空间复杂度、稳定性等因素，以及具体的运行环境。通过合理选择排序算法，可以提高程序的