排序——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);

        }
    }
}

运行结果：

总结一下：大的放右边，小的放左边