快速排序

    xiaoxiao2025-02-05  8

    方法一: <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
    最新回复(0)