lichjx 2016-09-24 04:01 采纳率: 0%
浏览 768

关于快速排序的一个奇怪问题

问题描述:
两种选取key位置的方法完全相同,但是调用一个是函数内调用,另一种是函数外调用,但结果是一个起作用一个不起作用,请问这是为什么?下面上代码。

不起作用的调用函数:

/// <summary>
        /// 快速排序
        /// </summary>
        /// <param name="array">支持IComparable并实现CompareTo方法的类型数组</param>
        /// <param name="left">分组的左边界(初始为数组内任意元素)</param>
        /// <param name="right">分组的右边界(初始为数组右边界)</param>
        /// <param name="tiObj">计时器(默认null,如果从外部传入则需要设置startTime)</param>
        /// <param name="start">是否是递归初始趟</param>
        /// <returns></returns>
        public static string[] quickSort(T[] array, int low, int high, bool start, GCTiming tiObj = null)
        {
            if (tiObj == null)
            {
                tiObj = new GCTiming();
                tiObj.StartTime();
            }

            int pivot = low;
            if (low < high)
            {  
                while (low < high)
                {
                    while (pivot < high)
                    {
                        if (array[pivot].CompareTo(array[high]) <= 0)
                        {
                            high--;
                        }
                        else
                        {
                            array_swap(array, pivot, high);
                            pivot = high;
                            break;
                        }
                    }

                    while (low < pivot)
                    {
                        if (array[low].CompareTo(array[pivot]) <= 0)
                        {
                            low++;
                        }
                        else
                        {
                            array_swap(array, low, pivot);
                            pivot = low;
                            break;
                        }
                    }
                }
                //pivot = array_qsort_partition(array, low, high);

                quickSort(array, low, pivot - 1, false, tiObj);
                quickSort(array, pivot + 1, high, false, tiObj);
            }
            if (start)
            {
                //Thread.Sleep(1000);
                int a = 10;
                object b;
                //for (int i = 0; i < 100000; i++)
                //{
                //    b = (object)a;
                //}
                tiObj.StopTime();
                return new string[] { tiObj.Result().TotalMilliseconds.ToString(), SortUtil<T>.intArrToString(array) };
            }

            return null;
        }

另一个起作用的调用方式:

 static void array_swap(T[] array, int i, int j)
        {
            T temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }

        /** 
         * @author  TIAN 
         * @brief   快速排序(哨兵筛选部分) 
         */
        static int array_qsort_partition(T[] array, int low, int hight)
        {
            int pivot = low;

            while (low < hight)
            {
                while (pivot < hight)
                {
                    if (array[pivot].CompareTo(array[hight]) <= 0)
                    {
                        hight--;
                    }
                    else
                    {
                        array_swap(array, pivot, hight);
                        pivot = hight;
                        break;
                    }
                }

                while (low < pivot)
                {
                    if (array[low].CompareTo(array[pivot]) <= 0)
                    {
                        low++;
                    }
                    else
                    {
                        array_swap(array, low, pivot);
                        pivot = low;
                        break;
                    }
                }
            }

            return pivot;
        }

        /** 
         * @author  TIAN 
         * @brief   快速排序(递归部分) 
         */
       public static string[] array_qsort(T[] array, int low, int high, bool start, GCTiming tiObj = null)
        {
            if (tiObj == null)
            {
                tiObj = new GCTiming();
                tiObj.StartTime();
            }
            if (low < high)
            {
                int pivot = array_qsort_partition(array, low, high);
                array_qsort(array, low, pivot - 1, false, tiObj);
                array_qsort(array, pivot + 1, high, false, tiObj);
            }

            if (start)
            {
                //Thread.Sleep(1000);
                int a = 10;
                object b;
                //for (int i = 0; i < 100000; i++)
                //{
                //    b = (object)a;
                //}
                tiObj.StopTime();
                return new string[] { tiObj.Result().TotalMilliseconds.ToString(), SortUtil<T>.intArrToString(array) };
            }

            return null;
        }

这两种调用为什么一个起作用另一个不起作用呢?
将主函数中的调用也一并奉上,方便大家复现和调试:
main():

