黑马程序员技术交流社区

标题: 快速排序算法之一二三 [打印本页]

作者: 赵贺景 时间: 2014-6-29 09:38
标题: 快速排序算法之一二三
namespace temp
{

public class QuickSort
{
      /// <summary>
      /// 排序
      /// </summary>
      /// <param name="numbers">；待排序数组</param>
      /// <param name="left">；数组第一个元素索引Index</param>
      /// <param name="right">；数组最后一个元素索引Index</param>
      private static void Sort(int[] numbers, int left, int right)
      {
         //左边索引小于右边，则还未排序完成
         if (left < right)
         {
            //取中间的元素作为比较基准，小于他的往左边移，大于他的往右边移
            int middle = numbers[(left + right) / 2];
            //下标
            int i = left - 1;
            int j = right + 1;
            while (true)
            {
                  while (numbers[++i] < middle && i < right) ;
                  while (numbers[--j] > middle && j > 0) ;
                  if (i >= j)
                     break;
                  Swap(numbers, i, j);
            }
            //递归排，直到循环结束
            Sort(numbers, left, i - 1);
            Sort(numbers, j + 1, right);
         }
      }
      /// <summary>
      /// 交换元素值
      /// </summary>
      /// <param name="numbers">；数组</param>
      /// <param name="i">；当前左边索引</param>
      /// <param name="j">；当前右边索引</param>
      private static void Swap(int[] numbers, int i, int j)
      {
         int number = numbers[i];
         numbers[i] = numbers[j];
         numbers[j] = number;
      }
      public static void Main()
      {
         //用随机数模拟的大数据量
         int[] max = new int[80000];
         //Random r = new Random(Guid.NewGuid().GetHashCode());
         Random r = new Random(Environment.TickCount);
         for (int i = 0; i < max.Length; i++)
         {

            max[i] = r.Next(0, 1000000);

         }
         //秒表掐时间
         Stopwatch s = new Stopwatch();
         s.Start();
         Sort(max, 0, max.Length - 1);
      //追加到集合里
         StringBuilder temp = new StringBuilder();
         for (int i = 0; i < max.Length; i++)
         {
            temp.Append(max[i].ToString() + ",");
         }
         s.Stop();

         // Console.WriteLine(s.Elapsed);
         Console.WriteLine(temp.ToString().Substring(0, temp.Length - 1));
         Console.WriteLine(s.Elapsed);

         Console.ReadLine();
      }
}
}直观的理解快排，就是找中间量，比之大的放右边，比之小的放左边，递归下去直到所有的数据排完。

作者: The_Enternal 时间: 2014-6-29 10:19
请问楼主，Sort函数中left初始值传的是0，right传的是max.lenth-1,那么 //下标 int i = left - 1; int j = right + 1;，这样的话left就是-1，right就是length，数组越界!最有楼主为什么截取字符串，还请楼主指点迷津

作者: 赵贺景 时间: 2014-6-29 10:45
while (numbers[++i] < middle && i < right) ;
while (numbers[--j] > middle && j > 0) ;这里 ++i；是先加的从单步调试可以知道 i的变化过程是 -1 0 1 递增不会报错
substring(位置，长度）只是为了输出stringBuileder 而已

作者: 天佑の清清 时间: 2014-6-29 11:08
快速排序是采用递归的方式对待排序的数列进行若干次的操作,每次操作使得被操作的
数列部分以某个元素为分界值分成两部分,一部分小于该分界值,另一部分大于该分界值。
基本思想是：快速排序是对冒泡排序的改进，基本思想是：在 n 个记录中任取一个记录（常取第一个记录），把该记录放到最终位置，所有记录与它比较，比之小的放在前半部分，比之大的放在后半部分，该记录放在两部分之间，这一过程称为一趟排序；对前后两部分重复上述过程，直到每部分只一个记录为止。

作者: The_Enternal 时间: 2014-6-29 19:06

赵贺景发表于 2014-6-29 10:45
while (numbers[++i] < middle && i < right) ;
while (numbers[--j] > middle && j ...

我试了一下，把代码改成 Console.WriteLine(temp);也能正常输出，感觉没必要进行截取

作者: continue　 时间: 2014-6-29 21:43

The_Enternal 发表于 2014-6-29 19:06
我试了一下，把代码改成 Console.WriteLine(temp);也能正常输出，感觉没必要进行截取

...

改变输出方式只是一种形式而已，计算过程中如果不断的进行屏幕绘制是比较消耗资源的

作者: czwanglei 时间: 2014-7-8 23:46
你好，这种帖子应该编辑为资源分享，不应该写为版块活动、

作者: FrancisTan 时间: 2014-7-9 08:20
有点晕，先把代码复制下来慢慢研究！

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2