C# 快速排序

古城微笑少年丶 2022-10-30 09:26 95阅读 0赞

static void Main(string[] args)
            {
                int[] array = new int[1000000];//定义一个长度为100的数组
    
                Random random = new Random();
                for (int i = 0; i < array.Length; i++)
                {
                    array[i] = random.Next(array.Length);//给数组随机分配值
                    //Thread.Sleep(10);//休眠10毫秒，可注释掉
                }
                DateTime d1 = DateTime.Now;
                quickSort(array, 0, array.Length - 1);
                //for (int i = 0; i < array.Length; i++)
                //{
                //    Console.WriteLine(array[i]);//循环输出
                //}
                double tt = (DateTime.Now - d1).TotalSeconds;
                Console.WriteLine("总耗时:" + tt + "s");
                Console.ReadKey();
            }
            /// <summary>
            /// 快速排序
            /// </summary>
            /// <param name="array">数组</param>
            /// <param name="left">左边指针</param>
            /// <param name="right">右边指针</param>
            /// <returns></returns>
            static void quickSort(int[] array, int left, int right)
            {
                //如果左边的指针小于右边的指针，那么就需要对该区间中的数据进行排序
                if (left < right)
                {
                    int i = left;//左边指针
                    int j = right;//右边指针
                    int x = array[left];//挖i坑
                    while (i < j)
                    {
                        //从右向左开始找，直到小于x为止
                        while (i < j && array[j] >= x)
                            j--;
                        if (i < j)
                            array[i++] = array[j];//填i坑，挖j坑
                        //从左往右找，直到大于等于x为止
                        while (i < j && array[i] < x)
                            i++;
                        if (i < j)
                            array[j--] = array[i];//填j坑，在挖i坑
                    }
                    //结束，填i坑
                    array[i] = x;
                    quickSort(array, left, i - 1);//左边再继续进行这个操作
                    quickSort(array, i + 1, right);//右边再继续进行这个操作
                }
            }