package com.txq.test; /*** quicksort,三方面改進：①三數中值選擇樞紐元②容量小的時候使用插入排序③重復元素的處理* @author XueQiang Tong* @date 2017/10/25*/ public class QS {public void quicksort(int []arr,int low,int high){int first = low;int last = high;int left = low;int right = high;int leftLen = 0;int rightLen = 0;//當分割后的容量較小時，使用插入排序，提高性能if(high - low + 1 <= 10){InsertSort(arr,low,high);return;}int key = SelectPivotMedianOfThree(arr,low,high);while(low < high){while(high > low && arr[high] >= key){if(arr[high] == key){//重復元素處理策略：分割過程中把他們放在數組兩端，遞歸調用時掠過他們，提高性能swap(arr,high,right);right --;rightLen ++;}high --;}arr[low] = arr[high];//交換while(high > low && arr[low] <= key){if(arr[low] == key){swap(arr,low,left);left ++;leftLen ++;}low ++;}arr[high] = arr[low];//交換}arr[low] = key;//此時總是low = high,把key放在此位置，一次迭代完成，進入下次遞歸調用//接下來，把重復元素存儲到key的周圍int i = low - 1;int j = first;while(j < left && arr[i] != key){swap(arr,j,i);i --;j ++;}i = low + 1;j = last;while(j > right && arr[i] != key){swap(arr,j,i);i ++;j --;}quicksort(arr,first,low - leftLen - 1);quicksort(arr,low + rightLen + 1,last);}/*** low,mid,high,對三個數排序，arr[mid] <= arr[low] <= arr[high],取arr[low]作為樞紐元* @param arr* @param low* @param high* @return*/private int SelectPivotMedianOfThree(int[] arr, int low, int high) {int mid = low + ((high - low) >> 1);if(arr[mid] > arr[high]){swap(arr,mid,high);}if(arr[low] > arr[high]){swap(arr,low,high);}if(arr[low] < arr[mid]){swap(arr,low,mid);}return arr[low];}public void swap(int arr[],int i, int j) {int tmp;tmp = arr[i];arr[i] = arr[j];arr[j] = tmp; }/*** 插入排序* @param arr*/private void InsertSort(int[] arr,int low,int high) {int i,j;int n = high - low + 1;int target;for(i = low+1;i < low+n;i++){j = i;target = arr[i];while(j > low && target < arr[j-1]){arr[j] = arr[j-1];j--;}arr[j] = target;} } }

?

轉載于:https://www.cnblogs.com/txq157/p/7728236.html

總結

以上是生活随笔為你收集整理的快速排序的改进的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。