首页 > 代码库 > 为什么要定义两个变量进行快速排序

为什么要定义两个变量进行快速排序

2024-09-16 09:02:00   215人阅读

    哪里都有讲快速排序的，啥的，我也看了很多篇别人写的文章。但是好多文章里面都是直接就说拿两个i，j变量，就开始比较了。

    快速排序，简单的说就是，先确定一个基准，然后就把比这个基准大的放到一边，比这个基准小的放到一边。放到一边的时候，是不管它是有序还是无序的。接下来在把之前的操作重复一下，其实就是一个递归的过程。

    为什么要定义两个变量进行快速排序呢？

    其实是这样的，快速排序，为啥叫快速排序呢，快在哪里，快在它减少了交换次数，还有一个原因就是快速排序是在快速排序是不用新开内存的，可以减少内存的使用。它就是在原地完成排序的。可能这样讲，你还是不明白，那我们来进行假设，如果只定义一个变量i的话呢，然后进行比较大小，那不就成了冒泡排序了吗。刚刚还说了快速排序是在原地完成排序的，不需要另外开辟空间资源的。你单独定义一个变量显然是不能实现的。

   为啥要定义如果基准数量在这边，那么就要先从另外一边开始扫描呢。

   先想想如果是放在同一边的话，那不就成了个冒泡排序吗。

   那么接下来我就分享下，我理解的快速排序给大家，请大家多多指教。

   首先，比如我们拿到一个数组 int [] arr=new int(){1,3,5,2,4,8,6,7}。按照我们刚刚的做法，

  

  class Program
    {
        static void Main(string[] args)
        {
            var arr = new int[] { 46, 12, 34, 56, 18, 100, 23, 54 };
            quick_sort(arr, 0, arr.Length - 1);
            foreach (var i in arr)
            {
                Console.WriteLine(i);
            }
            Console.ReadKey();


        }

        static void quick_sort(int[] s, int l, int r)
        {
            //递归调用
            if (l < r)
            {
                int i = AdjustArray(s, l, r);//先成挖坑填数法调整s[]  
                quick_sort(s, l, i - 1); // 递归调用   
                quick_sort(s, i + 1, r);
            }
        }

        /// <summary>
        /// 按照基准数进行调整数组
        /// </summary>
        /// <param name="arr"></param>
        /// <param name="left"></param>
        /// <param name="right"></param>
        /// <returns></returns>
        static int AdjustArray(int[] arr, int left, int right)
        {
            int temp = arr[left]; //假设第一个为基准树

            while (left < right)
            {
                //当左边小于右边，并且基准数小于右边的那个数。
                if (left < right && temp <= arr[right])
                {
                    right--; //把指针像前面移动
                }
                //当左边小于右边，并且基准数大于右边的那个数。
                if (left < right && temp >= arr[right])
                {
                    arr[left] = arr[right]; //说明右边的数比基准数小，那要放到左边来
                    left++;//然后接下来就是左边移动一下了++
                }
                //当左边小于右边，并且基准数大于左边的那个数。
                if (left < right && temp >= arr[left])
                {
                    left++;
                }
                //当左边小于右边，并且基准数小于左边的那个数。
                if (left < right && temp <= arr[left])
                {
                    arr[right] = arr[left];
                    right--;
                }
            }
            arr[left] = temp;
            return left;
        }
}

 

    

为什么要定义两个变量进行快速排序


联系
我们