class Program
    {
        static void Main(string[] args)
        {
            int orderSize = 20000;
            string[] lastBaseCounting = null;
            int[] arrFixedSize = getBefroeSortArr();
            int[] arrOrderSize = getBefroeSortArr2(orderSize);
            Console.WriteLine("Any key to start sort conting...\r\nPress ESC to exit this Program\r\n");
            while (Console.ReadKey().Key != ConsoleKey.Escape)
            { 
                printStartInfo("fixedSizeArr", arrFixedSize);
                printStartInfo("orderSize", arrOrderSize);
                //选择排序
                string[] res = SortComponent<int>.selectionSortSimple(getTmpArray(arrOrderSize));
                printEndInfo("selectionSortSimple:", fixContingTime(lastBaseCounting, res));
                //插入排序
                /*//这行会出问题,第一组选择排序的执行时间变成了0
                //res = SortComponent<int>.insertSortSimple(getBefroeSortArr2(50000));  */
                /*这样取结果就没问题,选择排序的执行时间会打印出来*/
                string[] res1 = SortComponent<int>.insertSortSimple(getTmpArray(arrOrderSize));
                printEndInfo("insertSortSimple:", fixContingTime(res,res1));
                //冒泡排序
                string[] res2 = SortComponent<int>.popSort(getTmpArray(arrOrderSize));
                printEndInfo("popSort:", fixContingTime(res1, res2));
                //鸡尾酒排序(双向冒泡排序)
                string[] res3 = SortComponent<int>.cocktailSort(getTmpArray(arrOrderSize));
                printEndInfo("cocktailSort", fixContingTime(res2, res3));

                string[] res4 = SortComponent<int>.shellSort(getTmpArray(arrOrderSize));
                printEndInfo("shellSort", fixContingTime(res3, res4));

                string[] res5 = SortComponent<int>.quickSort(getTmpArray(arrOrderSize), 0, orderSize - 1, true);
                printEndInfo("quickSort", fixContingTime(res4, res5));

                //string[] res5 = SortComponent<int>.array_qsort(getTmpArray(arrOrderSize), 0, orderSize - 1, true);
                //printEndInfo("quickSort", fixContingTime(res4, res5));

                printEndInfoWithNoArrayRes("selectionSortSimple:", fixContingTime(lastBaseCounting, res));
                printEndInfoWithNoArrayRes("insertSortSimple:", fixContingTime(res, res1));
                printEndInfoWithNoArrayRes("popSort:", fixContingTime(res1, res2));
                printEndInfoWithNoArrayRes("cocktailSort:", fixContingTime(res2, res3));
                printEndInfoWithNoArrayRes("shellSort:", fixContingTime(res3, res4));
                printEndInfoWithNoArrayRes("quickSort:", fixContingTime(res4, res5));

                lastBaseCounting = res;
                arrOrderSize = getBefroeSortArr2(orderSize);
            }
            //Console.WriteLine("Sort program is end\r\nPress any key to exit program...");
            //Console.ReadKey();
        }

        static void PrintArray(string[] array)
        {
            Console.WriteLine(SortUtil<string>.intArrToString(array));
        }

        static void printStartInfo(string arrname, int[] array)
        {
            Console.WriteLine("{0} before sort is:\r\n", arrname);
            PrintArray(Array.ConvertAll<int, string>(array, s => s.ToString()));
        }

        static void printEndInfo(string name, string[] sortRes)
        {
            Console.WriteLine("after {0} sort:\r\n{2}\r\ntotal time is :{1}ms\r\n\r\n", name, sortRes[0], sortRes[1]);
        }

        static void printEndInfoWithNoArrayRes(string name, string[] sortRes)
        {
            Console.WriteLine("{0}\r\ntotal time is :{1}ms\r\n\r\n", name, sortRes[0], sortRes[1]);
        }

        static int[] getBefroeSortArr()
        {
            return new int[] { 2, 9, 2, 1, 8, 2, 3, 5, 19, 29, 13, 11, 45 };
            //return new int[] { 1, 18, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 };
        }

        static int[] getBefroeSortArr2(int length = 100)
        {
            int[] arr = new int[length];
            Random rn = new Random();
            for (int i = 0; i < length; i++)
            {
                arr[i] = rn.Next(1, length);
            }
            return arr;
        }
        /// <summary>
        /// 创建基础排序数列的副本
        /// </summary>
        /// <param name="arr">样本数列</param>
        /// <returns></returns>
        static int[] getTmpArray(int[] arr)
        {
            int[] tmpArr = new int[arr.Length];
            arr.CopyTo(tmpArr, 0);
            return tmpArr;
        }

        static string[] fixContingTime(string[] resPre,string[] resCur)
        {
            if (resPre == null)
            {
                return resCur;
            }
            string[] tempResForReturn = new string[2];
            resCur.CopyTo(tempResForReturn,0);
            double tmpContingTiem = double.Parse(resPre[0]);
            tempResForReturn[0] = (double.Parse(resCur[0]) - tmpContingTiem).ToString();
            return tempResForReturn;
        }
    }

  • 写回答

