快速排序

快速排序(QuickSort)的算法

  英国的计算机科学家,托尼·霍尔于1959年想到的,1961年发表的这个算法也是今天世界计算机产业中使用最多的排序算法,霍尔因此获得了爵士头衔,成为第一个获得这种头衔的科学家。那么快速排序为什么快的呢?原因很简单,它还是强调少做事情,大致原理是这样的:

  首页,对于一大堆无序的数字,从中随机挑选一个,比如是53,这个被随机选上的数字被称为枢值(枢纽的枢),接下来将所有要排序的数字分成两部分,第一部分是大于等于53的,第二部分是小于53的,在第一部完成后,一大推无序的数字就变得稍微有序一点了。

第二步,从上面得到的两堆数字,分别采用第一部的方法各自找一个枢值。对于第一堆,由于所有的数字都比53大,至少也等于53,因此,第二次随机挑选的枢值肯定是一个大于53的数字,比如是79;类似地,对于第二堆,由于所有的数字都小于53,因此第二次随机挑选的枢值肯定小于它,比如4。接下来,再把两堆数字各自分成小于等于相应的枢值得数字序列。这样坐下来分别是小于4的数字,介于453之间的,介于5379之间的,以及大于或等于79。在接下来,同样的方法,四堆变八堆,八堆变十六堆,很快所有数字就排好序了。

  假如有一个学区,里面有2万名高中学生,如果让大家到一个超级大的学校上课,再从中挑选出学生中的尖子,效率一定搞不了。这就相当于是冒牌排序,每一个人都需要和所有人去比。

如果我们把这2万人方法哦10所学校中,每所学校只有两千人,从各个学校先各自挑选学习尖子,在彼此进行比较,这就有效得多了。这就是归并排序原理。

如果我们先划出几个分数线,根据个人成绩的高低把2万人分到10所学校去,第一所学校里的学生成绩最好,第10所学校最差,再找出学习尖子,那就容易多了,工作量最小。这就是快速排序的原理。

  其实,计算机算法和组织的管理,乃至社会的管理,在道理上有相同性,想要提高效率就是要少做事情。

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);
            }
        }
     //交换位置
private static void Swap(int[] numbers, int i, int j) { int number = numbers[i]; numbers[i] = numbers[j]; numbers[j] = number; }
原文地址:https://www.cnblogs.com/tianranhui/p/10175566.html