利用递归算法进行快速排序。
工具/原料
javascript语言
方法/步骤
1、初始状态,设置基准值,将数组中的第一个值作为基准值,即数字6。
2、第一次循环,j找到小于6的值后,停止寻找,i找到大于6的值后,停止寻找。
3、将两者数值交换。
4、第二次循环,j找到小于6的值后,停止寻找,i找到大于6的值后,停止寻找。
5、两者数值交换。
6、第三次循环,j找到小于6的值后,停止寻找,i找到大于6的值后,停止寻找。
7、当j找到小于6的值后,停止寻找,i开始循谪藁钴碳环,寻找大于6的值,当i=j时,结束循环。将i的值与基准值交换。
8、此时,在基准值6的左侧均为小于6的值,右侧为大于6的值。再使用递归算法,将左右两边数组进行排序。
方法/步骤2
1、代码段(使用js语言)。functionquickSort(num,f筠续师诈rom,to){varfrom=from!租涫疼迟=undefined?from:0;//开始位置varto=to!=undefined?to:num.length-1;//结束位置vari=from;varj=to;varkey=num[from];//基准值vartemp;//临时变量,用于数字交换if(i>=j){returnnum;//递归出口}while(i<j){//外层循环,当i=j时,循环结束,完成一轮的数字交换//j的目标是寻找比基准值小的值,//故当num[j]的值大于基准值时,需要往左移动,即j--,////直到找到小于基准值的情况下退出循环,并记录下此时的j值。while(i<j&&num[j]>key){j--;}//i的目标是寻找比基准值大的值,//故当num[j]的值小于基准值时,需要往右移动,即i++,//直到找到大于基准值的情况下退出循环,并记录下此时的i值。while(i<j&&num[i]<=key){i++;}//将i与j的值交换if(i<j){temp=num[i];num[i]=num[j];num[j]=temp;}}//最后将i与基准值交换,完成第一轮的数字查找num[from]=num[i];num[i]=key;//使用递归算法,对数组下标从from~i-1的部分,//即小于基准值的左边部分进行排序。quickSortTwo(num,from,i-1);//使用递归算法,对数组下标从i+1~to的部分,//即小于基准值的右边部分进行排序。returnquickSortTwo(num,i+1,to);}//调用函数console.log(quickSort(arr));为了方便,截图如下。
2、注意点:to=to!=undefined?to:num.len壹执慵驾gth-1;函数开始时需要有棒瀹跏癞一个判断值是否为undefined的语句,不能直接写to=to?to:num.length-1,因为在函数执行的过程中,到递归语句时,可能会传入0,如果传入0,会将to赋值为num.length-1,导致函数运行不正确。while(i<j&&num[j]>key),该代码容易产生误解,容易写成num[j]<key,然后左移j--。returnquickSortTwo(num,i+1,to);写代码时容易漏掉最后的return,如果没有return,函数返回undefined。