快速排序
思路:快速排序每次都是定位一个元素在数组中的绝对位置,简单说就是一个元素,在排好序后他的位置是一定的(当然快排是不稳定的),你每次选定一个元素,然后定位其排好序后的位置,再把这个元素从数组中去掉,就绪递归定位其他元素。最好的情况下就是每次选的元素都在最中间,这样就递归次数就少了(nlog2n),最坏情况就是每次都选在俩端(n^2)。
代码:
// 递归 每次找出标准值的位置 然后排除它 继续递归其他元素public static void quickSort(int[] arr,int start,int end) { if(arr == null || arr.length < 1) { return; } // 递归退出的标志 if (start >= end) { return; } // 标准值 int standard = findStandard(arr, start, end); // 左边递归 quickSort(arr,start,standard - 1); // 右边递归 quickSort(arr,standard + 1,end);
}public static int findStandard(int[] arr,int start,int end) { int left = start; int right = end; // 这里就随意一点啦选第一个作为标准值 int standard = arr[start]; while (left < right) { // 在左边寻找一个比标志值大的 while (left <= right && standard >= arr[left]) {left++;} // 在右边寻找一个比标准值小的 while (left <= right && standard <= arr[right]) {right--;} // 交换它们 if (left < right) { swap(arr,left,right); } } // 定位到标准值后 交换 swap(arr,start,right); // 返回 return right;}public static void swap(int [] a,int i,int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp;}
总结:利用这种寻找标准值的方法可用到其他算法中去比如要求使数组中的元素奇数在前偶数在后等。