快速排序算法

快速排序的基本思想

1、分解
在数组中选择一个记录作为基准（一般选择第一个或者最后一个），以基准将数组划分为两部分，
左边均小于等于基准值，右边均大于等于基准值，基准值位于正确的位置上面
2、求解
划分后，通过递归调用快速排序对左右区间再次进行排序
3、组合
递归调用后左右区间均已有序，组合步骤无需做什么

设序列为R[low,high]，从其中选第一个为基准，设为keyValue,然后设两个指针i和j,分别指向序列R[low,high]的起始和结束位置上：
      1），将i逐渐增大，直到找到大于keyValue的关键字为止；
      2），将j逐渐减少，直到找到小于等于keyValue的关键字为止；
      3），如果i<j，即R[i,j]的元素数大于1，则交换R[i]和R[j]；
      4），将基准记录keyValue放到合适的位置上，即i和j同时指向的位置（或者同时指向的位置-1）,则此位置为新的keyValuePosition。

原始数组： 45, 36, 18, 53, 72, 30, 48, 93, 15, 3
1、选择基准45，令i=0，j=9（数字上界）
2、从右往左扫描，找到第一个小于基准的数字3，将3移至R[i]，及R[0]
第一次移位 3, 36, 18, 53, 72, 30, 48, 93, 15, <--3
此时i=0，j=9
3、从左往右扫描，找到第一个大于基准的数字53，将53移至R[j],即R[9]
第二次移位 3, 36, 18, 53-->, 72, 30, 48, 93, 15, 53
此时i=3，j=9
4、当i<j时继续步骤2、3交替改变扫描方向，重复步骤2找到15，将15移至前面
第三次移位 3, 36, 18, 15, 72, 30, 48, 93, <--15, 53
此时i=3，j=8
5、重复步骤3找到72，将72移至后面
第四次移位 3, 36, 18, 15, 72-->, 30, 48, 93, 72, 53
此时i=4，j=8
6、当i<j时继续步骤2、3交替改变扫描方向，重复步骤2找到30，将30移至前面
第五次移位 3, 36, 18, 15, 30, <--30, 48, 93, 72, 53
此时i=4，j=5
重复步骤3，扫描至i=j=5停止
7、将keyvalue赋值给R[i]
3, 36, 18, 15, 30, 45, 48, 93, 72, 53
8、此时数组已经以45位基准分为左右两部分，左边小于45，右边大于45

9、递归以上步骤

具体代码：

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace quickSort
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] myArray = new int[] { 45, 36, 18, 53, 72, 30, 48, 93, 15, 3 };
            //升序
            SortAsc(myArray, 0, myArray.Length - 1);
        }

        private static void SortAsc(int[] numbers, int low, int high)
        {
            if (low < high)
            {
                //1、设置两个指针，分别指向数组的第一个和最后一个元素
                //2、取数组第一个值为基准，并保存在变量keyvalue中
                int keyvalue = numbers[low];
                int i = low;
                int j = high;
                while (i < j)
                {
                    //3、令j从high开始扫描，直到找到第一个小于基准的记录number[j]，
                    //   将number[j]移至i所指的位置，相当于numer[j]与keyvalue进行了交换
                    //numbers[j]>=keyvalue 必须用>=，否则数组中出现重复数据时会出现死循环
                    while (i < j && numbers[j] >= keyvalue)
                    {
                        j--;
                    }
                    numbers[i] = numbers[j];

                    //4、令i从low开始扫描，直到找到第一个大于基准的记录numbers[i]
                    //   将numbers[i]移至j所指的位置，相当于交换numbers[i]，numbers[j]
                    while (i < j && numbers[i] <= keyvalue)
                    {
                        i++;
                    }
                    numbers[j] = numbers[i];
                }
                //当i=j时，numbers[i]便是基准的位置
                numbers[i] = keyvalue;
                //左半部排序
                SortAsc(numbers, low, i - 1);
                //右半部排序
                SortAsc(numbers, i + 1, high);
            }
        }
    }
}