博客

C语言中如何进行排序和查找操作？

  • Post category:C

让我来为你详细讲解一下C语言中如何进行排序和查找操作。

排序操作

排序是对一组数据按照一定规则进行排列的操作。在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])
              swap(&arr[j], &arr[j+1]);
}

void swap(int *xp, int *yp)
{
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}

快速排序

快速排序是一种常用的排序算法，基本思想是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的元素都比另一部分的元素小，然后再按照这种方式分别对两部分的数据进行快速排序，递归进行下去，直到排列完成。

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 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 swap(int* a, int* b)
{
    int t = *a;
    *a = *b;
    *b = t;
}

查找操作

查找是在一组数据中查找特定元素的操作。在C语言中，常见的查找算法有线性查找、二分查找等。

线性查找

线性查找是一种简单的查找算法，从数据的第一个元素开始逐个查找，直到找到目标元素或遍历完整个数组。

int linearSearch(int arr[], int n, int x)
{
    int i;
    for (i = 0; i < n; i++)
    {
        if (arr[i] == x)
            return i;
    }
    return -1;
}

二分查找

二分查找是一种更高效的查找算法，前提是数据必须是有序的，基本思想是将数组从中间分成左右两个部分，如果目标元素小于中间值，则查找左半部分，否则查找右半部分，一直递归进行下去，直到找到目标元素或查找区间为空。

int binarySearch(int arr[], int l, int r, int x)
{
    while (l <= r)
    {
        int m = l + (r-l)/2;

        if (arr[m] == x)
            return m;

        if (arr[m] < x)
            l = m + 1;

        else
            r = m - 1;
    }

    return -1;
}

以上就是C语言中排序和查找的操作攻略，希望能对你有所帮助。

Tags: