快速排序的实现及优化

比眉伴天荒 2023-07-01 08:32 7阅读 0赞

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;//把主元的下标返回
        }
    
        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、因为快速排序的最坏时间复杂度是O(n2)。例如有可能会出现一种极端的情况，每次分割的时候，主元左边的元素个数都为0，而右边都为n-1个。这个时候，就需要分割n次了。而每次分割整理的时间复杂度为O(n)，所以最坏的时间复杂度为O(n2)。而最好的情况就是每次分割都能够从数组的中间分割了，这样分割logn次就行了，此时的时间复杂度为O(nlogn)。而平均时间复杂度，则是假设每次主元等概率着落在数组的任意位置，最后算出来的时间复杂度为O(nlogn)，至于具体的计算过程，我就不展开了。

//随机选取主元的方法，为了降低极端情况出现的可能性，我们可以随机选取主元，而不是固定一个位置选取。
    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);
    }