网站建设寻求,金华网站建设解决方案,网站开发流程管理,angularjs 网站模版快速排序作为一种高效的排序算法被广泛应用#xff0c;SUN的JDK中的Arrays.sort 方法用的就是快排。 快排采用了经典的分治思想#xff08;divide and conquer#xff09;#xff1a; Divide#xff1a;选取一个基元X#xff08;一般选取数组第一个元素#xff09;…快速排序作为一种高效的排序算法被广泛应用SUN的JDK中的Arrays.sort 方法用的就是快排。 快排采用了经典的分治思想divide and conquer Divide选取一个基元X一般选取数组第一个元素通过某种分区操作partitioning将数组划分为两个部分左半部分小于等于X右半部分大于等于X。 Conquer: 左右两个子数组递归地调用Divide过程。 Combine快排作为就地排序算法in place sort不需要任何合并操作 可以看出快排的核心部分就是划分过程partitioning,下面以一个实例来详细解释如何划分数组图取自于《算法导论》 初始化选取基元P2就是数组首元素。i1,ji12 (数组下标以1开头) 循环不变量2~i之间的元素都小于或等于Pi1~j之间的元素都大于或等于P 循环过程j从2到n考察j位置的元素如果大于等于P就继续循环。如果小于P就将j位置的元素不应该出现在i1~j这个区间和i1位置(交换之后仍在i1~j区间)的元素交换位置同时将i1.这样就维持了循环不变量见上述循环不变量说明。直到jn完成最后一次循环操作。 要注意的是在完成循环后还需要将i位置的元素和数组首元素交换以满足我们最先设定的要求对应图中的第i步。 细心的读者可能会想到另一种更直白的分区方法即将基元取出存在另一相同大小数组中遇到比基元小的元素就存储在数组左半部分遇到比基元大的元素就存储在数组右半部分。这样的操作复杂度也是线性的,即Theta(n)。但是空间复杂度提高了一倍。这也是快排就地排序的优势所在。 最后附上快排的java代码实现 public class QuickSort {private static void QuickSort(int[] array,int start,int end){if(startend){int keyarray[start];//初始化保存基元int istart,j;//初始化i,jfor(jstart1;jend;j){if(array[j]key)//如果此处元素小于基元则把此元素和i1处元素交换并将i加1如大于或等于基元则继续循环{int temparray[j];array[j]array[i1];array[i1]temp;i;}}array[start]array[i];//交换i处元素和基元array[i]key;QuickSort(array, start, i-1);//递归调用QuickSort(array, i1, end);}}public static void main(String[] args){int[] arraynew int[]{11,213,134,44,77,78,23,43};QuickSort(array, 0, array.length-1);for(int i0;iarray.length;i){System.out.println((i1)th:array[i]);}}
} 以下是运行结果 转载于:https://www.cnblogs.com/developerY/p/3163997.html