2条回答

  • lichjx 2016-09-24 04:05
    关注
    class SortUtil<T> 
        {
            public static void swap(T[] array, int i, int min)
            {
                T temp = array[i];
                array[i] = array[min];
                array[min] = temp;
            }
    
            void swap7(int x, int y)
            {
                if (x == y)
                    return;
                y = x + y - (x = y);
            }
    
            public static string intArrToString(T[] array)
            {
               return string.Join(",", Array.ConvertAll<T, string>(array, s => s.ToString()));
            }
        }
    
    

    算了,我把排序那个类的完整代码也放上来吧:

    /// <summary>
        /// 选择排序
        /// </summary>
        /// <typeparam name="T"></typeparam>
        class SortComponent<T> where T : IComparable<T>
        {
    
            public static string[] selectionSortSimple(T[] array)
            {
                int n = array.Length;
                GCTiming tiObj = new GCTiming();
                //Thread.Sleep(1000);
                tiObj.StartTime();
                Console.WriteLine("选择排序(selectionSort)开始:");
                for (int i = 0; i < n; i++)
                {
                    int min = i;
                    for (int j = i + 1; j < n; j++)
                    {
                        if (array[min].CompareTo(array[j]) > 0)
                        {
                            min = j;
                        }
                    }
    
                    SortUtil<T>.swap(array, i, min);
                }
                tiObj.StopTime();
                return new string[] { tiObj.Result().TotalMilliseconds.ToString(), SortUtil<T>.intArrToString(array) };
            }
            /// <summary>
            /// 插入排序
            /// 一、插入排序 
            ///特点:stable sort、In-place sort
            ///最优复杂度:当输入数组就是排好序的时候,复杂度为O(n),而快速排序在这种情况下会产生O(n^2)的复杂度。
            ///最差复杂度:当输入数组为倒序时,复杂度为O(n^2)
            ///插入排序比较适合用于“少量元素的数组”。
            /// </summary>
            /// <param name="array"></param>
            /// <returns></returns>
            public static string[] insertSortSimple(T[] array)
            {
                int n = array.Length;
                GCTiming tiOb = new GCTiming();
                tiOb.StartTime();
                Console.WriteLine("插入排序(insertionSort)开始:");
                //默认第一个元素排好序了,所以从第二个开始往排好序的方向比较
                for (int i = 1; i < n; i++)
                {
                    //与排好序的方向比较,如果小于前面的就交换后继续比,直到相等或大于后,从刚才的i下标继续往n的方向取元素排序
                    for (int j = i; j > 0; j--)
                    {
                        if (array[j].CompareTo(array[j - 1]) < 0)
                        {
                            SortUtil<T>.swap(array, j, j - 1);
                        }
                        else//如果下标i指针项大于比较项,则无需再向排好序的方向继续比较,因为前面的都是排好序的
                        {
                            break;
                        }
                    }
                }
                tiOb.StopTime();
                return new string[] { tiOb.Result().TotalMilliseconds.ToString(), SortUtil<T>.intArrToString(array) };
            }
    
            public static string[] popSort(T[] array)
            {
                int n = array.Length;
                bool popflag = true;
                GCTiming tiObj = new GCTiming();
                tiObj.StartTime();
                for (int i = 0; i < n && popflag; i++)
                {
                    popflag = false;
                    for (int j = 0; j < n - i - 1; j++)
                    {
                        if (array[j].CompareTo(array[j + 1]) > 0)
                        {
                            SortUtil<T>.swap(array, j, j + 1);
                            popflag = true;
                        }
                    }
                }
                tiObj.StopTime();
                return new string[] { tiObj.Result().TotalMilliseconds.ToString(), SortUtil<T>.intArrToString(array) };
            }
    
            public static string[] cocktailSort(T[] array)
            {
                int n = array.Length;
                bool cocktailFlag = true;
                GCTiming tiObj = new GCTiming();
                tiObj.StartTime();
                for (int i = 0; i < n && cocktailFlag; i++)
                {
                    for (int j = 0; j < n - i - 1; j++)
                    {
                        //大的往后排
                        if (array[j].CompareTo(array[j + 1]) > 0)
                        {
                            SortUtil<T>.swap(array, j, j + 1);
                            cocktailFlag = true;
                        }
                    }
                    for (int k = n - (i + 1) - 1; k > i; k--)
                    {
                        //小的往前排
                        if (array[k].CompareTo(array[k - 1]) < 0)
                        {
                            SortUtil<T>.swap(array, k, k - 1);
                            cocktailFlag = true;
                        }
                    }
                }
                tiObj.StopTime();
                return new string[] { tiObj.Result().TotalMilliseconds.ToString(), SortUtil<T>.intArrToString(array) };
            }
            /// <summary>
            /// 希尔排序
            /// </summary>
            /// <param name="array"></param>
            /// <returns></returns>
            public static string[] shellSort(T[] array)
            {
                int n = array.Length;
                int stepLenth = 1;
                GCTiming tiObj = new GCTiming();
                tiObj.StartTime();
                while (stepLenth < n / 3)
                /*目前已知最好的序列: Sedgewick's 序列 (Knuth的学生,Algorithems的作者)的序列: 1, 5, 19, 41, 109, ....
                  该序列由下面两个表达式交互获得:
                    1, 19, 109, 505, 2161,….., 9(4k – 2k) + 1, k = 0, 1, 2, 3,…
                    5, 41, 209, 929, 3905,…..2k+2 (2k+2 – 3 ) + 1, k = 0, 1, 2, 3, …
                */
                {
                    stepLenth = stepLenth * 3 + 1;
                }
    
                while (stepLenth >= 1)
                {
                    //从第二个元素开始
                    for (int i = 1; i < n; i++)
                    {
                        //从第i个元素开始,依次次和前面已经排好序的i-h个元素比较,如果小于,则交换
                        for (int j = i; j >= stepLenth; j -= stepLenth)
                        {
                            if (array[j].CompareTo(array[j - stepLenth]) < 0)
                            {
                                SortUtil<T>.swap(array, j, j - stepLenth);
                            }
                            else//如果大于,则不用继续往前比较了,因为前面的元素已经排好序,比较大的大就是教大的了。
                            { break; }
                        }
                    }
    
                    stepLenth = stepLenth / 3;//步长除以三递减
                }
                tiObj.StopTime();
                return new string[] { tiObj.Result().TotalMilliseconds.ToString(), SortUtil<T>.intArrToString(array) };
            }
            /// <summary>
            /// 快速排序
            /// </summary>
            /// <param name="array">支持IComparable并实现CompareTo方法的类型数组</param>
            /// <param name="left">分组的左边界(初始为数组内任意元素)</param>
            /// <param name="right">分组的右边界(初始为数组右边界)</param>
            /// <param name="tiObj">计时器(默认null,如果从外部传入则需要设置startTime)</param>
            /// <param name="start">是否是递归初始趟</param>
            /// <returns></returns>
            public static string[] quickSort(T[] array, int low, int high, bool start, GCTiming tiObj = null)
            {
                if (tiObj == null)
                {
                    tiObj = new GCTiming();
                    tiObj.StartTime();
                }
    
                int pivot = low;
                if (low < high)
                {  
                    while (low < high)
                    {
                        while (pivot < high)
                        {
                            if (array[pivot].CompareTo(array[high]) <= 0)
                            {
                                high--;
                            }
                            else
                            {
                                array_swap(array, pivot, high);
                                pivot = high;
                                break;
                            }
                        }
    
                        while (low < pivot)
                        {
                            if (array[low].CompareTo(array[pivot]) <= 0)
                            {
                                low++;
                            }
                            else
                            {
                                array_swap(array, low, pivot);
                                pivot = low;
                                break;
                            }
                        }
                    }
                    //pivot = array_qsort_partition(array, low, high);
    
                    quickSort(array, low, pivot - 1, false, tiObj);
                    quickSort(array, pivot + 1, high, false, tiObj);
                }
                if (start)
                {
                    //Thread.Sleep(1000);
                    int a = 10;
                    object b;
                    //for (int i = 0; i < 100000; i++)
                    //{
                    //    b = (object)a;
                    //}
                    tiObj.StopTime();
                    return new string[] { tiObj.Result().TotalMilliseconds.ToString(), SortUtil<T>.intArrToString(array) };
                }
    
                return null;
            }
    
    
    
            static void array_swap(T[] array, int i, int j)
            {
                T temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
    
            /** 
             * @author  TIAN 
             * @brief   快速排序(哨兵筛选部分) 
             */
            static int array_qsort_partition(T[] array, int low, int hight)
            {
                int pivot = low;
    
                while (low < hight)
                {
                    while (pivot < hight)
                    {
                        if (array[pivot].CompareTo(array[hight]) <= 0)
                        {
                            hight--;
                        }
                        else
                        {
                            array_swap(array, pivot, hight);
                            pivot = hight;
                            break;
                        }
                    }
    
                    while (low < pivot)
                    {
                        if (array[low].CompareTo(array[pivot]) <= 0)
                        {
                            low++;
                        }
                        else
                        {
                            array_swap(array, low, pivot);
                            pivot = low;
                            break;
                        }
                    }
                }
    
                return pivot;
            }
    
            /** 
             * @author  TIAN 
             * @brief   快速排序(递归部分) 
             */
           public static string[] array_qsort(T[] array, int low, int high, bool start, GCTiming tiObj = null)
            {
                if (tiObj == null)
                {
                    tiObj = new GCTiming();
                    tiObj.StartTime();
                }
                if (low < high)
                {
                    int pivot = array_qsort_partition(array, low, high);
                    array_qsort(array, low, pivot - 1, false, tiObj);
                    array_qsort(array, pivot + 1, high, false, tiObj);
                }
    
                if (start)
                {
                    //Thread.Sleep(1000);
                    int a = 10;
                    object b;
                    //for (int i = 0; i < 100000; i++)
                    //{
                    //    b = (object)a;
                    //}
                    tiObj.StopTime();
                    return new string[] { tiObj.Result().TotalMilliseconds.ToString(), SortUtil<T>.intArrToString(array) };
                }
    
                return null;
            }
        }
    
    
    评论

报告相同问题?

悬赏问题

  • ¥15 飞机曲面部件如机翼,壁板等具体的孔位模型
  • ¥15 vs2019中数据导出问题
  • ¥20 云服务Linux系统TCP-MSS值修改?
  • ¥20 关于#单片机#的问题:项目:使用模拟iic与ov2640通讯环境:F407问题:读取的ID号总是0xff,自己调了调发现在读从机数据时,SDA线上并未有信号变化(语言-c语言)
  • ¥20 怎么在stm32门禁成品上增加查询记录功能
  • ¥15 Source insight编写代码后使用CCS5.2版本import之后,代码跳到注释行里面
  • ¥50 NT4.0系统 STOP:0X0000007B
  • ¥15 想问一下stata17中这段代码哪里有问题呀
  • ¥15 flink cdc无法实时同步mysql数据
  • ¥100 有人会搭建GPT-J-6B框架吗?有偿