首页 > 代码库 > 快速排序

快速排序

2024-08-29 06:33:43   220人阅读

      快排思想：在数据序列中选择一个值作为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(基准)值选用不恰当时，快排较慢。

 

快速排序


联系
我们