方法一:
<pre code_snippet_id="1828553" snippet_file_name="blog_20160813_1_7365625" name="code" class="cpp">/****************************
*@time 2016/08/12 21:58
*@author dzq
*@description 快速排序(分治、挖坑)
************************************/
#include<cstdio>
#include<iostream>
using namespace std;
void quick_sort(int ori_Nums[],int start_Index,int end_Index)
{
if(start_Index>=end_Index) return;
int smaller_Num_Index=end_Index;
int bigger_Num_Index=start_Index;
int flag=ori_Nums[start_Index];
while(smaller_Num_Index>bigger_Num_Index)
{
while(smaller_Num_Index>bigger_Num_Index&&ori_Nums[smaller_Num_Index]>=flag) smaller_Num_Index--;//从后往前找比flag小的数字
while(smaller_Num_Index>bigger_Num_Index&&ori_Nums[bigger_Num_Index]<=flag) bigger_Num_Index++;//从前往后找比flag大的数
//*此处会出现三种情况:
// *1、比flag大的数和比flag小的数都找到了,交换
// *2、都没有找到,那么smaller_Num_Index最终会等于0
// *3、只找到了比flag小的数
if(smaller_Num_Index>bigger_Num_Index)
{
int tmp=ori_Nums[smaller_Num_Index];
ori_Nums[smaller_Num_Index]=ori_Nums[bigger_Num_Index];
ori_Nums[bigger_Num_Index]=tmp;
}
}
//*如是第一种情况,最终要讲flag放置在smaller_Num_Index=bigger_Num_Index的地方,同时将这个地方的数放置在flag的地方
// *如是第二种情况,两句都可没有
//*如是第三种情况,只用在这里可以交换较小的数与flag
ori_Nums[0]= ori_Nums[smaller_Num_Index];
ori_Nums[smaller_Num_Index]=flag;//放置flag
quick_sort(ori_Nums,0,smaller_Num_Index);//将flag左侧分治排序(包括flag)
quick_sort(ori_Nums+smaller_Num_Index+1,0,end_Index-smaller_Num_Index-1);//将flag右侧分治排序
}
int main()
{
int ori_Nums[]={3,2,1,4,4};
quick_sort(ori_Nums,0,4);
for(int i=0;i<5;i++)
{
printf("%d",ori_Nums[i]);
}
}
算法分析:
1、smaller_Num_Index>bigger_Num_Index&&ori_Nums[smaller_Num_Index]>=flag
如果数组中的数全部相当,若将等于号去掉,则会无限递归下去
有了等号,smaller_Num_Index最终将会为0,递归时quick_sort(ori_Nums,0,smaller_Num_Index)中smaller_Num_Index=0, quick_sort(ori_Nums+smaller_Num_Index+1,0,end_Index-smaller_Num_Index-1);ori_Nums+smaller_Num_Index+1最终数组的长度会变为0.
方法二:
/**************************************************************
*@time 2016/08/28 16:35
*@place DHU.13.5005
***************************************************************/
#include<cstdio>
void quick_sort(int *ori_Nums,int begin_Index,int end_Index)
{
if(end_Index-begin_Index<=0) return;
int lit=begin_Index;
int rit=end_Index;
int flag=ori_Nums[begin_Index];
while(lit<rit)
{
while(ori_Nums[rit]>=flag&&lit<rit) rit--;//从后往前找比flag小的数字
while(ori_Nums[lit]<=flag&&lit<rit) lit++;//从前往后找比flag大的数
if(lit<rit)//比flag大的数和小的数都找到了,则交换
{
int tmp=ori_Nums[rit];
ori_Nums[rit]=ori_Nums[lit];
ori_Nums[lit]=tmp;
}
//处理结束时必定为以下两个情景之一
else if(rit!=begin_Index)//只找到了比flag小的数,则交换flag与小的数
{
ori_Nums[begin_Index]=ori_Nums[rit];
ori_Nums[rit]=flag;
}
//都没有找到,则证明已排好,不处理
}
quick_sort(ori_Nums,begin_Index,rit);//将flag左侧分治排序(包括flag)
quick_sort(ori_Nums,rit+1,end_Index);//将flag右侧分治排序
}
int main()
{
int ori_Nums[]={3,2,1,4,4};
myQsort(ori_Nums,0,5);
for(int i=0;i<5;i++)
{
printf("%d\n",ori_Nums[i]);
}
}
转载请注明原文地址: https://ju.6miu.com/read-1296110.html