快速排序算法原理及实现（单轴快速排序、三向切分快速排序、双轴快速排序） |
您所在的位置：网站首页 › 快速排序的原理 › 快速排序算法原理及实现（单轴快速排序、三向切分快速排序、双轴快速排序） |
|
欢迎探讨，如有错误敬请指正 如需转载，请注明出处http://www.cnblogs.com/nullzx/ 1. 单轴快速排序的基本原理快速排序的基本思想就是从一个数组中任意挑选一个元素（通常来说会选择最左边的元素）作为中轴元素，将剩下的元素以中轴元素作为比较的标准，将小于等于中轴元素的放到中轴元素的左边，将大于中轴元素的放到中轴元素的右边，然后以当前中轴元素的位置为界，将左半部分子数组和右半部分子数组看成两个新的数组，重复上述操作，直到子数组的元素个数小于等于1（因为一个元素的数组必定是有序的）。 以下的代码中会常常使用交换数组中两个元素值的Swap方法，其代码如下 public static void Swap(int[] A, int i, int j){ int tmp; tmp = A[i]; A[i] = A[j]; A[j] = tmp; } 2. 快速排序中元素切分的方式快速排序中最重要的就是步骤就是将小于等于中轴元素的放到中轴元素的左边，将大于中轴元素的放到中轴元素的右边，我们暂时把这个步骤定义为切分。而剩下的步骤就是进行递归而已，递归的边界条件为数组的元素个数小于等于1。以首元素作为中轴，看看常见的切分方式。 2.1 从两端扫描交换的方式基本思想，使用两个变量i和j，i指向首元素的元素下一个元素（最左边的首元素为中轴元素），j指向最后一个元素，我们从前往后找，直到找到一个比中轴元素大的，然后从后往前找，直到找到一个比中轴元素小的，然后交换这两个元素，直到这两个变量交错（i > j）（注意不是相遇 i == j，因为相遇的元素还未和中轴元素比较）。最后对左半数组和右半数组重复上述操作。 public static void QuickSort1(int[] A, int L, int R){ if(L < R){//递归的边界条件，当 L == R时数组的元素个数为1个 int pivot = A[L];//最左边的元素作为中轴，L表示left, R表示right int i = L+1, j = R; //当i == j时，i和j同时指向的元素还没有与中轴元素判断， //小于等于中轴元素，i++,大于中轴元素j--, //当循环结束时，一定有i = j+1, 且i指向的元素大于中轴，j指向的元素小于等于中轴 while(i pivot的情况,j继续向左扫描 j--; if(j < k){ break OUT_LOOP; } } if(A[j] == pivot){//A[j]==pivot的情况 Swap(A, k, j); k++; j--; }else{//A[j] pivot2，则交换最左边的元素和最右边的元素，已保证pivot1 = pivot1 && a[k] pivot2: 这个时候显然a[k]应该放到最右端大于pivot2的部分。但此时，我们不能直接将a[k]与j的下一个位置a[--j]交换（可以认为A[j]与pivot1和pivot2的大小关系在上一次j自右向左的扫描过程中就已经确定了，这样做主要是j首次扫描时避免pivot2参与其中），因为目前a[--j]和pivot1以及pivot2的关系未知，所以我们这个时候应该从j的下一个位置（--j）自右向左扫描。而a[--j]与pivot1和pivot2的关系可以继续分为三种情况讨论3.1）a[--j] > pivot2 j接着继续扫描 3.2）a[--j] >= pivot1且a[j] pivot2, pivot1 A[R]){ Swap(A, L, R); //保证pivot1 = pivot1 && A[k] pivot2){//j先增减，首次运行pivot2就不会发生改变 if(j = pivot1 && A[j] |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |