快速排序 数组+递归实现
快速排序 数组+递归实现
问题描述：
给定N个元素的数组arr[N]，需要把数组arr中的数排成非递减的次序并输出.
基本思想：
1. 用一个自定义的分割方法split()选取用来作分割的元素(也称为partition主元)，最简单的分割方法是选定待排范围的第一个数为partition主元，一趟快排完成后，主元e是数组arr中第i个元素，主元e左边的元素都不大于e，主元e右边的元素都大于e； 2. 使用两个跟踪变量(forward和backward)，递归地对从i到backward采用快速排序方法quickSort()，并递归地对从forward到i采用快速排序方法quickSort()； 3. backward从后向前递减，forward从前向后递增。forward从前往后扫，当出现第一个比主元大的数，将该数放进arr[i]; backward从后向前扫，当出现第一个比主元小的数时，将该数放进arr[i]. 当forward与backward相等时，停止...
注： 数组arr=L区间(主元e左边的部分)+主元e+U(未排序部分)+R(主元e右边的部分)，其中区间U是区间L与区间R夹住的部分，每次递归都是让U缩小，直到为0，此时快排结束...
代码：
#include<iostream>
#include<cstdio>
using namespace std;
class Solution{
public:
void quickSort(int arr[], int forward, int backward)
{
int part_pos; // 记录每次调用快排 quickSort()后主元e的位置
if(forward>=backward) return;
// int split(int[], int, int); // 如果是在C语言中，此处需要声明一下，这里放在了class里面，不能进行声明
part_pos=split(arr, forward, backward);
// cout<<"The postion of the partition elemen is: "<<part_pos<<endl;
for(int idx=0;idx<9;idx++)
{
printf("%d ",arr[idx]);
}
printf("\n");
quickSort(arr, forward, part_pos-1); // 递归地给主元e左侧元素排序
quickSort(arr, part_pos+1, backward); // 递归地给主元e右侧元素排序
}
int split(int arr[], int forward, int backward) // 分割并返回分割主元的位置
{
int part_val=arr[forward]; // 用来作分割的元素(也称为partition主元)的值，以第一个数为分割基准
while(true)
{
while(forward<backward && arr[backward]>part_val) backward--;
if(forward>=backward) break;
arr[forward++]=arr[backward];
while(forward<backward && arr[forward]<=part_val) forward++;
if(forward>=backward) break;
arr[backward--]=arr[forward];
}
arr[backward]=part_val;
return backward;
}
};
int main()
{
Solution sol;
int arr[]={12,3,6,18,7,15,10,56,4};
sol.quickSort(arr,0,8);
printf("The final result is:\n");
for(int idx=0;idx<9;idx++)
{
printf("%d ",arr[idx]);
}
printf("\n");
return 0;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2016年04月17日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读