C++实现快速排序算法 |21xrx.com

C++实现快速排序算法

2023-07-06 06:14:18 深夜i -- --

C++ 快速排序算法实现

快速排序算法是一种常用的排序算法，其特点是速度快且效率高。快速排序算法的实现可以使用C++语言来完成，具体步骤如下。

首先，需要定义一个函数来实现快速排序。函数名可以取为quickSort()，其参数是待排序的数组和数组的长度。在函数中，需要先进行递归判断，如果数组长度小于等于1，则不需要进行排序，直接返回即可。

若数组长度大于1，则需要进行排序。快速排序算法的核心是分治思想。具体步骤如下：

1. 选择一个元素作为基准值，一般选择第一个或最后一个元素；

2. 将数组分成两个部分，一部分是小于基准值的元素，另一部分是大于基准值的元素；

3. 对分出来的两部分元素分别递归进行快速排序。

在函数中，可以采用以下代码实现：

void quickSort(int arr[], int left, int right){

if(left >= right) return;

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);

}

在函数中，变量left和right分别代表数组的左右边界。在代码中，首先定义了变量i和j，分别指向数组的左右端点，在while循环中，将j向左移动，找到第一个小于基准值的元素，然后将其与i位置的元素交换。接着i向右移动，找到第一个大于等于基准值的元素，将其与j位置的元素交换。最后，将基准值放置到i的位置。

递归排序左右两部分的数组，直到所有的子数组都有序。

在调用函数时，需要传入待排序的数组和数组的长度。可以采用以下代码实现：

int main(){

int arr[] = {5, 3, 1, 4, 2};

int len = sizeof(arr) / sizeof(arr[0]);

quickSort(arr, 0, len - 1);

for(int i = 0; i < len; i++){

cout << arr[i] << " ";

}

cout << endl;

return 0;

}

运行代码，输出结果为1 2 3 4 5，即为排序后的数组。

总体来说，C++实现快速排序算法较为简单，其实现方式也可以应用于其他编程语言。快速排序算法是一种十分实用的排序算法，在实际开发中，可以大量地应用到数组排序、查找等领域。

上一篇: idea打包java可执行jar包

下一篇: C++程序设计：通讯录管理系统

评论区

()

相似文章