快速排序算法c++语言

快速排序是一种常用的排序算法，其基本思想是通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，然后再分别对这两部分记录继续进行排序，以达到整个序列有序的目的。以下是快速排序的C++代码实现：

void quickSort(int arr[], int left, int right) {
    if (left < right) {
        int i = left, j = right, pivot = arr[left];
        while (i < j) {
            while (i < j && arr[j] >= pivot) j--;
            if (i < j) arr[i++] = arr[j];
            while (i < j && arr[i] < pivot) i++;
            if (i < j) arr[j--] = arr[i];
        }
        arr[i] = pivot;
        quickSort(arr, left, i - 1);
        quickSort(arr, i + 1, right);
    }
}

相关问题

C++快速排序算法源码

下面是 C 语言实现快速排序算法的源码：

#include <stdio.h>

// 交换函数
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 分区函数
int partition(int arr[], int left, int right) {
    int pivot = arr[left];
    int i = left + 1;
    int j = right;

    while (i <= j) {
        while (i <= j && arr[i] <= pivot) {
            i++;
        }
        while (i <= j && arr[j] > pivot) {
            j--;
        }
        if (i < j) {
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[left], &arr[j]);
    return j;
}

// 快速排序函数
void quickSort(int arr[], int left, int right) {
    if (left < right) {
        int pivot_index = partition(arr, left, right);
        quickSort(arr, left, pivot_index - 1);
        quickSort(arr, pivot_index + 1, right);
    }
}

int main() {
    int arr[] = { 5, 2, 9, 1, 5, 6, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);

    quickSort(arr, 0, n - 1);

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

    return 0;
}

这段代码实现了快速排序算法，包括 swap 函数、partition 函数和 quickSort 函数。其中 swap 函数用于交换两个元素的值，partition 函数用于分区并返回基准元素的位置，quickSort 函数用于递归地对左右两个子序列进行快速排序。最后在 main 函数中测试了该算法的正确性。

写一份C++ 快速排序算法

### 回答1：
快速排序是一种分治算法，通过递归地交换数组元素来排序。这里是一份 C 语言的实现：

#include <stdio.h>

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

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 pivotIndex = partition(arr, low, high);

        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}

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

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");
    printArray(arr, n);
    return 0;
}

### 回答2：
快速排序是一种常用的排序算法，它通过选择一个基准元素将数组分为两部分，使得左边的元素都小于或等于基准元素，右边的元素都大于或等于基准元素。然后对两部分分别进行递归调用快速排序，直到排序完成。

以下是一个用C语言写的快速排序算法示例：

#include<stdio.h>

// 交换两个元素的位置
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 找到基准元素的正确位置，并返回该位置的索引
int partition(int array[], int low, int high) {
    int pivot = array[high];  // 选择最后一个元素作为基准
    int i = low - 1;

    for (int j = low; j < high; j++) {
        if (array[j] <= pivot) {
            i++;
            swap(&array[i], &array[j]);
        }
    }

    swap(&array[i + 1], &array[high]);
    return (i + 1);
}

// 快速排序递归函数
void quickSort(int array[], int low, int high) {
    if (low < high) {
        int pivotIndex = partition(array, low, high);  // 找到基准元素的正确位置

        quickSort(array, low, pivotIndex - 1);  // 对基准元素左边的部分进行递归排序
        quickSort(array, pivotIndex + 1, high);  // 对基准元素右边的部分进行递归排序
    }
}

// 打印数组
void printArray(int array[], int n) {
    for (int i = 0; i < n; i++)
        printf("%d ", array[i]);
    printf("\n");
}

int main() {
    int array[] = {64, 25, 12, 22, 11};
    int n = sizeof(array) / sizeof(array[0]);

    printf("原始数组：");
    printArray(array, n);

    quickSort(array, 0, n - 1);

    printf("排序后的数组：");
    printArray(array, n);

    return 0;
}

以上示例代码展示了一份用C语言写的快速排序算法。首先定义了两个辅助函数swap和partition，用于交换两个元素的位置和确定基准元素的正确位置。然后定义了快速排序的递归函数quickSort，利用递归思想实现了排序过程。最后，在main函数中初始化一个数组，调用quickSort进行排序，并打印排序前后的数组。

### 回答3：
快速排序（Quicksort）是一种分治的排序算法。它的基本思想是选择一个元素作为基准（通常选择第一个或最后一个元素），然后将比基准小的元素放在基准的左边，比基准大的元素放在基准的右边，最后递归地对基准左右两侧的子序列进行排序。

下面是一份用C语言实现的快速排序算法：

#include <stdio.h>

// 交换函数，用于交换两个元素的值
void swap(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

// 分割函数，选择基准并进行划分
int partition(int arr[], int low, int high) {
    int pivot = arr[low]; // 选择第一个元素为基准
    int i = low, j = high;

    while (i < j) {
        while (i < j && arr[j] > pivot)
            j--;
        if (i < j) {
            swap(&arr[i], &arr[j]);
            i++;
        }
        while (i < j && arr[i] < pivot)
            i++;
        if (i < j) {
            swap(&arr[i], &arr[j]);
            j--;
        }
    }

    return i; // 返回基准的位置
}

// 快速排序函数
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pivot = partition(arr, low, high);
        quickSort(arr, low, pivot - 1); // 对基准左侧进行排序
        quickSort(arr, pivot + 1, high); // 对基准右侧进行排序
    }
}

// 测试代码
int main() {
    int arr[] = {9, 6, 3, 8, 5, 2, 7, 4, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    quickSort(arr, 0, n - 1);

    printf("排序结果：");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");

    return 0;
}

该快速排序算法的时间复杂度为O(nlogn)，空间复杂度为O(logn)，是一种效率较高的排序算法。