【数据结构】排序算法——快速排序
快速排排序是效率非常高的排序算法之一。
我们取最后一个元素5为基准值key
size_t Pation1(int *arr,int left,int right)
{
size_t begin = left;
size_t end = right - 1;
int key = arr[end];
while (begin < end)
{
while (begin < end && arr[begin] <= key)
begin++;
while (begin < end && arr[end] >= key)
end--;
if (begin < end)
swap(arr[begin],arr[end]);
}
if (begin != right-1)// 1 2 4 5 6
swap(arr[begin],arr[right-1]);
return begin;
}
void QuickSort(int *arr,int right)
{
if (left < right)
{
size_t div = Pation1(arr,left,right);
QuickSort(arr,div);
QuickSort(arr,div + 1,right);
}
}
第二种方法:挖坑法
此方法的实现代码如下: size_t Pation2(int *arr,size_t left,size_t right)
{
size_t begin = left;
size_t end = right - 1;
int key = arr[end];
while (begin < end)
{
while (begin < end && arr[begin] <= key)
begin++;
if (begin < end)
arr[end--] = arr[begin];
while (begin < end && arr[end] >= key)
end--;
if (begin < end)
arr[begin++] = arr[end];
}
if (begin != right-1)
arr[begin] = key;//1 2 3 4 5 6
return begin;
}
void QuickSort(int *arr,int right)
{
if (left < right)
{
size_t div = Pation2(arr,right);
}
}
第三种方法:追赶法
如下图所示: size_t Pation3(int *arr,size_t left,size_t right)
{
int index = GetMid(arr,left,right);
if (index != right - 1)
swap(arr[index],arr[right - 1]);
int key = arr[right - 1];
int cur = left;
int pre = cur - 1;
while (cur < right)
{
if (arr[cur] < key && ++pre != cur)
swap(arr[pre],arr[cur]);
cur++;
}
if (++pre != right)
swap(arr[pre],arr[right-1]);
return pre;
}
void QuickSort(int *arr,int left,int right)
{
if (left < right)
{
size_t div = Pation3(arr,right);
QuickSort(arr,right);
}
}
以上实现的快速排序是递归的,递归也是可以转换成循环,我们利用循环+栈来实现,非递归的快排。 #include <stack>
void QuickSort(int *arr,size_t size)
{
int left = 0;
int right = size;
stack<int> s;
s.push(right);
s.push(left);
while (!s.empty())
{
left = s.top();
s.pop();
right = s.top();
s.pop();
if (left < right)
{
size_t div = Pation3(arr,right);
s.push(div);//保存基准值左边数据的边界
s.push(left);
s.push(right);//保存基准值右边的数据的边界
s.push(div + 1);
}
}
}
优化 快速排序时间复杂度一般为 size_t GetMid(int *arr,size_t right)
{
size_t mid = left + ((right - left) >> 1);
if (arr[left] < arr[right-1])
{
if (arr[left] > arr[mid])
return left;
else if (arr[right - 1] < arr[mid])
return right - 1;
else
return mid;
}
else
{
if (arr[left] < arr[mid])
return left;
else if (arr[right - 1] > arr[mid])
return right - 1;
else
return mid;
}
} (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |