哪些网站是做设计的/百度识图在线识别网页版

本文记录快速排序算法的一个精美实现，关于其中的一些优化或者思路请参考如下资料：

快速排序中的分割算法的解析与应用

http://www.cnblogs.com/hapjin/p/5518922.html

http://blog.csdn.net/hapjin/article/details/49785477

http://blog.csdn.net/hapjin/article/details/49201341

 

public class QuickSort{//分割数组,将数组分成两部分. 一部分比pivot(枢轴元素)大,另一部分比pivot小private static int parition(int[] arr, int left, int right){int pivot = media3(arr, left, right);int i = left;int j = right - 1;//注意 ,在 media3()中 arr[right-1]就是 pivot//应对特殊情况下的数组,比如数组长度 小于3if(i >= j)return i;for(;;){while(arr[++i] < pivot){}while(arr[--j] > pivot){}if(i < j)swap(arr, i, j);elsebreak;}swap(arr, i, right-1);//restore pivot 将枢轴元素放置到合适位置:arr左边元素都比pivot小,右边都比pivot大return i;// 返回 pivot的 索引
    }//三数取中,用在快排中随机选择枢轴元素时private static int media3(int[] arr, int left, int right){if(arr.length == 1)return arr[0];if(left == right)return arr[left];int center = (left + right) / 2;//找出三个数中的最小值放到 arr[left]if(arr[center] < arr[left])swap(arr, left, center);if(arr[right] < arr[left])swap(arr, left, right);//将 中间那个数放到 arr[media]if(arr[center] > arr[right])swap(arr, center, right);swap(arr, center, right-1);//尽量将大的元素放到右边--将privot放到右边, 可简化 分割操作(partition).return arr[right-1];//返回中间大小的那个数
    }private static void swap(int[] arr, int left, int right){int tmp = arr[left];arr[left] = arr[right];arr[right] = tmp;}public static void quickSort(int[] arr){quickSort(arr, 0, arr.length - 1);}private static void quickSort(int[] arr, int left, int right){if(left < right){int pivot_index = parition(arr, left, right);quickSort(arr, left, pivot_index - 1);quickSort(arr, pivot_index + 1, right);}}public static void main(String[] args) {    int[] arr2 = {1,0,-1};quickSort(arr2);for (int i : arr2) {System.out.print(i + " ");}}
}

 

不解释了，直接参考上面给出的参考链接即可。