快速排序

基本介绍图示代码

基本介绍

是对冒泡排序的一种改进 通过一趟排序将要排序的数据分割成独立的两部分， 其中一部分的所有数据都比另外一部分的所有数据都要小， 然后再按此方法对这两部分数据分别进行快速排序， 整个排序过程可以递归进行，以此达到整个数据变成有序序列

图示

代码

public class QuickSort { public static void main(String[] args) { int[] arr = {-9,78,0,23,-567,70}; quickSort(arr,0,arr.length-1); System.out.println("排序：" + Arrays.toString(arr)); } public static void quickSort(int[] arr,int left,int right){ int l = left; int r = right; int pivot = arr[left]; //参照数 int temp = 0; while (l < r){ //找到 左边大于等于 参照数 的下标 while (arr[l] < pivot){ l += 1; } //找到 右边小于等于 参照数 的下标 while (arr[r] > pivot){ r -= 1; } //左右指针相遇，退出 if (l >= r){ break; } //交换 temp = arr[l]; arr[l] = arr[r]; arr[r] = temp; //如果交换完后，发现这个arr[l]==pivot值相等r--，前移 if (arr[l] == pivot){ r -= 1; } ///如果交换完后，发现这个arr[r]==pivot值相等l++，后移 if (arr[r] == pivot){ l += 1; } //如果l==r,必须l++,r--,否则为出现栈溢出 if (l == r){ l += 1; r -= 1; } //向右递归 if (left < r){ quickSort(arr,left,r); } //向左递归 if (right > l){ quickSort(arr,l,right); } } } }

【结果】