快速排序

作者：追风剑情发布于：2014-10-5 10:07 分类：Algorithms

开发工具 Visual Studio2010

开发语言 C#

快速排序算法时间复杂度是，而且是不稳定的。

using System;

namespace QuickSortTest
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] R = new int[] { 9, 5, 7, 1, 3, 2, 6, 8, 4};
            QuickSort(R, 0, R.Length-1);

            for (int i = 0; i < R.Length; i++)
                Console.Write(R[i]+" ");

            Console.ReadKey();
        }

        static void QuickSort(int[] R, int s, int t)
        {
            int i = s, j = t;
            int tmp;
            if (s < t) {
                tmp = R[s];//用区间的第一个记录作为基准
                while (i != j)//从区间两端交替向中间扫描，直至i=j为止
                {
                    //从右向左扫描，找第1个关键字小于tmp的R[j]
                    while (j > i && R[j] > tmp)
                        j--;
                    //找到这样的R[j],则R[i]和R[j]交换
                    R[i] = R[j];
                    //从左向右扫描，找第1个关键字大于tmp的R[i]
                    while (i < j && R[i] < tmp)
                        i++;
                    //找到这样的R[i],则R[i]和R[j]交换
                    R[j] = R[i];
                }
                R[i] = tmp;
                QuickSort(R, s, i-1);   //对左区间递归排序
                QuickSort(R, i + 1, t); //对右区间递归排序
            }
        }
    }
}