博客

C程序 快速排序

  • Post category:C

我来为您详细讲解“C程序 快速排序”的完整使用攻略。

一、什么是快速排序

快速排序是一种常见的排序算法，其思想是将一个待排序的序列（如一个数组）分成两个子序列，其中一个序列元素均小于另一个序列，然后递归排序这两个序列，最后合并成一个有序的序列。通过每次分割子序列，快速排序的时间复杂度为O(nlogn)。

二、快速排序的实现

以下是快速排序的C程序实现：

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

        quicksort(arr, low, j - 1);
        quicksort(arr, j + 1, high);
    }
}

三、快速排序的使用攻略

使用快速排序需要遵循以下步骤：

  1. 定义一个待排序的序列，例如：

c
int arr[] = {10, 12, 5, 3, 7, 8, 9, 2, 15};

  1. 调用快速排序算法对序列进行排序，例如：

c
quicksort(arr, 0, 8);

其中，第一个参数为待排序的序列，第二个参数为序列中最小元素的下标，第三个参数为序列中最大元素的下标。

  1. 输出排序后的序列，例如：

c
for (int i = 0; i < 9; i++) {
printf("%d ", arr[i]);
}

结果为：2 3 5 7 8 9 10 12 15

接下来，我将通过两个示例说明快速排序的使用：

示例一

有一个长度为10的数组，要求对其中的元素进行从小到大的排序，代码如下：

#include <stdio.h>

void quicksort(int arr[], int low, int high);

int main() {
    int arr[] = {10, 12, 5, 3, 7, 8, 9, 2, 15, 1};
    int n = 10;

    quicksort(arr, 0, n - 1);

    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

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

        quicksort(arr, low, j - 1);
        quicksort(arr, j + 1, high);
    }
}

输出结果为：1 2 3 5 7 8 9 10 12 15

示例二

有一个字符串数组，要求对其中的元素进行按字典序从小到大的排序，代码如下：

#include <stdio.h>
#include <string.h>

void quicksort(char arr[][20], int low, int high);

int main() {
    char arr[][20] = {"hello", "world", "C", "programming", "language"};
    int n = 5;

    quicksort(arr, 0, n - 1);

    for (int i = 0; i < n; i++) {
        printf("%s ", arr[i]);
    }
    printf("\n");

    return 0;
}

void quicksort(char arr[][20], int low, int high) {
    int i, j;
    char pivot[20], temp[20];
    if (low < high) {
        strcpy(pivot, arr[low]);
        i = low;
        j = high;
        while (i < j) {
            while (strcmp(arr[i], pivot) <= 0 && i <= high)
                i++;
            while (strcmp(arr[j], pivot) > 0 && j >= low)
                j--;
            if (i < j) {
                strcpy(temp, arr[i]);
                strcpy(arr[i], arr[j]);
                strcpy(arr[j], temp);
            }
        }
        strcpy(temp, arr[j]);
        strcpy(arr[j], arr[low]);
        strcpy(arr[low], temp);

        quicksort(arr, low, j - 1);
        quicksort(arr, j + 1, high);
    }
}

输出结果为：C hello language programming world

以上就是快速排序的C程序实现和使用攻略，希望能对您有所帮助。

Tags: