C语言排序方法(冒泡,选择,插入,归并,快速)

下面是关于C语言排序方法冒泡、选择、插入、归并、快速的详细攻略：

冒泡排序

冒泡排序是一种最简单的排序算法，它的核心思想是从左到右依次比较相邻的两个元素，如果前一个元素大于后一个元素，就交换它们的位置，这样一遍比较后，最大的元素就会被“冒泡”到最右边。然后再对剩余的元素重复同样的操作，这样一直迭代直到整个序列排序完成。

下面是标准的C语言冒泡排序代码示例：

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

上面代码的时间复杂度为$O(n^2)$。下面是一个例子：

排序前： 21 34 11 5 4 2
排序后： 2 4 5 11 21 34

选择排序

选择排序的核心思想是每次从未排定的序列中选择最小的元素，将其和未排定序列的最左边的元素交换位置，这样每一次就使得未排定序列的长度减少1。选择排序的时间复杂度和冒泡排序一样，也是$O(n^2)$。

下面是标准的C语言选择排序代码示例：

void selection_sort(int arr[], int len){
    int i, j, min_idx, temp;
    for (i = 0; i < len - 1; i++){
        min_idx = i;
        for (j = i + 1; j < len; j++){
            if (arr[j] < arr[min_idx]){
                min_idx = j;
            }
        }
        temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;
    }
}

下面是一个例子：

排序前： 21 34 11 5 4 2
排序后： 2 4 5 11 21 34

插入排序

插入排序的核心思想是将未排序的元素一个一个地插入到已排序的序列中，插入元素的时候需要保证插入后的序列仍然保持有序。插入排序的时间复杂度也是$O(n^2)$。

下面是标准的C语言插入排序代码示例：

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

下面是一个例子：

排序前： 21 34 11 5 4 2
排序后： 2 4 5 11 21 34

归并排序

归并排序的核心思想是将原序列通过逐层的细分、合并操作，分割到某一层时，其中的子序列长度为1，则每个子序列都是有序的，然后将相邻的子序列合并，直到整个序列排序完成。归并排序的时间复杂度是$O(nlogn)$，比前面的排序算法要快得多。

下面是标准的C语言归并排序代码示例：

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

void merge_sort(int arr[], int l, int r){
    if (l < r){
        int m = l + (r-l)/2;
        merge_sort(arr, l, m);
        merge_sort(arr, m+1, r);
        merge(arr, l, m, r);
    }
}

下面是一个例子：

排序前： 21 34 11 5 4 2
排序后： 2 4 5 11 21 34

快速排序

快速排序的核心思想是基于分治的思想，在每一次操作时随机选择一个元素作为比较基准，然后将序列中其余的元素根据比较基准的大小分为两个子序列，分别递归地对它们进行排序，最后将它们连接起来即可。快速排序的时间复杂度是$O(nlogn)$。

下面是标准的C语言快速排序代码示例：

int partition(int arr[], int low, int high){
    int pivot = arr[high];
    int i = low - 1;
    int j, temp;
    for (j = low; j <= high-1; j++){
        if (arr[j] < pivot){
            i++;
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    temp = arr[i+1];
    arr[i+1] = arr[high];
    arr[high] = temp;
    return i + 1;
}

void quicksort(int arr[], int low, int high){
    if (low < high){
        int pi = partition(arr, low, high);
        quicksort(arr, low, pi - 1);
        quicksort(arr, pi + 1, high);
    }
}

下面是一个例子：

排序前： 21 34 11 5 4 2
排序后： 2 4 5 11 21 34

以上就是C语言常用的几种排序方法的详细讲解，希望对你有所帮助。