29.快速排序

编程语言 > CSharp > CSharp进阶 > CSharp进阶语法知识 排序算法 编程语言 CSharp CSharp进阶 CSharp进阶语法知识
发布时间 :
字数:2k 阅读 : 评论:
  1. 29.排序-快速排序
    1. 29.1 知识点
      1. 快速排序基本原理
      2. 代码实现
        1. class语句块类 主函数外
        2. 主函数内
      3. 总结
    2. 29.2 知识点代码

29.排序-快速排序

29.1 知识点

快速排序基本原理

  • 口诀：

    • 选取基准，产生左右标识。
    • 左右比基准，满足则换位。
    • 排完一次，基准定位。
    • 左右递归，直到有序。

  • 通俗理解：

    • 传入要排序的数组和要排序的左索引和右索引，用来初始化左右标识（整个数组要排序的话，左右标识分别为0和数组长度；递归到后面可能只有中间一段要排序）。
    • 每轮目标：确定基准的最终位置。
    • 基准首先和右标识所在的元素比较，比他大，右标识就-1继续比；比他小，就把右标识所在的元素复制到当前左标识所在的位置上，左标识+1，然后切换到和左标识所在的元素比较；以此类推，直到左右标识相等，就是当前基准要放的位置。
    • 然后从基准切一刀，分成两个序列，递归地进行上面的操作。

代码实现

class语句块类 主函数外

// 第一步：申明用于快速排序的函数
/// <summary>
/// 快速排序函数
/// </summary>
/// <param name="array">要排序的数组</param>
/// <param name="leftBoundary">左边界</param>
/// <param name="rightBoundary">右边界</param>
public static void QuickSort(int[] array, int leftBoundary, int rightBoundary)
{
    // 递归函数结束条件
    if (leftBoundary >= rightBoundary) return;

    // 声明临时变量，记录基准值，左游标，右游标
    int tempValue, tempLeftBoundary, tempRightBoundary;
    tempValue = array[leftBoundary]; // 基准值，相当于把左标识元素存起来了
    tempLeftBoundary = leftBoundary;
    tempRightBoundary = rightBoundary;

    // 核心交换逻辑
    while (tempLeftBoundary != tempRightBoundary)
    {
        // 比较位置交换

        // 从右边开始比较，看值有没有资格放到表示的右侧
        while (tempLeftBoundary < tempRightBoundary && array[tempRightBoundary] > tempValue)
        {
            tempRightBoundary--;
        }
        // 移动结束，可以换位置，右标识元素放到左标识里
        array[tempLeftBoundary] = array[tempRightBoundary];

        // 上面是移动右侧游标，下面移动左侧游标

        // 移动完右侧游标，移动左侧游标
        while (tempLeftBoundary < tempRightBoundary && array[tempLeftBoundary] < tempValue)
        {
            tempLeftBoundary++;
        }
        // 移动结束，可以换位置，左标识元素放到右标识里
        array[tempRightBoundary] = array[tempLeftBoundary];

        // 一轮位置交换结束，重新判断是否进循环
    }

    // 放置基准值到找到的最终位置
    // 跳出循环后，把基准值放在中间位置，此时tempRight和tempLeft一定是相等的
    array[tempRightBoundary] = tempValue;

    // 从基准值一刀两半，两边两个字数组继续快速排序递归
    QuickSort(array, leftBoundary, tempRightBoundary - 1);
    QuickSort(array, tempLeftBoundary + 1, rightBoundary);
}

主函数内

// 创建无序数组
int[] arr = new int[] { 8, 7, 1, 5, 4, 2, 6, 3, 9 };

// 调用快速排序
QuickSort(arr, 0, arr.Length - 1);

// 打印输出
for (int i = 0; i < arr.Length; i++)
{
    Console.WriteLine(arr[i]);
    // 1
    // 2
    // 3
    // 4
    // 5
    // 6
    // 7
    // 8
    // 9
}

总结

  • 归并排序和快速排序都会用到递归，两者的区别：
    • 相同点：都会用到递归，都会把数组分成几部分。
    • 不同点：
      • 归并排序递归过程中会不停产生新数组用于合并；快速排序不会产生新数组。
      • 归并排序是拆分数组完毕后再进行排序；快速排序是边排序边拆分。
  • 基本原理：
    • 选取基准，产生左右标识。
    • 左右比基准，满足则换位。
    • 排完一次，基准定位。
    • 左右递归，直到有序。
  • 套路写法：基准值变量，左右游标记录。
  • 3层while循环：
    • 游标不停左右移动。
    • 重合则结束。
    • 结束定基准。
    • 递归排左右。
    • 错位则结束。
  • 注意事项：
    • while循环外定基准。
    • 循环内右边找到放左边，左边找到放右边。

29.2 知识点代码

using System;

