博客

C 排序算法

  • Post category:C

C 排序算法完整使用攻略

排序算法是计算机程序设计中常见的基本算法之一，可用于将一个无序的数据序列重新排列成一个有序的数据序列。C 语言是一门基础的编程语言，在排序算法应用上有较高的灵活性和自由度，下面是一些常用的 C 排序算法及其使用攻略。

冒泡排序（Bubble Sort）

冒泡排序是一种简单的排序算法，其思想是重复地遍历要排序的数列，每次遍历比较相邻两个元素，如果顺序错误则交换，直到没有可以交换的元素。具体实现过程如下：

void bubbleSort(int arr[], int n){
    for(int i=0; i<n-1; i++){
        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;
            }
        }
    }
}
  • arr[]: 待排序的整数数组
  • n: 数组长度

以下是一个使用冒泡排序对数组进行排序的程序示例：

#include <stdio.h>
int main(){
    int arr[] = {9, 4, 5, 1, 0, 3, 6, 7, 2, 8};
    int n = sizeof(arr)/sizeof(arr[0]);
    bubbleSort(arr, n);
    printf("Sorted array:");
    for(int i=0; i<n; i++){
        printf(" %d", arr[i]);
    }
    return 0;
}

输出结果为：

Sorted array: 0 1 2 3 4 5 6 7 8 9

快速排序（Quick Sort）

快速排序是一种高效的排序算法，其思想是选取一个基准元素，将其他元素分为两个子序列，小于基准的在左边，大于基准的在右边，然后递归的对左右子序列排序，最终得到有序数列。具体实现过程如下：

void quickSort(int arr[], int left, int right){
    if(left<right){
        int pivot = partition(arr, left, right);
        quickSort(arr, left, pivot-1);
        quickSort(arr, pivot+1, right);
    }
}
int partition(int arr[], int left, int right){
    int pivot = arr[right];
    int i = left-1;
    for(int j=left; j<=right-1; j++){
        if(arr[j] < pivot){
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i+1];
    arr[i+1] = arr[right];
    arr[right] = temp;
    return (i+1);
}
  • arr[]: 待排序的整数数组
  • left: 数组最左边元素下标
  • right: 数组最右边元素下标

以下是一个使用快速排序对数组进行排序的程序示例：

#include <stdio.h>
int main(){
    int arr[] = {9, 4, 5, 1, 0, 3, 6, 7, 2, 8};
    int n = sizeof(arr)/sizeof(arr[0]);
    quickSort(arr, 0, n-1);
    printf("Sorted array:");
    for(int i=0; i<n; i++){
        printf(" %d", arr[i]);
    }
    return 0;
}

输出结果为：

Sorted array: 0 1 2 3 4 5 6 7 8 9

总结

上述两种排序算法是 C 语言基础中较常用且容易实现的排序算法，但由于其时间复杂度并不是最优的，因此还可使用其他排序算法如堆排序、归并排序、插入排序等。在实际开发中，各种排序算法的适用场景也各有不同，需要根据实际需求进行选择。

Tags: