快速排序算法

作者: XZhongWen | 来源:发表于2018-06-03 18:41 被阅读0次

    快速排序算法

    基本思想

    快速排序是一类交换排序,它是对起泡排序的一种改进.它的基本思想是, 通过一趟排序将待排记录分割成独立的两个部分, 其中一部分记录的关键字均比另一部分的关键字小, 然后再分别对这两个部分继续进行快速排序, 以达到整个序列有序的目的.

    快速排序的工作过程

    1. 在数组中选择一个关键字作为枢纽(pivot)

      这里pivot的选择对快速排序算法的性能启关键性的影响
      当每次选中的pivot在执行完一趟快速排序后, 都能使数组中大致一半的记录在pivot的左边, 另一边在pivot的右边, 此时快速排序算法的执行效率最高, 时间复杂度为O(nlogn)
      当每次选中的pivot在执行完一趟快速排序后, 都使数组中除pivot外的所有记录都在pivot的一边时, 快速排序算法的执行效率最低, 时间复杂度为O( n^2 )

      选择pivot的常用方式
      选择待排数组的第一个数left和最后一个数right, center = (left + right) / 2, 这里的left, center, right为数组中记录的下标值; 选择center位置的记录为pivot

    2. 划分待排数组元素, 将小于pivot的记录放在pivot的左边, 大于pivot的记录放在pivot的右边

    3. 重复上述两个步骤, 直到每个划分中的记录个数小于2, 此时待排数组有序, 快速排序算法执行完毕

    这里以整型数组A[] = {49, 38, 65, 97, 76, 13, 27} 为例, 演示一趟快速排序算法的执行过程, 即对待排数组的划分过程

    选择38作为pivot, 此时数组A的初始状态如下


    pivot.png

    如果A[low] < pivot, low++
    如果A[high] > pivot, high--
    如果A[low] >= pivot, A[high] <= pivot, 交换A[low]与A[high]的位置


    partition.png

    快速排序算法实现

    /**
     选择pivot并将pivot放到right - 1位置
    
     @param A 待排数组
     @param left 左边序号
     @param right 右边序号
     */
    int Median3(ElementType A[], int left, int right) {
        int center = (left + right) / 2;
        if (A[left] > A[center]) {
            Swap(&A[left], &A[center]);
        }
        if (A[left] > A[right]) {
            Swap(&A[left], &A[right]);
        }
        if (A[center] < A[right]) {
            Swap(&A[center], &A[right]);
        }
        Swap(&A[center], &A[right - 1]);
        return A[right - 1];
    }
    
    /**
     快速排序
    
     @param A 待排数组
     @param left 左边序号
     @param right 右边序号
     */
    void QuickSort(ElementType A[], int left, int right) {
        int pivot = Median3(A, left, right);
        int i = left;
        int j = right - 1;
        for (; ; ) {
            while (A[++i] < pivot) {}
            while (A[--j] > pivot) {}
            if (i < j) {
                Swap(&A[i], &A[j]);
            } else {
                break;
            }
        }
        Swap(&A[i], &A[right - 1]);
        QuickSort(A, left, i - 1);
        QuickSort(A, i + 1, right);
    }
    

    相关文章

      网友评论

        本文标题:快速排序算法

        本文链接:https://www.haomeiwen.com/subject/vvtssftx.html