北京营销推广网站建设,ip动态地址做网站,专业h5网站建设教程,筋郑州做网站快速排序算法
#xff08;1#xff09;概念#xff1a;快速排序是指通过一趟排序将要排序的数据分割成独立的两部分#xff0c;其中一部分的所有数据都比另外一部分的所有数据都要小#xff0c;然后再按此方法对这两部分数据分别进行快速排序。整个排序过程可以递归进行1概念快速排序是指通过一趟排序将要排序的数据分割成独立的两部分其中一部分的所有数据都比另外一部分的所有数据都要小然后再按此方法对这两部分数据分别进行快速排序。整个排序过程可以递归进行以此达到整个数据变成有序序列。
2快速排序的的过程简图
选择一个关键值作为基准值。比基准值小的都在左边序列一般是无序的比基准值大的都在右边一般是无序的。 示例代码
/*** 快速排序** param arr 需要排序的数组* param start 数组的最小索引 0* param end 数组的最大索引 arr.length - 1* return 排序好的数组*/
public static int[] quickSort(int arr[], int start, int end) {int pivot arr[start];int i start;int j end;while (i j) {while ((i j) (arr[j] pivot)) {j--;}while ((i j) (arr[i] pivot)) {i;}if ((arr[i] arr[j]) (i j)) {i;} else {int temp arr[i];arr[i] arr[j];arr[j] temp;}}if (i - 1 start) arr quickSort(arr, start, i - 1);if (j 1 end) arr quickSort(arr, j 1, end);return (arr);
}示例代码2
/*** 快速排序无返回值* param a 需要排序的数组* param low 数组的最小索引 0* param high 数组的最大索引 arr.length - 1*/
public static void quickSort2(int[] a, int low, int high) {int start low;int end high;int key a[low];while (end start) {//从后往前比较while (end start a[end] key)//如果没有比关键值小的比较下一个直到有比关键值小的交换位置然后又从前往后比较end--;if (a[end] key) {int temp a[end];a[end] a[start];a[start] temp;}//从前往后比较while (end start a[start] key)//如果没有比关键值大的比较下一个直到有比关键值大的交换位置start;if (a[start] key) {int temp a[start];a[start] a[end];a[end] temp;}//此时第一次循环比较结束关键值的位置已经确定了。左边的值都比关键值小右边的值都比关键值大但是两边的顺序还有可能是不一样的进行下面的递归调用}//递归if (start low) quickSort2(a, low, start - 1);//左边序列。第一个索引位置到关键值索引-1if (end high) quickSort2(a, end 1, high);//右边序列。从关键值索引1 到最后一个
}
