算法java快速排序的两种方法（单边循环、双边循环）
快速排序
1、平均时间复杂度是nlog2n，最坏时间复杂度n2
2、数据量较大时，优势非常明显
3、属于不稳定排序
快速排序的两种方法（单边循环、双边循环）
1、单边循环
package cn.itcast.algorithm.suanFa; /** * 快速排序____单边循环 */ import java.util.Arrays; public class MainS15 { public static void main(String[] args) { int[] a = {5, 3, 7, 2, 9, 8, 1, 4}; quick(a, 0, a.length -1); } //对quick进行递归 private static void quick(int[] a, int l, int h){ if (l >= h){ //区间里面只有一个或者没有元素的时候停止 return; } int p = partition(a, l, h); quick(a, l, p-1);//左边分区的范围确定 quick(a, p+1, h);//右边分区的范围确定 } private static int partition(int[] a, int l, int h) { int pv = a[h];//选择最右元素作为基准点元素 int i = l; for (int j = l;j < h;j++){ //j指针负责找到比基准点小的元素，找到则与i进行交换 if (a[j] < pv){ if (i != j) { swap(a, i, j); } i++; } } if (i != h) { swap(a, h, i); //最后基准点与i进行交换，i即为分区位置 } System.out.println(Arrays.toString(a)+" i = " + i); //返回值代表了基准点元素所在的正确索引，用它确定下一轮分区的边界 return i; } private static void swap(int[] a, int s, int i) { int temp = a[s]; a[s] = a[i]; a[i] = temp; } }
2、双边循环
package cn.itcast.algorithm.suanFa; import java.util.Arrays; /** * 快速排序____双边循环 */ public class MainS16 { public static void main(String[] args) { int[] a = {5, 3, 7, 2, 9, 8, 1, 4}; System.out.println(Arrays.toString(a)); quick(a, 0, a.length -1); } //对quick进行递归 private static void quick(int[] a, int l, int h){ if (l >= h){ //区间里面只有一个或者没有元素的时候停止 return; } int p = partition(a, l, h); quick(a, l, p-1);//左边分区的范围确定 quick(a, p+1, h);//右边分区的范围确定 } private static int partition(int[] a, int l, int h) { int pv = a[l];//选择最左元素作为基准点元素,必须先j后i的查找 int i = l; int j = h; while(i < j){ //j 从右找小的 //j 指针负责从右向左找比基准点小的元素 while(i < j && a[j] > pv){ j--; } //i 从左找大的 //i 指针负责从左向右找比基准点大的元素 while(i < j && a[j] <= pv){ i++; } //找到之后二者交换,直至i,j相交，循环停止 swap(a, i, j); } swap(a, l, j); System.out.println(Arrays.toString(a)+" j = " + j); return j; } private static void swap(int[] a, int s, int i) { int temp = a[s]; a[s] = a[i]; a[i] = temp; } }
