首页 > 代码库 > 快速排序

快速排序

      快排思想:在数据序列中选择一个值作为key(基准)值,每趟从数据序列的两端开始交替进行,将小于key的元素交换到序列前端,将大于key的元素交换到序列后端,介于两者之间的位置则成为key的最终位置,同时,序列被划分为两个子序列,在用同样的方法分别对两个子序列进行排序,直到子序列的长度为1,则完成排序。

例   10  18  4  15  6  12  48  9  

第一步: 令key=10,begin=0,end=7;序列从后到前查找比key的值小的元素,交换位置,然后 begin++;

此时序列: 9 18 4 15 6 12 48 10   key=10,begin=1 ,所对应的值为18;

第二步:序列以 begin开始从前往后查找比key值大的元素,交换位置,然后end--;

此时序列: 9 10 4 15 6 12 48 18    key=10, end=6,所对应的值为48;

.....直到满足begin>=end的时候结束第一次快排

第一次快排的结果为:9  6  4  10  15  12  48  18   此时begin=end=3;

 

具体代码如下:

public static void quickSort(int[] array, int begin, int end) {
        if (begin < end) {
            int temp = 0;
            int i = begin;
            int j = end;
            int key = array[i];
            while (i != j) {
                while (i < j && key <= array[j]) {
                    j--;
                }
                if (i < j) {
                    temp = array[j];
                    array[j] = array[i];
                    array[i++] = temp;
                }
                while (i < j && key >= array[i]) {
                    i++;
                }
                if (i < j) {
                    temp = array[i];
                    array[i] = array[j];
                    array[j--] = temp;
                }
            }
            array[i] = key;//基准到达最终位置,从基准分成两部分
            for (int a = 0; a <= array.length - 1; a++)
                System.out.print(array[a] + "  ");
            System.out.println(" ");
            quickSort(array, begin, i - 1);//前半部分
            quickSort(array, j + 1, end);//后半部分
        
        }
    }

代码优化:取中间的数据作为基准key

public static void quicksort(int[] array, int begin, int end) {
        if (begin >= end) {
            return;
        }
        int key = array[(begin + end) / 2];//取中间值作为key
        int i = begin;
        int j = end;
        while (i <= j) {
            if (array[i] < key && i <= j) {
                i++;
            }
            if (array[j] > key && i <= j) {
                j--;
            }
            int temp = 0;
            temp = array[j];
            array[j] = array[i];
            array[i] = temp;
            i++;
            j--;
        }

        for (int a = 0; a < array.length; a++) {

            System.out.print(array[a] + " ");
        }
        quicksort(array, begin, j);
        quicksort(array, i, end);
    }

快排算法分析:

  不稳定算法,最好情况空间复杂度为O(log2n),最坏情况O(n),平均空间复杂度为O(log2n),

  当数据较大且数据序列随机排列时,适用快排,当数据较小,或key(基准)值选用不恰当时,快排较慢。

 

快速排序