内部排序—快速排序

浅浅的花香味﹌ 2022-06-14 03:48 168阅读 0赞

快速排序的基本思想是：通过一趟排序将待排序的记录划分成两个部分，其中一部分记录的关键字均不大于另一部分记录的关键字，然后再分别对这两部分记录继续进行快速排序，以达到整个序列有序。

用一维数组存储记录，一趟快速排序的具体做法是：设置两个指针i和j,他们的初始值分别指向第一个记录和最后一个记录。设置一个枢轴记录（通常为第一个记录）的关键字为pivotkey,则首先从j所指的位置向前搜索，找到第一个关键字小于pivotkey的记录与枢轴记录互相交换，然后从i所指的位置起向后搜索，找到第一个关键字大于pivotkey的记录与枢轴记录互相交替，重复这两步直到i等于j时为止。

快速排序是不稳定的排序算法，其平均时间复杂度为 O(nlogn)，空间复杂度O(logn)。若初始记录序列按关键字有序或基本有序，算法的时间复杂度则退化为O(n2)。

///  /// 快速排序 /// 思想：先从数列中取出一个数作为基准数。 /// 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。 /// 再对左右区间重复第二步，直到各区间只有一个数。 /// 
    /// 
    /// 
    /// 
    /// 
       
    private void QuickSort(int[] arrData, int low, int high)
    {
        if (low < high)
        {
            //将中间的这个数和第一个数交换
            int i = low, j = high;
            int key = arrData[low];
            while (i < j)
            {
                while (i < j && arrData[j] >= key) // 从右向左找第一个小于x的数
                    j--;
                if (i < j)
                    arrData[i++] = arrData[j];
    
                while (i < j && arrData[i] < key) // 从左向右找第一个大于等于x的数
                    i++;
                if (i < j)
                    arrData[j--] = arrData[i];
            }
            arrData[i] = key;
            QuickSort(arrData, low, i - 1); // 递归调用 
            QuickSort(arrData, i + 1, high);
        }
    }