namespace Lesson28_快速排序
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("快速排序");

            //主函数内

            #region 知识点二 代码实现

            //创建无序数组
            int[] arr = new int[] { 8, 7, 1, 5, 4, 2, 6, 3, 9 };

            //调用快速排序
            QuickSort(arr, 0, arr.Length - 1);

            //打印输出
            for (int i = 0; i < arr.Length; i++)
            {
                Console.WriteLine(arr[i]);
                //1
                //2
                //3
                //4
                //5
                //6
                //7
                //8
                //9
            }

            #endregion
        }

        #region 知识点一 快速排序基本原理

        //口诀
        //选取基准 产生左右标识
        //左右比基准 满足则换位
        //排完一次 基准定位
        //左右递归 直到有序

        //通俗理解
        //传入要排序的数组 和 要排序的左索引和右索引 用来初始化左右标识 （整个数组要排序的话 左右标识分别为0和数组长度 递归到后面可能只有中间一段要排序）
        //每轮目标：每轮确定基准的最终位置 
        //基准首先和右标识所在的元素比
        //比他大 右标识就-1 继续比 比他小 就把右标识所在的元素 复制到 当前左标识所在的位置上 左标识+1 然后切换到和左标识所在的元素比
        //比他小 左标识就+1 继续比 比他大 就把左标识所在的元素 复制到 当前右标识所在的位置上 右标识-1 然后切换到和右标识所在的元素比
        //以此类推 直到左右标识相等 就是当前基准要放的位置
        //然后从基准切一刀 分成两个序列 递归的进行上面的操作

        #endregion

        //class语句块类 主函数外

        #region 知识点二 代码实现

        //第一步：申明用于快速排序的函数
        /// <summary>
        /// 快速排序函数
        /// </summary>
        /// <param name="array">要排序的数组</param>
        /// <param name="leftBoundary">左边界</param>
        /// <param name="rightBoundary">右边界</param>
        public static void QuickSort(int[] array, int leftBoundary, int rightBoundary)
        {
            //第七步：递归函数结束条件
            //左右标识一进来就相等 就不用排了
            if (leftBoundary >= rightBoundary)return;

            //第二步：声明临时变量 记录 基准值 左游标 右游标
            int tempValue,tempLeftBoundary, tempRightBoundary;
            tempValue = array[leftBoundary];//基准值 相当于把 左标识元素存起来了
            tempLeftBoundary = leftBoundary;
            tempRightBoundary = rightBoundary;


            //第三步：核心交换逻辑
            //左右游标会不同变化 要不相同时才能继续变化
            while(tempLeftBoundary != tempRightBoundary)
            {
                //第四步：比较位置交换

                //首先从右边开始 比较 看值有没有资格放到表示的右侧
                while (tempLeftBoundary < tempRightBoundary 
                    &&
                    array[tempRightBoundary] > tempValue)
                {
                    tempRightBoundary--;
                }
                //移动结束证明可以换位置 右标识元素放到左标识里
                array[tempLeftBoundary] = array[tempRightBoundary];

                //上面是移动右侧游标 下面移动左侧游标

                //接着移动完右侧游标 就要来移动左侧游标
                while (tempLeftBoundary < tempRightBoundary &&
                    array[tempLeftBoundary] < tempValue)
                {
                    tempLeftBoundary++;
                }
                //移动结束证明可以换位置 左标识元素放到右标识里
                array[tempRightBoundary] = array[tempLeftBoundary];

                //一轮位置交换结束 重新判断是否进循环
            }

            //第五步：放置基准值到找到的最终位置
            //跳出循环后 把基准值放在中间位置
            //此时tempRight和tempLeft一定是相等的
            array[tempRightBoundary] = tempValue;

            //第六步：从基准值一刀两半 两边两个字数组继续快速排序递归
            QuickSort(array, leftBoundary, tempRightBoundary - 1);
            QuickSort(array, tempLeftBoundary + 1, rightBoundary);
        }

        #endregion

        #region 知识点三 总结

        //归并排序和快速排序都会用到递归
        //两者的区别
        //相同点：
        //1.他们都会用到递归
        //2.都会把数组分成几部分
        //不同点：
        //1.归并排序递归过程中会不停产生新数组用于合并；快速排序不会产生新数组
        //2.归并排序是拆分数组完毕后再进行排序；快速排序是边排序边拆分

        //基本原理
        //选取基准 产生左右标识
        //左右比基准 满足则换位
        //排完一次 基准定位
        //左右递归 直到有序

        //套路写法
        //基准值变量
        //左右游标记录

        //3层while循环
        //游标不停左右移动
        //重合则结束
        //结束定基准
        //递归排左右
        //错位则结束

        //注意事项
        //while循环外定基准
        //循环内右边找到放左边 左边找到放右边

        #endregion
    }
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com

赏

©2016-2024 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