java实现快速排序

快速排序在排序算法中，平均情况下时间复杂度是O(nlog₂n),基本思想是:首先选择一个轴值，将待排序记录划分成独立的两部分，左侧记录的关键码均小于或等于轴值，右侧记录的关键码总大于等于轴值，然后分别对这两部分重复上述过程，直到整个序列有序，java代码实现如下：

package algorithm; /*  * @author pardy  * @describe 快速排序  * @param arrSort  * 待排序数组  * @param first  * 左侧下标  * @param end  * 右侧下标  */ public class quickSort { //一次划分 public static int partition(int[] arrSort,int first,int end){ int i = first; int j = end; while(i<j){ while(i<j&&arrSort[i]<=arrSort[j]){ j--; //右侧扫描 } if(i<j){ int temp = arrSort[i]; //设置temp用于交换两个数 arrSort[i]=arrSort[j]; arrSort[j]=temp; i++; } while(i<j&&arrSort[i]<=arrSort[j]){ i++; } if(i<j){ int temp = arrSort[i]; //设置temp用于交换两个数 arrSort[i]=arrSort[j]; arrSort[j]=temp; j--; } } return i; } //快速排序 public static void sort(int[] arrSort,int first,int end){ //数组长度大于0 if(arrSort.length>0){ if(first<end){ int pivot = partition(arrSort, first, end);//一次划分，获取轴值 sort(arrSort,first,pivot-1);//递归对左侧序列进行快速排序 sort(arrSort,pivot+1,end);//递归对右侧序列进行快速排序 } } } public static void main(String[] args) { int[] arrSort={2,6,7,8,1}; sort(arrSort,0,arrSort.length-1); System.out.print("快速排序结果："); for (int i : arrSort) { System.out.print(i+" "); } } }