1、分割操作單向掃描

public class QuickSort {public int partition(int[] a, int left, int right) {int temp, pivot;//pivot存放主元int i, j;pivot = a[right];i = left;for (j = left; j < right; j++) {if (a[j] < pivot) {//交換值temp = a[i];a[i] = a[j];a[j] = temp;i++;}}a[right] = a[i];a[i] = pivot;return i;//把主元的下標(biāo)返回}public void quickSort(int[] a, int left, int right) {int center;if (left < right) {center = partition(a, left, right);quickSort(a, left, center - 1);//左半部分quickSort(a, center + 1, right);//右半部分}} }

2、分割操作雙向掃描

private int partition2(int[] a, int left, int right) {int i, j;int pivot = a[left];i = left + 1;j = right;while (true) {//向右掃描while (i <= j && a[i] <= pivot)i++;//向左掃描while (i <= j && a[j] >= pivot)j--;if (i >= j)break;//交換int temp = a[i];a[i] = a[j];a[j] = temp;}//把a[j]和主元交換a[left] = a[j];a[j] = pivot;return j;}

3、因為快速排序的最壞時間復(fù)雜度是O(n2)。例如有可能會出現(xiàn)一種極端的情況，每次分割的時候，主元左邊的元素個數(shù)都為0，而右邊都為n-1個。這個時候，就需要分割n次了。而每次分割整理的時間復(fù)雜度為O(n)，所以最壞的時間復(fù)雜度為O(n2)。而最好的情況就是每次分割都能夠從數(shù)組的中間分割了，這樣分割logn次就行了，此時的時間復(fù)雜度為O(nlogn)。而平均時間復(fù)雜度，則是假設(shè)每次主元等概率著落在數(shù)組的任意位置，最后算出來的時間復(fù)雜度為O(nlogn)，至于具體的計算過程，我就不展開了。

//隨機選取主元的方法，為了降低極端情況出現(xiàn)的可能性，我們可以隨機選取主元，而不是固定一個位置選取。 int random_partition(int[] arr, int left, int right) {i = random(left, right);//隨機選取一個位置//在把這個位置的元素與ar[left]交換swap(arr[i], arr[left]);return partition(arr, left, right); }

總結(jié)

以上是生活随笔為你收集整理的快速排序的实现及优化的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。