快速排序:采用分而治之的算法。时间是O(N*LogN)。

主要思路:
  1. 先从元素列表中选取一个数为基准数,一般是选取第一个。
  2. 将小于基准数的元素放在左区间,大于基准数的元素放在右区间。
  3. 继续对左右区间的数进行上一步。

如下图:
快速排序演示图

  1. 选择基准值为3。
  2. 将小于基准值的数放在左区间2,1。将大于基准值的数放在右区间5,4。
  3. 对左区间2,1进行排序为1,2。
  4. 右区间5,4进行排序为4,5。
  5. 组合。

代码实现,如下:

/// <summary>
/// 快速排序
/// </summary>
/// <param name="arry">元素列表</param>
/// <param name="start">开始坐标</param>
/// <param name="end">结束坐标</param>
static void QuickSort(int[] arry, int start, int end)
{
    //只有一位元素
    if (start >= end)
    {
        return;
    }

    //开始坐标
    int frist = start;
    //结束坐标
    int last = end;
    //基准值
    int key = arry[start];

    while (frist < last)
    {
        //从右至左依次查找
        while (frist < last && arry[last] >= key)
        {
            last--;
        }
        arry[frist] = arry[last];

        //从左到右依次查找
        while (frist < last && arry[frist] <= key)
        {
            frist++;
        }
        arry[last] = arry[frist];
    }
    //基准值
    arry[frist] = key;

    //左区间排序
    QuickSort(arry , start , frist - 1);
    //右区间排序
    QuickSort(arry , frist + 1 , end);
}

测试,如下:

static void Main(string[] args)
{
    int[] arry = new[]{5,1,4,7,2,8,3,6,9};

    QuickSort(arry, 0, arry.Length - 1);

    foreach (var i in arry)
    {
        Console.Write(i + ",");
    }
    Console.WriteLine();
    Console.WriteLine("程序运算完成");
    Console.ReadKey();
}

输出:

1,2,3,4,5,6,7,8,9,
程序运算完成

发表评论

电子邮件地址不会被公开。 必填项已用*标注

wJie博客 – 个人博客 is Stephen Fry proof thanks to caching by WP Super Cache