C语言实现数字从小到大排序的四种算法详解

创作时间:

作者:

@小白创作中心

C语言实现数字从小到大排序的四种算法详解

引用

来源

https://docs.pingcode.com/baike/1095323

要在C语言中实现数字从小到大排序，可以使用多种排序算法，如冒泡排序、选择排序、插入排序、快速排序等。在这些算法中，冒泡排序、选择排序、插入排序是相对简单且易于理解的初学者友好算法，而快速排序则是高级且效率较高的算法。下面我们将详细介绍每种算法，并通过代码示例来说明其实现方法。

一、冒泡排序

冒泡排序是一种简单的排序算法，其核心思想是通过重复遍历要排序的数组，每次比较相邻的两个元素，如果它们的顺序错误就交换它们的位置。这个过程重复进行，直到整个数组有序。

实现步骤

从数组的第一个元素开始，比较相邻的两个元素。
如果第一个元素大于第二个元素，就交换它们的位置。
对每一对相邻元素重复以上步骤，直到最后一对元素。
重复以上步骤，直到无需再进行交换，即数组已经有序。

冒泡排序代码示例

#include <stdio.h>

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

int main() {  
    int arr[] = {64, 34, 25, 12, 22, 11, 90};  
    int n = sizeof(arr)/sizeof(arr[0]);  
    bubbleSort(arr, n);  
    printf("Sorted array: \n");  
    for (int i=0; i < n; i++) {  
        printf("%d ", arr[i]);  
    }  
    return 0;  
}

二、选择排序

选择排序是一种直观的排序算法，其核心思想是每次从未排序的部分中选出最小的元素，并将其放到已排序部分的末尾。

实现步骤

找到数组中最小的元素，把它和数组的第一个元素交换位置。
再从剩下的未排序元素中找到最小的元素，把它和数组的第二个元素交换位置。
重复以上步骤，直到数组排序完成。

选择排序代码示例

#include <stdio.h>

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

int main() {  
    int arr[] = {64, 25, 12, 22, 11};  
    int n = sizeof(arr)/sizeof(arr[0]);  
    selectionSort(arr, n);  
    printf("Sorted array: \n");  
    for (int i=0; i < n; i++) {  
        printf("%d ", arr[i]);  
    }  
    return 0;  
}

三、插入排序

插入排序是一种简单直观的排序算法，其核心思想是将数组分为已排序和未排序两部分，每次从未排序部分取出一个元素，将其插入到已排序部分的正确位置。

实现步骤

从第一个元素开始，该元素可以认为已经被排序。
取出下一个元素，在已排序的元素序列中从后向前扫描。
如果已排序的元素大于新元素，将已排序的元素向后移动一位。
重复步骤3，直到找到已排序的元素小于或等于新元素的位置。
将新元素插入到该位置。
重复步骤2-5，直到所有元素均排序完毕。

插入排序代码示例

#include <stdio.h>

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

int main() {  
    int arr[] = {12, 11, 13, 5, 6};  
    int n = sizeof(arr)/sizeof(arr[0]);  
    insertionSort(arr, n);  
    printf("Sorted array: \n");  
    for (int i=0; i < n; i++) {  
        printf("%d ", arr[i]);  
    }  
    return 0;  
}

四、快速排序

快速排序是一种分治算法，其核心思想是选择一个基准元素，将数组分成两部分，使得左边部分所有元素都小于基准元素，右边部分所有元素都大于基准元素，然后递归地对两部分进行排序。

实现步骤

选择一个基准元素（pivot）。
重新排列数组，所有比基准元素小的元素放在基准元素的左边，所有比基准元素大的元素放在基准元素的右边。
递归地对基准元素左边和右边的子数组进行快速排序。

快速排序代码示例

#include <stdio.h>

void swap(int* a, int* b) {  
    int t = *a;  
    *a = *b;  
    *b = t;  
}  

int partition(int arr[], int low, int high) {  
    int pivot = arr[high];  
    int i = (low - 1);  
    for (int j = low; j <= high - 1; j++) {  
        if (arr[j] < pivot) {  
            i++;  
            swap(&arr[i], &arr[j]);  
        }  
    }  
    swap(&arr[i + 1], &arr[high]);  
    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);  
    }  
}  

int main() {  
    int arr[] = {10, 7, 8, 9, 1, 5};  
    int n = sizeof(arr)/sizeof(arr[0]);  
    quickSort(arr, 0, n-1);  
    printf("Sorted array: \n");  
    for (int i=0; i < n; i++) {  
        printf("%d ", arr[i]);  
    }  
    return 0;  
}