排序——5.快速排序-白红宇

快速排序

快速排序的核心思想：

1.选出数组中一个元素，将整个数组中比他小的元素放在他左边，比他大的放在他右边。这样整个数组就被分成了两部分，被选出的那个元素就在这两部分中间。

2.再对每一部分执行同样的操作。

3.重复执行第2步，直到每一个部分只有一个元素。

具体是这样实现的，假设有数组a[10]：

选定第一个元素，这里需要一个中间变量来储存选定的元素，int key = a[0]

从右边开始分别与选定的这个元素（也就是a[0]=8）比较，直到一个小于等于8的元素，在这个数组中是a[7]=5。

然后将5放置到a[0]的位置（因为我们已经把a[0]的值放置到变量key中，这样a[0]相当于空了，实际上还是8，但对我们已经没用了）

再从左到右从第一个元素开始分别与key比较大小，同样是将找到的第一个比key大元素的放到刚刚空出来的地方，在这个数组中从左到右第一个比8大的元素是a[8]=11，填到空位里去就是这样：

这样就又出来一个空位，我们再从右到左分别和key比较，然后填空位·······

以此类推，每次填上一个空位就会又多出一个空位直到没有元素可以比较，这时候将key填到剩下的那个空位：

完成这样一次循环，数组被分为两部分：

和

对这每一部分都执行一次上边的分解操作，直到分解到每部分只有用一个元素

这时候就已经完成了排序。

代码入下：

using System;using System.Collections.Generic;using System.Linq;using System.Text;namespace 快速排序{    class Program    {        static void Main(string[] args)        {            int[] a = new int[] { 8, 4, 6, 3, 2, 1, 8, 5, 11, 25 };            Console.WriteLine("未排序之前的顺序：");            foreach (int s in a)            { Console.WriteLine("    {0}", s); }            QuickSort(a,0,a.Length-1);            Console.WriteLine("排序之后的顺序：");            foreach (int s in a)            { Console.WriteLine("    {0}", s); }            Console.ReadKey();        }                public static void QuickSort(int[] Arr, int left,int right)        {            if (left >= right)            { return; }            int i = left;            int j = right;            int key = Arr[left];            while (i < j)            {                while (i < j && key <= Arr [j])                {                    j--;                }                Arr[i] = Arr[j];//这个时候a[j]就是个空位                while (i < j && key > Arr[i])                {                    i++;                }                Arr[j] = Arr[i];//这个时候a[i]就是个空位            }            Arr[i] = key;//用key填上空位            QuickSort(Arr, left, i - 1);            QuickSort(Arr, i + 1, right);        }    }}

运行结果：

总结一下：

大的放右边，小的放左边