车陂手机网站建设报价,数字广东网络建设有限公司,外贸网络推广网,健康义乌app目录
快速排序基础
优化1#xff1a;随机取样
优化2#xff1a;三数取中
优化3#xff1a;插入排序
总结#xff1a; 快速排序#xff08;Quick Sort#xff09;是一种高效的排序算法#xff0c;它的平均时间复杂度为O(n log n)。然而#xff0c;在某些情况下随机取样
优化2三数取中
优化3插入排序
总结 快速排序Quick Sort是一种高效的排序算法它的平均时间复杂度为O(n log n)。然而在某些情况下快速排序可能表现不佳特别是在输入数据近乎有序或包含大量重复元素时。为了解决这些问题我们可以对快速排序进行一些优化。本文将介绍Java语言中如何使用随机取样、三数取中和插入排序等优化技巧来提高快速排序的性能。
快速排序基础
快速排序的基本思想是选择一个基准元素pivot将数组分成两个子数组小于基准的元素放在左边大于基准的元素放在右边然后对这两个子数组递归地进行排序。
public static void quickSort(int[] arr){quick(arr,0,arr.length-1);
}private static void quick(int[] arr,int start,int end){if (startend){return;}int pivotpartition(arr,start,end);quick(arr,start,pivot-1);quick(arr,pivot1,end);
}private static int partition(int[] arr,int left,int right ){int tmparr[left];while (leftright){while (leftrightarr[right]tmp){right--;}arr[left]arr[right];while (leftrightarr[left]tmp){left;}arr[right]arr[left];}arr[left]tmp;return left;
}
优化1随机取样
在快速排序中如果每次选择的基准元素都是数组的最左边或最右边那么在输入数据接近有序时性能会下降。为了解决这个问题我们可以随机选择基准元素。
private static void quick(int[] arr,int start,int end){if (startend){return;}int randomIndex getRandomIndex(start, end);swap(arr, start, randomIndex);int pivotpartition(arr,start,end);quick(arr,start,pivot-1);quick(arr,pivot1,end);
}
public int getRandomIndex(int low, int high) {Random rand new Random();return rand.nextInt(high - low 1) low;
} 随机选择基准元素可以减小快速排序在特定输入下的性能波动。 优化2三数取中
另一个性能优化的方法是选择中位数作为基准元素。这可以避免最坏情况下的快速排序性能下降。
private static void quick(int[] arr,int start,int end){if (startend){return;}//三数取中法int indexmidThree(arr,start,end);int tmparr[start];arr[start]arr[index];arr[index]tmp;int pivotpartition1(arr,start,end);quick(arr,start,pivot-1);quick(arr,pivot1,end);
}
private static int midThree(int[] arr,int left,int right){int mid(leftright)/2;if (arr[left]right){if (arr[mid]arr[left]){return left;}else if (arr[mid]arr[right]){return right;}else {return mid;}}else {//arr[left]rightif (arr[mid]arr[right]){return right;}else if (arr[mid]arr[left]){return left;}else {return mid;}}
} 三数取中的方法可以有效地避免快速排序的最坏情况提高了算法的稳定性。 优化3插入排序
对于小规模的数组快速排序的递归开销可能会变得显著。在这种情况下使用插入排序可以提高性能。
private static void quick(int[] arr,int start,int end){if (startend){return;}if(end-start114){//插入排序insertSort2(arr, start, end);return;}//三数取中法int indexmidThree(arr,start,end);int tmparr[start];arr[start]arr[index];arr[index]tmp;int pivotpartition(arr,start,end);quick(arr,start,pivot-1);quick(arr,pivot1,end);}public static void insertSort2(int[] arr,int start,int end){for (int i start; i end; i) {int temparr[i];int ji-1;while (j0arr[j]temp){arr[j1]arr[j];j--;}arr[j1]temp;}}private static int midThree(int[] arr,int left,int right){int mid(leftright)/2;if (arr[left]right){if (arr[mid]arr[left]){return left;}else if (arr[mid]arr[right]){return right;}else {return mid;}}else {//arr[left]rightif (arr[mid]arr[right]){return right;}else if (arr[mid]arr[left]){return left;}else {return mid;}}}private static int partition(int[] arr,int left,int right ){int tmparr[left];while (leftright){while (leftrightarr[right]tmp){right--;}arr[left]arr[right];while (leftrightarr[left]tmp){left;}arr[right]arr[left];}arr[left]tmp;return left;} 注意代码里的小于14长度是我自己规定的各位友友可以自己定义小数组的长度~~ 插入排序在小规模数组上的性能通常比快速排序更好~~
总结
在Java中优化快速排序的方法包括随机取样、三数取中和插入排序。这些优化可以改善快速排序在各种输入情况下的性能表现使其成为一种强大而高效的排序算法。通过合理地选择这些优化技巧可以根据实际需求来提高算法的性能。喜欢的友友可以关注一下博主噢
