针对一无序序列(自定义),采用快速排序算法,实现排序
时间: 2023-07-08 11:47:01 浏览: 131
好的,针对一无序序列,我来告诉你如何使用快速排序算法进行排序。首先,我们需要了解快速排序算法的基本思想:
快速排序是一种分治策略的排序算法,基本思路是:选定一个基准数,将比基准数小的数全部放在基准数的左边,比基准数大的数全部放在基准数的右边,然后再递归地对左右两个子序列进行排序,直到整个序列有序为止。
接下来,我们可以根据这个思路写出快速排序算法的代码实现:
```
void quickSort(int arr[], int left, int right) {
if (left >= right) {
return;
}
int i = left, j = right;
int pivot = arr[(left + right) / 2]; // 选取基准数
while (i <= j) {
while (arr[i] < pivot) {
i++;
}
while (arr[j] > pivot) {
j--;
}
if (i <= j) {
swap(arr[i], arr[j]);
i++;
j--;
}
}
quickSort(arr, left, j); // 递归排序左子序列
quickSort(arr, i, right); // 递归排序右子序列
}
```
这里的 arr 表示待排序的数组,left 和 right 分别表示当前排序区间的左右边界。在算法中,我们先选取基准数 pivot,然后用双指针 i 和 j 分别从左右两端向中间扫描,如果左边的数小于 pivot,就继续向右移动 i 指针;如果右边的数大于 pivot,就继续向左移动 j 指针;如果 i 指针指向的数大于等于 pivot,且 j 指针指向的数小于等于 pivot,就交换 i 和 j 指针所指向的数。这样一趟下来,就能够将基准数放到它最终的位置上,同时也将序列分成了两个子序列,通过递归地对左右两个子序列进行排序,最终实现了对整个序列的排序。
最后,我们可以在程序中调用 quickSort 函数对序列进行排序,如下所示:
```
int main() {
int arr[] = {5, 3, 8, 4, 2, 7, 1, 6};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}
```
这里的 arr 数组即为待排序的数组,n 表示数组的长度,我们将调用 quickSort 函数对它进行排序,最终输出有序的数组。
阅读全文