电子商务网站建设前期,北京工商登记服务平台,宝塔虚拟主机,网站建设后台功能一、快速排序#xff08;Quicksort#xff09;思想设要排序的数组是A[0]……A[N-1]#xff0c;首先任意选取一个数据#xff08;通常选用数组的第一个数#xff09;作为关键数据#xff0c;然后将所有比它小的数都放到它前面#xff0c;所有比它大的数都放到它后面…一、快速排序Quicksort思想设要排序的数组是A[0]……A[N-1]首先任意选取一个数据通常选用数组的第一个数作为关键数据然后将所有比它小的数都放到它前面所有比它大的数都放到它后面这个过程称为一趟快速排序。值得注意的是快速排序不是一种稳定的排序算法也就是说多个相同的值的相对位置也许会在算法结束时产生变动。一趟快速排序的算法是1设置两个变量i、j排序开始的时候i0jN-12以第一个数组元素作为关键数据赋值给key即keyA[0]3从j开始向前搜索即由后开始向前搜索(j--)找到第一个小于key的值A[j]将A[j]和A[i]互换4从i开始向后搜索即由前开始向后搜索(i)找到第一个大于key的A[i]将A[i]和A[j]互换5重复第3、4步直到ij (3,4步中没找到符合条件的值即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值使得jj-1ii1直至找到为止。找到符合条件的值进行交换的时候i j指针位置不变。另外ij这一过程一定正好是i或j-完成的时候此时令循环结束。二、算法实现1递归算法public static void quickSort(int[] data, int low, int high) {//无需排序if (low high) {return;}int mid sortUnit(data, low, high);//一趟排序quickSort(data, low, mid - 1);//左边排序quickSort(data, mid 1, high);//右边排序}public static int sortUnit(int[] data, int low, int high) {int key data[low]; //保存比较数据//进行一趟排序处理while (low high) { //从尾部寻找比key小的数据while (key data[high]lowhigh) {high--;}data[low] data[high];//交换保存小的数据//从首部寻找比key大的数据while (key data[low]lowhigh) {low;}data[high] data[low];//交换保存大的数据}data[low] key;//回填比较数据return high;} 2非递归算法 public static void quickSort(int[] data) {if(data.length2)return;StackInteger stacknew Stack(); //保存队列栈//保存起始队列stack.push(0);stack.push(data.length-1);//额外空间int low; int high;int mid;while (!stack.isEmpty()) { highstack.pop();lowstack.pop();mid sortUnit(data, low, high);//一趟排序//左边排序队列保存if (lowmid - 1) {stack.push(low);stack.push(mid-1);}//右边排序队列保存if (mid 1 high) {stack.push(mid1);stack.push(high);}}}public static int sortUnit(int[] data, int low, int high) {int key data[low]; //保存比较数据//进行一趟排序处理while (low high) { //从尾部寻找比key小的数据while (key data[high]lowhigh) {high--;}data[low] data[high];//交换保存小的数据//从首部寻找比key大的数据while (key data[low]lowhigh) {low;}data[high] data[low];//交换保存大的数据}data[low] key;//回填比较数据return high;}
